Complex polygon cutting method for solving intersection degradation problem

Abstract

The invention discloses a complex polygon cutting method for solving an intersection degradation problem. The method comprises steps of a polygon formed by the outer ring boundary of a solid polygon intersects with a cut polygon; if the solid polygon has a hole, the resulting polygon and a polygon formed by the hole are subjected to differencing; an obtained cutting result and a next hole polygon are subjected to differencing until all the hole polygons are processed; and finally, the whole cutting process is ended, and the cutting result of the general polygon is obtained. The method is applicable to any convex, concave or perforated polygon cutting, and can realize the intersection, differencing and union of the solid polygon and the cut polygon, and obtain the correct cutting result in the case of intersection degradation. The frequency of polygon intersection and the summit traversal frequency of cutting result generation are reduced, and the cutting algorithm operation speed is accelerated. The method is better than the Greiner-Hormann algorithm in terms of space consumption and time consumption.

Description

technical field [0001] The invention relates to computer graphics and geographic information system (GIS) technology, in particular to a complex polygon clipping method for solving the intersection degradation problem. Background technique [0002] The polygon clipping algorithm is widely used in geographic information system (GIS), computer graphics, robot kinematics and other fields, and is the basis of many important problems in computer graphics. Clip the part outside the polygon. [0003] At present, there are many classic algorithms for polygon clipping abroad, such as Sutherland-Hodgeman algorithm, Liang-Barsky algorithm, Maillot algorithm and other algorithms, but the above algorithms require the clipping polygon to be a rectangle, and the clipped polygon (also called solid polygon) is a convex polygon. However, in practical applications, the clipping algorithm has universal significance and practical application value only when the solid polygon is a general polygo...

AI Technical Summary

Problems solved by technology

However, none of the above algorithms specifically describe the solution of polygon clipping in the two special cases of coincident edges and tangency of two polygons at vertices (also known as intersection degeneration).

Wang Huiqing et al. used the intersection entry and exit discrimination method between the intersection associated line segments to deal with the problem of key points and double edges. However, this algorithm inserts the intersection point into the vertex list of the solid polygon and the clipping polygon. When generating the clipping result polygon, it needs to be in the solid polygon Switching back and forth between the two vertex lists of the clipping polygon and the traversal, the workload is very heavy

Images