In today’s data-driven world, calculating the minimum circumscribed contour area of a plane point set is widely used in various practical scenarios. It is an important and fascinating task that aims to find a smallest rectangular or polygonal region that completely surrounds a given set of discrete points. This seemingly simple problem hides many challenges that require a combination of mathematics, computational geometry, and optimization methods to solve.
Calculating the minimum circumscribed contour area of a plane point set is of great significance to many fields. First, in computer vision, it is a critical step for tasks such as object detection and image segmentation. By determining the minimum circumscribed contour area of a target object, we can better understand and describe the shape of the object, thereby achieving more accurate target recognition and tracking. In autonomous driving systems, this technology can be used to detect road edges or obstacle boundaries to help vehicles plan paths and make decisions. In addition, in fields such as industrial manufacturing, geographic information systems, and urban planning, calculating the minimum circumscribed contour area of a point set can provide valuable spatial analysis and shape modeling tools.
In the past few decades, researchers have actively explored methods for calculating the minimum circumscribed contour area of a plane point set and have made important progress. Early methods were mainly based on geometric principles, such as rotation jamming, convex hull, and divide-and-conquer strategies. Although these traditional methods perform well in certain scenarios, they have certain limitations in processing complex point sets and large-scale data. In recent years, with the improvement of computer performance and the development of numerical optimization algorithms, some novel and efficient methods have emerged.
Recent research efforts have focused on improving the efficiency and robustness of algorithms. Machine learning-based methods, such as support vector machines (SVM) and artificial neural networks, are introduced to improve the accuracy and speed of convex hull calculations. In addition, through technologies such as multi-core processing, parallel computing and GPU acceleration, researchers strive to improve the operating efficiency of the algorithm so that it can process larger-scale point cloud data. At the same time, the development of deep learning technology has also brought new possibilities for calculating the minimum circumscribed contour area of a plane point set, such as using convolutional neural networks for segmentation and contour estimation.
It is worth mentioning that with the widespread application of three-dimensional scanning technology, researchers have begun to extend the calculation of the minimum circumscribed contour area of a plane point set to three-dimensional point cloud data, and have developed a series of new algorithms. These algorithms are designed to extract the minimum circumscribed volume or surface from complex three-dimensional scenes and have high practical value.
In summary, calculating the minimum circumscribed contour area of a plane point set is a critical and challenging task in the fields of computer vision, image processing, and pattern recognition. By solving this problem, we can extract valuable shape information from discrete point sets, providing powerful support for applications such as target detection, autonomous driving, and spatial modeling. As technology continues to advance and innovate, we can expect to see more exciting developments and breakthroughs in this field.
Two cases are introduced below:
1. Calculate the convex hull first, then calculate the area
The convex hull method is a commonly used method to calculate the minimum circumscribed contour area of a set of plane points. It is based on the principles of mathematical geometry and estimates the minimum circumscribed contour area by finding the set of points that form the convex hull. The following are the advantages and disadvantages of the convex hull method:
Advantages:
Simple and intuitive: The basic principles of the convex hull method are easy to understand. It can condense the point set into a polygon or convex polygon through concise steps, which is easy to represent visually and conceptually.
Accuracy: When the point set satisfies convexity, the convex hull method can provide an accurate minimum circumscribed contour area. This allows the convex hull method to produce reliable results in many practical situations.
Fast calculation: Compared with other complex algorithms, the convex hull method has high computational efficiency. When the size of the point set is small, the convex hull method can usually calculate the minimum circumscribed contour area in a very short time.
Widely applicable: The convex hull method is suitable for various types of point sets, regardless of whether they are evenly distributed, whether there are noise points, etc. Therefore, the convex hull method has wide applicability and can be used to solve problems in many fields.
Disadvantages:
Complex Shape Limitations: The convex hull method may have limitations when dealing with point sets with complex shapes. Since the convex hull requires the generation of a convex polygon that completely surrounds the point set, the convex hull method cannot provide accurate and reasonable results for non-convex point sets or point sets with internal holes.
Sensitive to noise points: The convex hull method is more sensitive to noise points. When outliers or noise points exist in the point set, these points may affect the final convex hull result, resulting in inaccurate calculation of the circumscribed contour area.
Computational efficiency increases with scale: Although the convex hull method runs faster on small-scale point sets, its computational efficiency can decrease rapidly as the size of the point set increases. For large point sets, the computational time of the convex hull method can become quite expensive.
Implementation Complexity: Although the basic principles of the convex hull method are simple and easy to understand, implementing an optimized convex hull algorithm may require complex programming skills and data structure support. This makes implementing and debugging convex hull algorithms potentially challenging.
In summary, the convex hull method, as a common method for calculating the minimum circumscribed contour area of a plane point set, has many advantages. It is simple and intuitive, fast to calculate, and applicable to a variety of situations. However, it may have some limitations when dealing with complex shapes and point sets with noisy points. Therefore, in practical applications, we need to choose an appropriate method according to the characteristics of the problem or combine it with other technologies to solve specific solving tasks.
import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt
#Specify font file path
import matplotlib.font_manager as fm
font_path = 'C:/Windows/Fonts/simhei.ttf'
prop = fm.FontProperties(fname=font_path)
# Define points on the ellipse as a sample point set
points = np.array([[1, 0], [0.866, 0.5], [0.5, 0.866], [0, 1], [-0.5, 0.866], [-0.866, 0.5],
[-1, 0], [-0.866, -0.5], [-0.5, -0.866], [0, -1], [0.5, -0.866], [0.866, -0.5]])
# Calculate the convex hull of the point set
hull = ConvexHull(points)
# Get the vertex coordinates of the convex hull
vertices = hull.points[hull.vertices]
# Draw convex hull boundary and point set
plt.plot(points[:,0], points[:,1], 'o', label='point set')
plt.plot(vertices[:,0], vertices[:,1], 'r--', lw=2, label='convex hull boundary')
plt.xlabel('x', fontproperties=prop)
plt.ylabel('y', fontproperties=prop)
plt.title('Convex hull and point set', fontproperties=prop)
plt.legend(prop=prop)
plt.grid(True)
plt.axis('equal')
plt.show()
# Calculate the area of the polygon formed by the convex hull vertices
area = hull.area
print("convex hull vertex coordinates:\
", vertices)
print("convex hull area size:", area)
Convex hull vertex coordinates:
[[-1. 0. ]
[-0.866 -0.5 ]
[-0.5 -0.866]
[ 0. -1. ]
[0.5-0.866]
[0.866-0.5]
[ 1. 0. ]
[0.866 0.5]
[0.5 0.866]
[0.1.]
[-0.5 0.866]
[-0.866 0.5 ]]
Convex hull area size:6.211565981473167 (theoretical area is np.pi)
Note: There is still a certain gap in the area. You can take more points to reduce the error.
2. Map the plane point set contour to the image and calculate the area through the opencv function cv2.contourArea
This method is also suitable for concave point sets to solve tasks that the convex hull method cannot complete.
import matplotlib.pyplot as plt
import cv2
import numpy as np
# Arc parameters
radius=1.0
start_angle = 0 # Starting angle, unit: degrees
end_angle = 270 #End angle, unit: degrees
num_points_arc = 1000 # Number of data points on the arc
# Convert the starting angle and ending angle to radians
start_angle_rad = np.deg2rad(start_angle)
end_angle_rad = np.deg2rad(end_angle)
# Calculate the polar coordinates of the point on the arc
theta_arc = np.linspace(start_angle_rad, end_angle_rad, num=num_points_arc)
x_arc = 0 + radius * np.cos(theta_arc)
y_arc = 0 + radius * np.sin(theta_arc)
# Straight line parameters
line1_start_point = (0, 0)
line1_angle = start_angle_rad
line2_start_point = (0,0)
line2_angle = end_angle_rad
# Calculate data points on the straight line
num_points_line = 1000 # Number of data points on each straight line
l=np.linspace(0, radius, num=num_points_line)
x_line1 = line1_start_point[0] + l*np.cos(line1_angle)
y_line1 = line1_start_point[1] + l*np.sin(line1_angle)
x_line2 = line2_start_point[0] + l*np.cos(line2_angle)
y_line2 = line2_start_point[1] + l*np.sin(line2_angle)
# Combine data points
X = [x_line1,x_arc,x_line2[::-1]]
Y = [y_line1,y_arc,y_line2[::-1]]
fig = plt.figure(figsize=(5, 5))
plt.rcParams['xtick.direction'] = 'in' # Set the tick mark direction of the x week inward
plt.rcParams['ytick.direction'] = 'in' # Set the scale direction of the y-axis inward
clist = ['blue', 'red', 'green', 'black', 'darkgreen', 'lime', 'gold', 'purple', 'green', 'cyan', 'salmon', 'grey' ,
'mediumvioletred', 'darkkhaki', 'gray', 'darkcyan', 'violet', 'powderblue']
# for i in range(len(X)):
# plt.plot(X[i],Y[i], c=clist[i])
# plt.tight_layout()
# plt.show()
# Create a blank image
blank_image = np.zeros((1400, 1400), dtype=np.uint8)
#Coordinate transformation
X_new=np.array(X).flatten() + radius
Y_new=-1*np.array(Y).flatten() + radius
# Convert to integer array
X_shifted = np.array(X_new*700, dtype=np.int32)
Y_shifted = np.array(Y_new*700, dtype=np.int32)
# draw outline
points = np.column_stack((X_shifted, Y_shifted))
cv2.drawContours(blank_image, [points], contourIdx=0, color=255, thickness=3)
# Calculate the area enclosed by the contour
area = cv2.contourArea(points)/700/700
#Theoretical area calculation
theta_span = end_angle_rad - start_angle_rad
theoretical_area = 0.5 * radius * radius * theta_span
# Output the area result and compare it with the theoretical area
print("The area enclosed by the outline: ", area)
print("Theoretical area:", theoretical_area)
print("Area difference:", area - theoretical_area)
# show image
cv2.namedWindow('Contour Image',0)
cv2.imshow("Contour Image", blank_image)
cv2.waitKey(0)
cv2.destroyAllWindows()
The area enclosed by the outline: 2.3565163265306124
Theoretical area: 2.356194490192345
Area difference: 0.0003218363382675449
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. OpenCV skill tree Home page Overview 23694 people are learning the system