CN111915665B - A method for determining points in polygons using simplified intersection calculation on computer - Google Patents

Abstract

The invention relates to a method for judging points in a polygon by using simplified intersection calculation on a computer, which comprises the following steps: reading the vertex coordinates of the polygon into a computer memory to generate a polygonal bounding box, performing uniform grid division on the polygonal bounding box, and generating a strip-shaped structure parallel to one coordinate axis in a grid unit; meanwhile, judging whether the segment divided by the intersection point of the grid line and the edge of the polygon is positioned in/out of the polygon; for a test point, a ray is emitted from the test point and is parallel to a coordinate axis parallel to the generation of the strip structure; counting the number of polygon edges intersected by the ray until the ray reaches an unambiguous grid line segment; and according to the parity of the intersection times and the attribute that the grid line segment reached by the ray is positioned in/out of the polygon, whether the test point is positioned in the polygon can be known. The invention can greatly simplify the intersection calculation, efficiently utilize the parallel processing capability of the computer and greatly improve the calculation efficiency.

Description

A method for determining points in polygons using simplified intersection calculation on computer

technical field

The invention belongs to the processing fields of computer algorithms, computer graphics, computational geometry, and geographic information systems, and specifically relates to a method for determining and calculating points within a polygon, that is, for the spatial position of a point, it is determined whether the position is located in a polygon. methods within a defined spatial area.

Background technique

The determination calculation of a point within a polygon is a basic computing technology in computer graphics, computational geometry, and geographic information system processing. For a polygon, for any test point, it is necessary to determine whether the point is located within the polygon. There are many works in this area, among which the ray method and the method based on uniform meshing are widely used. The ray method is to emit a ray from the test point and count the number of times it intersects with the edges of the polygon. If the number of intersections is even, the test point is outside the polygon; otherwise, it is inside. The ray method requires an intersection test with each side of the polygon, and its computational complexity is O(N), where N is the number of sides of the polygon. In order to reduce the computational complexity, a variety of methods are proposed. First, a certain preprocessing is performed on the polygon, such as dividing the polygon into a trapezoid or a convex polygon, and then the local area where the test point is located can be quickly located, and then according to the situation of the local area. Judgmental calculation. This type of method can reduce the number of polygon edges that need to be detected, and the computational complexity can be reduced to O(logN). However, the preprocessing of such methods is more troublesome. To this end, the uniform grid method proposes to divide the bounding box of the polygon into a rectangular grid aligned with the coordinate axis, so that simple preprocessing can be performed, and the detection of test points can also be limited to the local area adjacent to the grid cell where it is located. area carried out. After comparing various methods, the uniform grid method is an efficient calculation method for point-in-polygon determination suitable for practical applications. Further, a method combining the ray method and the uniform grid method is proposed. First, the attributes of each grid intersection point inside/outside the polygon are calculated. The ray method is used to determine the calculation of points within the polygon. Since a mesh intersection is related to multiple mesh cells, the polygon edges in these mesh cells are all checked. To this end, some methods propose to first calculate the attribute that the center point of each grid unit is located inside/outside the polygon, then connect the test point to the center point of the grid unit where it is located, and improve the grid center point located in the polygon. The determination calculation method of inner/outer properties and the optimization of grid resolution, as well as the method of robust processing for some ambiguity cases, can reduce the computational complexity of preprocessing of the uniform grid method to O(N), Reduces the expected value of the complexity of the test computation to O(1).

Although the combination of the ray method and the uniform grid method minimizes the computational complexity, the basic intersection operation between the test ray and the polygon edge still requires a lot of multiplication, addition and other calculations. For computer processors , the computational cost is still relatively high.

SUMMARY OF THE INVENTION

In order to solve the above-mentioned technical problems, the present invention proposes a point-in-polygon determination method on a computer that simplifies the calculation of intersection, so as to simplify the calculation of intersection and facilitate the efficient use of the parallel processing capability of the computer, thereby improving the accuracy of points within the polygon. Judge the computational efficiency. The invention further improves the combination of the ray method and the grid method. First, the ray emitted by the test point is fixed in a direction parallel to a coordinate axis, so that a coordinate of the intersection point can be known in advance, and the computational complexity of the intersection between the ray and the polygon edge is reduced. At the same time, the strip-like structure is managed for the edge segments of the polygons in the mesh unit, so that the edges in each strip-like structure may intersect the rays located in the strip-like structure. Edges that the ray does not intersect will not need to intersect the ray, and it is also beneficial to use the GPU for parallel computing for better efficiency, because there is no need for time-consuming fork processing to determine whether a ray and an edge may intersect.

The technical solution of the present invention is a method for judging points within a polygon that simplifies the calculation of intersection, comprising the following steps:

Step (1) read the vertex coordinates of the polygon into the computer memory to generate the bounding box of the polygon, so that the boundaries of the bounding box are all located outside the polygon; the bounding box of the polygon is divided into a uniform mesh aligned with the coordinate axis, according to the polygon's bounding box. The intersection of grid lines whose sides are parallel to the X-axis or Y-axis divide these grid lines into many segments, and determine and record the attributes of each grid line segment inside/outside the polygon;

Step (2) Generate a strip structure in each grid cell to manage the edge segments of the polygons contained in the mesh cell. Here, a strip structure is bounded by edges parallel to the Y axis or the X axis constituted so that the edge segments of the polygons intersect with both ends of the strip structure;

Step (3) When inputting test points for detection, use a single processor or multiple processors in parallel, for each test point, emit a ray parallel to the Y-axis or X-axis from it, and gradually calculate its and X-axis from near to far. The intersection of the X-axis or Y-axis parallel grid lines, until the attribute that the intersection is located inside/outside the polygon can be known from the attribute that the segment of the grid line where it is located is located inside/outside the polygon, at this time, the forward line of the ray is terminated;

In step (4), the relevant strip structures to be used are called in, and in a separate processor or a parallel processor, the judgment calculation of the point in the polygon is carried out; The intersection of the edges of the polygons in the strip-like structure passing through, and the number of intersections of the ray and the edges of the polygons is counted;

Step (5) According to the results of steps (3) and (4), the attribute that the test point is located inside/outside the polygon is known.

Further, the step (1) determines that the segment divided by the intersection point of the grid line and the polygon edge is located in the polygon inside/outside attribute, and the steps are as follows:

(1.a) A grid line can be regarded as a ray emitted from a point at its outermost end, and the intersection of the grid line and the side of the polygon is obtained by intersecting it with the edge of the polygon;

(1.b) The outermost points of the grid lines are located outside the polygon. At the same time, according to the ray method of judging and calculating the points within the polygon, it can be seen that the attributes of adjacent grid line segments inside/outside the polygon change alternately. .

Further, in the step (2), for the edge segments of the polygons in each grid unit, a strip-like structure is established for management, and the steps are as follows:

(2.a) For the edge segments in a grid unit, according to the X or Y coordinate values of their endpoints located in the grid unit, generate many parallel lines parallel to the Y or X coordinate axis, and use these parallel lines as The boundary divides the grid cell into many strips;

(2.b) Each strip structure records the edges it contains, without recording the coordinates of the endpoints of the edge segments.

Further, the ray emitted when a test point is tested in the step (3) is parallel to the boundary edge of the strip structure.

Further, in the step (3), when the ray emitted from the test point and the grid line are intersected from near to far, it is judged whether the attribute that the intersection is located in/outside the polygon can be determined by the grid line segment where it is located. The attributes located inside/outside the polygon are used to know whether the ray stops moving forward; if it can be known, the ray stops moving forward; otherwise, the ray needs to continue moving forward for intersection processing with subsequent grid lines.

Further, in the step (4), when a test ray and the edge of the polygon in each strip structure that it passes through are subjected to the intersection test, it is not necessary to detect whether the edge intersects the ray before the intersection point is obtained. Therefore, Facilitates the use of computer parallelism, such as reducing time-consuming fork processing when using GPUs. When calculating the intersection of a ray and an edge, a coordinate value of the intersection is known, which is the coordinate value of the coordinate axis perpendicular to the ray; by judging the size of another coordinate value of the intersection and another coordinate value of the test point , that is, to know whether the ray really intersects the edge.

Further, in the step (5), the results of steps (3) and (4) are integrated to obtain the attribute that the test point is located inside/outside the polygon, and the processing is as follows:

(5.a) If the intersection of the ray and the grid line is located within the polygon when the ray terminates and moves forward, the test point is located within the polygon when the number of intersections between the ray and the polygon's edge is an even number; otherwise, it is outside;

(5.b) If the intersection of the ray and the grid line is located outside the polygon when the ray terminates and moves forward, the test point is located outside the polygon when the number of intersections between the ray and the edge of the polygon is an even number; otherwise, it is inside.

Beneficial effects:

The invention can greatly save operations such as multiplication and addition in the calculation of intersection, and can efficiently use the parallel processing capability of the computer such as GPU, etc., and can greatly improve the calculation efficiency of the point in the polygon.

Description of drawings

Figure 1 shows the calculation of the intersection between the edge of the polygon and the grid line, and then according to the situation of the intersection, the segment of the horizontal grid line is determined to be located inside/outside the polygon. At the same time, each grid unit is organized in a strip structure to effectively manage the edge segments in each grid unit;

Fig. 2 is the intersection of the ray and the horizontal grid line of the test point, and the calculation of the intersection of the ray and the edge in the strip structure that passes through, thus, it can be determined whether the test point is located in the polygon;

3 is a statistical processing method for the intersection of the ray and the edge of the polygon when the ray and the edge of the polygon are collinear, or when the ray passes through the vertex of the polygon;

Figure 4 shows the 4 polygons used for testing, (a) a polygon with a small number of sides; (b) a polygon with a small number of sides and a relatively balanced distribution; (c) a polygon with a large number of sides but an uneven distribution; (d) ) is a polygon with many sides and a well-balanced distribution.

Figure 5 is a flow chart of the method of the present invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only a part of the embodiments of the present invention, but not all of the embodiments. Based on the embodiments of the present invention, those of ordinary skill in the art can obtain all other The embodiments all belong to the protection scope of the present invention.

The present invention is a point-in-polygon determination method using a computer to simplify the calculation of intersection, which can be used in many scenarios in engineering, for example, in a geographic information system, for roads, buildings, parks, etc. Area limitation; when certain objects need to be located, such as whether a certain car is on a certain road or in a certain park, the present invention can be used for quick retrieval. Or, when flood floods a city, the area covered by flood can be represented by polygon, then using the present invention, it can quickly know which positions are not covered by flood and are safe.

According to an embodiment of the present invention, without loss of generality, the present invention generates both the strip structure and the ray for testing in a direction parallel to the Y axis, and the ray is emitted upward from the test point (the direction in which the Y coordinate gradually increases). ),As shown in Figure 1.

According to an embodiment of the present invention, the above-mentioned method of the present invention is divided into two stages:

The first stage preprocesses the polygons;

The second stage: According to the preprocessing results, determine whether a test point is located within the polygon.

The working steps of the first paragraph are as follows:

1) Detect the X and Y coordinates of all vertices of the polygon, and obtain the smallest X coordinate, the smallest Y coordinate, the largest X coordinate and the largest Y coordinate. Then, decrease the minimum X coordinate and the minimum Y coordinate by a predetermined value, respectively increase the maximum X coordinate and the maximum Y coordinate by a predetermined value, thereby obtaining the bounding box of the polygon, and the boundaries of the bounding box are located in the polygon. outside.

2) Uniform meshing with optimized mesh resolution for bounding boxes. Each grid was calculated according to the method in "Jing Li and Wencheng Wang. 2014. Point-In-Polygon Tests by Applying the Ray Crossing Method LocallyVia Grid Center Points. International Journal of Electrical Engineering 21, 3(2014), 85–92." The lengths Mx and My of the cell along the X and Y axes are:

Mx=k*sqrt(M*W/H),

My=k*sqrt(M*H/W)

and Ivana Kolingerova.2001.A cell-based point-in-polygonalgorithm suitable for large sets of points.Computers&Geosciences 27,10(2001),1135–1145.”得到的网格单元总数，一般约为N，这里N为多边形的边数。Here, k is an empirical coefficient, generally set k = 1; W and H are the width and height of the bounding box, respectively; M is based on "Borut

and Ivana Kolingerova.2001.A cell-based point-in-polygonalgorithm suitable for large sets of points.Computers&Geosciences 27,10(2001),1135–1145.” The total number of grid cells obtained is generally about N, where N is The number of sides of the polygon.

3) For the edge of each polygon, calculate the X coordinate of its intersection with the grid lines parallel to the X axis. Here, iterative addition can be used according to the feature that the distance between adjacent grid lines parallel to the X axis is equal. Step by step to find the X coordinate of each intersection point. As shown in FIG. 1 , the interval between the coordinates x1 and x2 and the interval between x2 and x3 of the intersection of the side AB and the grid line parallel to the X axis are equal.

4) According to the intersection of the sides of the polygon and the grid lines parallel to the X axis, each grid line parallel to the X axis is divided into many segments; the attributes of these segments inside/outside the polygon can be obtained according to the ray method, and recorded . At this time, for the case where the edge of the polygon is collinear with the grid line parallel to the X axis, it is a segment by itself on the grid line, and its inside/outside polygon attribute is marked as "ambiguous".

5) According to the intersection of the edge of the polygon and the grid line, you can know which polygonal edge fragments each grid unit has; the X coordinates of the endpoints of these edge fragments, or the X coordinate of the intersection of the edge and the grid line parallel to the X axis coordinate, or the X coordinate of the grid lines parallel to the Y axis. According to the X coordinates of these endpoints, a vertical line parallel to the Y axis is generated as the boundary line of the strip structure, so as to obtain the strip structure division result of the grid unit, and the included edges are recorded in each strip structure (no need to record the endpoint coordinates of these edge fragments). The attribute that the upper boundary of a strip structure is located inside/outside the polygon is the attribute that its segment on the grid line parallel to the X axis is located inside/outside the polygon, because its upper boundary must be one of the grid lines. within the fragment. As shown in Figure 1, the grid cell containing point C is divided into 3 strip structures.

The working steps in the second stage are as follows:

(1) According to the X coordinate of the test point, an upward ray parallel to the Y axis is generated.

(2) Calculate the intersection of the ray and the grid line parallel to the X axis from the near and far, until the intersection is located at the inner/outer property of the polygon.

(3) For each strip-like structure that the ray passes through, the intersection of the ray and the edge therein is detected. At this time, the X coordinate of the intersection point is known, and it is only necessary to calculate the Y coordinate of the intersection point, which can be obtained from the line equation of the edge and the X coordinate of the ray. If the resulting Y coordinate is smaller than the Y coordinate of the test point, the edge is below the test point and will not intersect the ray; otherwise, it is a true intersection. If it is a real intersection, the number of statistical intersections will increase by 1; otherwise, if it is not a real intersection, it will not be counted. For the case where the ray passes through the vertex of the polygon or is collinear with the edge of the polygon, the intersection statistics are performed as shown in Figure 3:

3.1) If a vertex of the polygon passed by the ray has two associated edges on the same side of the ray, the two edges related to the vertex are not statistically processed; otherwise, the two edges related to the vertex are counted as The ray intersects the edge of the polygon 1 time.

3.2) If the ray is collinear with an edge of the polygon, and the 2 edges associated with the edge are on the same side of the ray, then the edge and its associated 2 edges are not subject to statistical processing; otherwise, the edge and the associated 2 The number of edges is counted as one intersection of the ray and the edge of the polygon.

(4) According to the attribute that the intersection of the ray and the grid line parallel to the X-axis is located inside/outside the polygon, and the statistics of the number of intersections of the ray and the sides of the polygon, it can be known whether the test point is located in the polygon. If the number of intersections is even, the test points have the same inside/outside polygon properties as the intersection points; otherwise, their inside/outside polygon properties are opposite. As shown in Figure 2, the number of intersections is odd, and the test point q is inside the polygon because the intersection of the ray and the horizontal grid line is outside the polygon at this time.

In the present invention, the GPU of the computer can be used for parallel computing to improve the detection speed. At this time, all strip structures are first loaded into the global memory of the GPU; then, according to the parallel processing capability of the GPU, a group of test points to be processed is grouped, so that each group is processed by one processor in the GPU; finally, By calling in the relevant strip structures to be used by each processor, the judgment calculation of points within the polygon can be performed in parallel in each processor of the GPU.

and IvanaKolingerova.2001.A cell-based point-in-polygon algorithm suitable for largesets of points.Computers&Geosciences 27,10(2001),1135–1145)的推荐。这4个多边形在图4中展示，(a)Pol 10，(b)Pol100，(c)Pol1249，(d)Pol28000，分别有10条边、100条边、1249条边和28000条边。测试时在多边形的包围盒中随机均匀地采样了1000 000个点作为测试点。相关测试所有的计算机配置有一个Intel(R)Core(TM)i7-8700 CPU,16GB内存，一个NVIDIA GeForce GTX 1080Ti GPU(有16GB的存储空间)。The present invention is tested on a computer, and the comparison method is the most efficient grid method GCP (Jing Li and Wencheng Wang. 2014. Point-In-Polygon Tests by Applying the RayCrossing Method Locally Via Grid Center Points. International Journal of Electrical Engineering 21, 3 (2014), 85–92.). According to the number of sides of the polygon and whether the distribution of the sides of the polygon is uniform, 4 polygons were selected for the test. They come from (Borut

and Ivana Kolingerova. 2001. A cell-based point-in-polygon algorithm suitable for largesets of points. Computers & Geosciences 27, 10 (2001), 1135–1145). The 4 polygons are shown in Figure 4, (a) Pol 10, (b) Pol100, (c) Pol1249, (d) Pol28000, with 10 edges, 100 edges, 1249 edges and 28000 edges, respectively. During testing, 1000,000 points are randomly and uniformly sampled in the polygon's bounding box as test points. Related tests All computers were configured with an Intel(R) Core(TM) i7-8700 CPU, 16GB of RAM, and an NVIDIA GeForce GTX 1080Ti GPU (with 16GB of storage).

The experimental results for the comparison of these two methods are as follows:

*Calculation of speedup ratio: (t1-t2)/t2, t1 and t2 are the time spent by GCP and the present invention respectively.

Statistics of various computations used to complete these tests:

*re1, re2, and re3 are respectively the saving of the related computation amount of the multiplication, addition and comparison operations required by the present invention compared to the GCP method, and the calculation is: the required number of operations of the present invention/the number of corresponding operations required by GCP.

It can be seen from the above experimental results that although this method requires more computation and more space to store the preprocessing results in the preprocessing stage, the increase is not very large. During detection and calculation, the present invention can greatly save the number of required multiplication, addition, and comparison operations, thereby greatly improving the detection speed; and, due to the efficient use of the parallel processing capability of the computer, the present invention can obtain more Higher computing efficiency on the CPU.

The parts of the present invention that are not described in detail belong to the well-known technology in the art.

The above description is only a part of the specific embodiments of the present invention, but the protection scope of the present invention is not limited thereto. Any changes or substitutions that can be easily conceived by any person skilled in the art within the technical scope disclosed by the present invention shall be included within the protection scope of the present invention.

Claims (6)

1. a method for determining a point in a polygon using simplified intersection calculation on a computer, is characterized in that, comprises the following steps: Step (1) Read the vertex coordinates of the polygon into the computer memory or the cache in the GPU to generate the bounding box of the polygon, so that the boundaries of the bounding box are all located outside the polygon; perform a uniform mesh aligned with the coordinate axis on the bounding box of the polygon Grid division, which divides the grid lines into many segments according to the intersection of the polygon's sides and the grid lines parallel to the X-axis or the Y-axis, and calculates the attributes of each grid line segment inside/outside the polygon; Step (2) Generate a strip structure in each grid cell to manage the edge segments of the polygons contained in the mesh cell. Here, a strip structure is bounded by edges parallel to the Y axis or the X axis constituted so that the edge segments of the polygons intersect with both ends of the strip structure; Step (3) When inputting test points for detection, use multiple processors in parallel, for each test point, emit a ray parallel to the Y-axis or X-axis from it, and gradually calculate its relationship with the X-axis or X-axis from near to far. The intersection of the Y-axis parallel grid lines, until the attribute that the intersection is located inside/outside the polygon can be known from the attribute that the segment of the grid line where it is located is located inside/outside the polygon, at this time, the forward line of the ray is terminated; Step (4) Load the relevant strip structure to be used by the processor. In the parallel processor, calculate the intersection of the ray emitted from a test point and the polygon edge, and count the number of intersections between the ray and the polygon edge. ; Step (5) According to the results of steps (3) and (4), the attribute that the test point is located inside/outside the polygon is known. 2. a kind of computer according to claim 1 uses the point in polygon of simplification to find the intersection calculation method, it is characterized in that: Described step (1) judges that the segment that the grid line is divided by its intersection with the edge of the polygon is located in the polygon inside/outside attribute, and its steps are as follows: (1.a) A grid line can be regarded as a ray emitted from a point at its outermost end, and the intersection of the grid line and the side of the polygon is obtained by intersecting it with the edge of the polygon; (1.b) The outermost point of the grid line is located outside the polygon. At the same time, according to the ray method of judging and calculating the point within the polygon, it can be known that the attributes of adjacent grid line segments located inside/outside the polygon are alternately changed , from this, it can be known that each segment on the grid line is located inside/outside the polygon. 3. a kind of computer according to claim 1 uses the point in polygon of simplifying the intersection calculation method to judge, it is characterized in that: In the step (2), for the edge segments of the polygons in each grid unit, a strip-like structure is established for management: the steps are as follows: (2.a) For the edge segments in a grid unit, according to the X or Y coordinate values of their endpoints located in the grid unit, generate many parallel lines parallel to the Y or X coordinate axis, and use these parallel lines as The boundary divides the grid cell into many strips; (2.b) Each strip structure records the edges it contains, without recording the coordinates of the endpoints of the edge segments. 4. a kind of computer according to claim 1 uses the point in polygon of simplifying the intersection calculation method to judge, it is characterized in that: In the step (3), the rays emitted when a test point is tested are parallel to the boundary edge of the strip structure. 5. a kind of computer according to claim 1 uses the point in polygon of simplification of calculating intersection to determine method, it is characterized in that: In the step (3), when the ray emitted from the test point and the grid line are intersected from near to far, the attribute of judging whether the grid line segment where the intersection is located is located inside/outside the polygon is known, and is determined by This determines whether the ray stops advancing; if it is known, the property that the intersection is inside/outside the polygon is equivalent to the property that the segment of the grid line it is on is inside/outside the polygon, and the ray stops advancing; otherwise, the ray continues The forward and subsequent grid lines are intersected. 6. a kind of computer according to claim 1 uses the point-in-polygon determination method of simplified intersection calculation, it is characterized in that: In the described step (5), the results of the steps (3) and (4) are integrated to obtain the attribute that the test point is located in/outside the polygon, and the processing is as follows: (5.a) If the intersection of the ray and the grid line is within the polygon when the ray stops advancing, then the test point is within the polygon when the number of intersections between the ray and the sides of the polygon is an even number; otherwise, it is outside; (5.b) If the point of intersection with the grid line when the ray stops advancing is outside the polygon, the test point is outside the polygon when the number of intersections of the ray and the sides of the polygon is an even number; otherwise, it is inside.

Images