| Abstract [eng] |
An algorithm for polygon set-operations (union, intersection, difference) was introduced. In CAD system these operations are very important and widely used. The most important aspects are speed and quality of results. Previously used and analyzed polygon operations was based on grid calculations. Thus this strategy takes big amount of time to perform operation and generates not exact results. The major idea in presented algorithm for polygon operations was to use sweeplines through calculated event points (all vertexes and intersection points between data segments). For each sweepline the intervals information is generated (depending on amount of up and down directions from crossed segments). Afterward these intervals are connected between each other to construct the final polygon. As additional feature of this algorithm is support of arcs, quadratic and cubic bezier curves, which connects polygon vertexes. The results of this algorithm were compared with results of scanline (grid) based algorithm and Java2D API (this API is not able to process big amount of data, thus this is used only to check the correctness of result for polygon operations). After implementation and experiments it is obvious that this algorithm works and provides better results (speed and quality of resulting polygons). The detailed comparison and analysis of polygons set-operations is presented in experimental part of this paper. |
