Boolean Operation Of Two Planar Polygons

Geometry engine is one of the underlying technologies of CAD software,and Boolean operation is one of the core algorithms of geometry engine.The stability and efficiency of the Boolean algorithm play a crucial role in the performance of the geometry engine.There are two main reasons for the instability of geometric calculation algorithms.One is the digital calculation error caused by the number system,and the other is the theoretical level of the algorithm caused by the incomplete handling of various special situations such as geometric singularities,which are unique to geometric calculation.To a large extent,the algorithm stability and running speed of geometric calculation are mutually restricted.The Boolean operation of two planar polygons is the basis of the three-dimensional Boolean operation,and the geometric singularity of the Boolean operation of two planar polygons mainly appears in special geometric positional relationships such as overlapping points and overlapping edges.Based on the theory of geometric numbers and its preliminary application in Boolean operations,this paper systematically sorts out various geometric singularities of Boolean operations of two planar polygons,and realizes the unified expression and calculation of various geometric singularities of Boolean operations of two planar polygons based on geometric numbers.And build the stability and speed test sample and test system of Boolean algorithm of two planar polygons test.It mainly includes the following contents:(1)The geometric number expression calculation method of three overlapping points and four overlapping points is proposed,which solves the problem of unified processing of various geometric singularities in Boolean operations of two planar polygons by geometric number theory.Systematically analyzed the characteristics of various geometric singularities,and proposed the idea of splitting the three and four overlapping points into two points,and provided a complete solution for the three and four overlapping points based on geometric numbers.(2)Constructed an algorithm based on geometric number consistency Boolean operation(GNCBO).Based on the existing geometric Boolean operation framework,the algorithm for overlapping-points processing and part of the program implementation are given.Combined with the algorithm for reoverlapping-edges processing and the method of inclusive testing,the algorithm is implemented in C++ language.(3)Design samples and test methods for the stability and running time of Boolean operations of two planar polygons,develop an interactive test system for algorithm performance,and provide a testing tool platform for the research of Boolean operations of two planar polygons algorithms.Stability test samples include sample data for various geometric singularities such as overlapping points and overlapping edges;runtime test samples include randomly generated samples and test sample data for specified overlapping points and overlapping edges.Developed algorithm stability and running time performance testing software system,which provides functions such as interactive selection of test sample types,graphic display of sample graphics and Boolean operation results,and output of time test results.(4)The algorithm is tested and performance analyzed.No misjudgments occurred in the stability test,indicating that the algorithm can correctly handle geometric singularities from a theoretical level.When there are geometric singularities of various overlapping points,the running speed of the GNCBO algorithm proposed in this paper fluctuates little: on an ordinary laptop computer,the average running time for 10,000 tests on four sets of test data containing various overlapping points is about 0.170938 s,the average standard deviation is about0.009378s.