CN101114379A - A method to determine whether a point is inside a polygon - Google Patents

Abstract

The invention belongs to the technical fields of computer graphics technology and computational geometry, and is a method for judging whether a point is located in a polygon. The present invention first carries out convex subdivision to polygons, and establishes binary tree to manage these convex polygons; Then, according to the coordinate position of the detected point, investigates the binary tree established, to find the convex corresponding to the leaf node of the binary number. polygon, and then detect whether the point is located in the convex polygon to determine whether the detected point is located in the given polygon. The invention has the advantages of high calculation speed, less storage space than similar methods based on polygon division, and easy implementation. It is applicable to the situation where multiple points need to perform this inclusive judgment on the same polygon.

Description

A method to determine whether a point is inside a polygon

technical field

The invention belongs to the technical fields of computer graphics technology and computational geometry, and in particular relates to a method for judging whether a point is located in a polygon.

Background technique

It is a basic problem in computational geometry to determine whether a point is located in a polygon, and the methods in this area are widely used in many fields such as computer graphics, pattern recognition, and geographic information systems. The methods in this respect can be divided into two categories, one is not to pre-process the polygon, and the other is to pre-process the polygon.

In the former method, the most commonly used method is the ray method, that is, a ray is sent from the detected point, and the number of sides of the polygon intersected with it is calculated. If it is an odd number, the point is located in the polygon, otherwise it is located in the polygon. outside. This type of method needs to calculate each side of the polygon, and the time complexity is high, which is O(N) (that is, the calculation amount is linearly corresponding to N), and N is the number of sides of the polygon.

In the latter method, it is mainly to organize the sides of the polygon, the covered area, etc., so that the time complexity of judgment calculation is reduced and the calculation speed is accelerated. For example, the famous trapezoidal subdivision method (see Zalik B, Jezernik A., Zalik KR. Polygon trapezoidation by sets of open trapezoids. Computers & Graphics 2003; 27(5): 791-800.), using a straight line passing through the parallel coordinate axis of the vertex , divide the polygon into some trapezoids, and then arrange the trapezoids in order according to the monotonous increase or decrease of the trapezoidal coordinate values. When judging and calculating, binary search technology can be used to avoid processing many sides and reduce the time complexity of judging and calculating to O(logN), where N is the number of sides of the polygon.

In practical applications, polygons with a large number of sides are often encountered, but the existing technical methods have a large space overhead, and it is not convenient to process polygons with a large number of sides, which is limited by space expression ability or computing power. , the judgment efficiency is not high.

Contents of the invention

The purpose of the present invention is to provide a method for judging whether a point is located within a polygon, which improves calculation speed and reduces space overhead.

Whether judging point of the present invention is positioned at the method for polygon, its step comprises:

1) Divide the given polygon into a set of monotone polygons;

2) Carry out convex subdivision of the non-convex polygons in the above-mentioned monotone polygons to obtain a convex polygon set of given polygons;

3) The straight line formed by the sides of the convex polygon is used as the dividing line, and a balanced binary tree is established based on the number of convex polygons on both sides of each dividing line, in which the root node and the middle node store the respective corresponding dividing lines, and each leaf node stores the corresponding a convex polygon;

4) According to the positional relationship between the given point and the dividing line stored in the non-leaf nodes of the balanced binary tree, the above-mentioned balanced binary tree is searched until a leaf node is reached;

5) Determine the positional relationship between the given point and the convex polygon corresponding to the leaf node, if the point is inside the convex polygon, then the point is inside the given polygon; otherwise, the point is outside the given polygon.

The invention is a method for preprocessing polygons, which is also based on the subdivision of polygon coverage areas. Compared with the existing method, the subdivided units are convex polygons, and the number of units generated by other subdivision methods is less than that of other subdivision methods. Therefore, the space overhead of establishing a binary tree and expressing convex polygons is saved. The time complexity of binary tree search is O(logN), and the time complexity of judging whether a point is located in a convex polygon is also O(logN), so the time complexity of the present invention is also O(logN). But thanks to the small number of subdivision units, its judgment speed is faster than the method based on trapezoidal subdivision. When dealing with polygons with a large number of sides, the efficiency of judging whether a point is inside a polygon is greatly improved, and it is suitable for various methods that need to judge whether a point is inside a polygon multiple times for the same polygon.

Description of drawings

Figure 1 Diagram of the convex subdivision operation of polygons.

Fig. 2 Convex subdivision results of polygons.

Fig. 3 The balanced binary tree established according to the result graph of convex subdivision.

Figure 4 is a diagram of the method for judging whether a point is within a convex polygon.

Figure 5 is a flow chart of judging whether a point is within a polygon.

Detailed ways

The method of the present invention mainly comprises following two phases: the first phase is to carry out convex dissection to given polygon, establishes balanced binary tree and manages convex polygon; Whether the detected point is inside the polygon.

1. The implementation steps of the first stage are as follows:

First, the given polygon is divided into some monotone polygons (that is, the sides of each such polygon can be divided into 2 monotone edge sequences) (see the literature de Berg M, van Kreveld M, Overmars M, et al. Computational Geometry: Algorithms and Applications.2nd ed.Berlin: Springer, the method in 2000), and then each monotone polygon is convexly divided.

What the present invention adopted is a kind of convex subdivision method without adding points, and Fig. 1 is the convex subdivision operation figure of polygon, and its concrete steps are as follows:

1) Divide the polygon into monotone polygons

a) Find all the upper concave points and lower concave points of the polygon; here, if the Y coordinate value of a concave point is smaller than the Y coordinate value of its two adjacent vertices, then the concave point is called an upper concave point; if a concave point If the Y coordinate value of a point is greater than the Y coordinate values of its two adjacent vertices, the concave point is called a concave point;

b) For all the upper concave points and lower concave points, sort them according to their Y coordinate values;

c) For each upper concave point, connect it with any lower concave point or convex vertex whose Y coordinate value is smaller than it to form a side, select the side that is within the polygon and has the shortest side length, and cut the polygon once In the same way, for each concave point, connect it with any upper concave point or convex vertex whose Y coordinate value is greater than it to form a side, select the side that is located in the polygon and has the shortest side length, and divide the polygon perform a split;

d) Repeat the operation of c), the upper concave point and the lower concave point must be operated once;

2) Divide non-convex monotone polygons into convex polygons

a) Find the concave points in the monotone polygon, and sort their Y coordinate values from large to small;

b) Process the concave points sequentially according to the order of the Y coordinate value from large to small, connect the concave point with the concave point or other vertices whose Y coordinate value is smaller than it, and select the side with the shortest side length and within the monotone polygon as the a subdivision of the monotonic polygon;

c) Repeat the operation of b) until there is no concave point in each divided polygon, that is, the union of these convex polygons is the original polygon. Figure 2 is the result of the convex subdivision of the polygon.

3) Build a balanced binary tree that manages convex polygons

The set composed of convex polygons is iteratively divided into two sets, that is, the set of convex polygons under investigation is divided into two sets each time until there is only one convex polygon in each subset. In the process of bisection, for the sides of these polygons in the polygon set under consideration, extend the two ends of each side to form a straight line collinear with these sides, calculate the difference in the number of convex polygons on both sides of each straight line, and The ratio of the number of convex polygons intersected by the straight line to the number of convex polygons in the set determines the dividing line that divides the set.

Their specific calculation methods are as follows:

a) Assuming that the set of convex polygons located on the left side of a straight line is S _L , the set of convex polygons located on the right side is S _R , and the set of convex polygons intersecting the line is S _I , the numbers of convex polygons they contain are respectively n _L , n _R , n _I . We calculate 3 parameters, the purity $\mathrm{PD}\left(\mathrm{Pure\; Degree}\right)=\frac{{\mathrm{no}}_L+{\mathrm{no}}_R}{{\mathrm{no}}_L+{\mathrm{no}}_R+{\mathrm{no}}_I},$ Balance $\mathrm{BD}\left(\mathrm{Balance\; Degree}\right)=1-\frac{|{\mathrm{no}}_L-{\mathrm{no}}_R|}{{\mathrm{no}}_L+{\mathrm{no}}_R},$ Selectivity SD (Selection Degree)=Min(PD, BD), that is, the smaller value of the two values of PD and BD is the value of SD.

b) Calculate the SD value for each straight line, and then use the straight line with the largest SD value as the dividing line of this convex polygon set, and divide this set into two sub-sets. At this time, these two sub-sets must contain the same division Convex polygons intersected by lines.

Here, the purpose of calculating PD is to make the number of convex polygons intersected with the dividing line as small as possible, so as to reduce the number of repeated processing of convex polygons, reduce the height of the tree, save storage space and speed up judgment calculation; calculate BD The purpose is to make the two sides of the tree as balanced as possible, so as to improve the speed of the corresponding binary search when judging the calculation.

The established balanced binary tree is shown in Fig. 3, in which the intermediate nodes of the tree record the related division straight lines, and its leaf nodes record the related convex polygon.

2. The implementation steps of the second stage are as follows:

(1) According to the coordinates of the detected points, search the binary tree from top to bottom, that is: first examine the root node of the tree, see which side of the line the detected point is located on, and then use the child corresponding to that side The node is taken as the object of the next investigation, and iteratively proceeds until the leaf node is reached, and the convex polygon in the leaf node is the convex polygon to be found.

(2) For the convex polygon in the leaf node, to judge whether the detected point is located in the convex polygon, first divide its edge into two monotone edge sequences, that is: find the vertex with the largest Y coordinate value in the convex polygon and A vertex with the smallest Y coordinate value divides the edge of the polygon into two parts according to these two vertices, each part is a sequentially connected edge, and the Y coordinate value of the vertices of these edges increases or decreases in sequence Then, form a straight line parallel to the X axis according to the Y coordinate value of the detected point, as shown in Figure 4, calculate the X coordinate values of the two intersection points of the straight line and the two monotone edge sequences of this convex polygon, compare the detected Whether the X coordinate value of the point is between the X coordinate values of the two intersection points. If so, the point lies within this convex polygon, that is, within the given polygon; otherwise, it is outside the given polygon.

Fig. 5 is an overall flow chart of the present invention for judging whether a point is located within a polygon.

The following are some experimental data of the present invention: 4 polygons are randomly generated for experimentation, and they all have 10,000 sides, but the proportions of their concave points are 0%, 10%, 30% and 50% respectively. A polygon with a concave ratio of 0% is a convex polygon. During the test, we evenly distribute 1000 points in the polygonal bounding box for detection, and take their average detection time as the experimental data. We compared the new method with the randomized incremental trapezoidation-based algorithm (the randomized incremental trapezoidation-based algorithm), which is the fastest known in the world. The experimental data are shown in the table below. Experiments show that the number of convex polygons used by the new method is less than the number of trapezoids used by the random increasing trapezoidal method, and the new method is better than the random increasing trapezoidal method in terms of storage space requirements and detection speed.

Dimple ratio (%) Number of convex polygons or trapezoids to divide Number of tree nodes Maximum tree depth (hierarchical tree) trapezoidal (trapezoidal method) Convex polygon (this invention) trapezoidal method this invention trapezoidal method this invention 0% 20001 1 46317 1 46 1 10% 20001 1423 51792 2316 56 12 30% 20001 3628 50769 5910 51 15 50% 20001 4229 50903 7464 47 15

Dimple ratio (%) Preprocessing time (ms) storage space(KB) Average time to detect a point (microseconds) trapezoidal method this invention trapezoidal method this invention trapezoidal method this invention 0% 54.79 13.63 2446 1200 0.87 0.38 10% 61.30 52.78 2556 1536 0.85 0.50 30% 60.20 77.82 2535 2057 0.95 0.51 50% 61.20 100.00 2538 2254 0.86 0.75

Experiments show that compared with the current fastest method based on trapezoidal division—incremental trapezoidal method, the method of the present invention has the same complexity in various aspects such as the time of polygon preprocessing, space requirements and judgment calculations, but the new method The generated convex polygons are less than the trapezoids generated by the incremental trapezoidal method, so the new method requires less space and faster judgment speed.

Claims (7)

1. A method for judging whether a point is located in a polygon, the steps comprising: 1) Divide the given polygon into a set of monotone polygons; 2) Carry out convex subdivision of the non-convex polygons in the above-mentioned monotone polygons to obtain a convex polygon set of given polygons; 3) The straight line formed by the sides of the convex polygon is used as the dividing line, and a balanced binary tree is established based on the number of convex polygons on both sides of each dividing line, in which the root node and the middle node store the respective corresponding dividing lines, and the leaf nodes store the corresponding convex polygons. polygon; 4) According to the positional relationship between the given point and the dividing line stored in the non-leaf nodes of the balanced binary tree, the above-mentioned balanced binary tree is searched until a leaf node is reached; 5) Determine the positional relationship between the given point and the convex polygon corresponding to the leaf node, if the point is inside the convex polygon, then the point is inside the given polygon; otherwise, the point is outside the given polygon. 2. the method for judging whether point is located in polygon as claimed in claim 1, is characterized in that described step 1) is: a) find all the concave points and concave points of the polygon; b) For all the upper concave points and lower concave points, sort them according to their Y coordinate values; c) For each upper concave point, connect it with any lower concave point or convex vertex whose Y coordinate value is smaller than it to form a side, select the side that is inside the polygon and has the shortest side length, and cut the polygon once In the same way, for each concave point, connect it with any upper concave point or convex vertex whose Y coordinate value is greater than it to form a side, select the side that is located in the polygon and has the shortest side length, and divide the polygon perform a split; d) Repeat the operation of c), the upper concave point and the lower concave point must be operated once. 3. the method for judging whether the point is located in the polygon as claimed in claim 1 or 2, is characterized in that described step 2) is: a) Find the concave points in the monotone polygon, and sort their Y coordinate values from large to small; b) Process the concave points sequentially according to the order of the Y coordinate value from large to small, connect the concave point with the concave point or other vertices whose Y coordinate value is smaller than it, and select the side with the shortest side length and within the monotone polygon as the a subdivision of the monotonic polygon; c) Repeat the operation of b) until there is no concave point in each divided polygon. 4. the method for judging whether point is located in polygon as claimed in claim 1, it is characterized in that calculating and dividing the ratio of the number of convex polygons in the current convex polygon collection intersected by straight line relative to the convex polygon number in the collection, and Positioned on the ratio of the number of convex polygons in the current convex polygon set on both sides of the dividing line to select the dividing line that divides the current convex polygon set, the steps are as follows: 1) Let the sets of convex polygons located on both sides of a dividing line be S _L , S _R , and the set of convex polygons intersecting the line be S ₁ , and the numbers of convex polygons they contain are n _L , n _R , n ;Calculation of 3 parameters; purity $\mathrm{PD}\left(\mathrm{Pure\; Degree}\right)=\frac{{\mathrm{no}}_L+{\mathrm{no}}_R}{{\mathrm{no}}_L+{\mathrm{no}}_R+{\mathrm{no}}_I},$ balance $\mathrm{BD}\left(\mathrm{Balance\; Degree}\right)=1-\frac{|{\mathrm{no}}_L-{\mathrm{no}}_R|}{{\mathrm{no}}_L+{\mathrm{no}}_R},$ Selectivity SD (Selection Degree) = Min (PD, BD); 2) Select a dividing line with the largest SD value as the dividing line of the current convex polygon set. 5. The method for judging whether a point is located in a polygon as claimed in claim 4, characterized in that: if there are multiple dividing straight lines with the maximum SD value, then choose one as the dividing straight line of the current convex polygon set. 6. the method for judging whether point is located in polygon as claimed in claim 1, it is characterized in that described step 4) is for starting from the root node of binary tree, judges which side that detected point is positioned at its relevant dividing straight line, and Take the corresponding child node here as the tree node to be investigated in the next step, and iteratively operate along the tree node until a leaf node is reached. 7. the method for judging whether point is located in polygon as claimed in claim 1 or 6, it is characterized in that described step 5) divides the edge of the convex polygon corresponding to this leaf node into two monotone edge sequences; then, according to given The Y coordinate value of the fixed point forms a straight line parallel to the X axis, and calculates the X coordinate value of the two intersection points of the line and the two monotone edge sequences of the convex polygon; if the X coordinate value of the given point is located at the X of the two intersection points coordinate values, then the point is inside the convex polygon and inside the given polygon; otherwise, the point is outside the convex polygon and outside the given polygon.

Images