Search NASA⌕ Search

SEARCH · Search NASA

Results for “polygon subtraction algorithm”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

Polygon Subtraction in Two or Three Dimensions

There has been much previous work on the topic of Boolean operations for polygons. Most of the emphasis has been on polygon clipping (polygon intersection). One of the earliest solutions was by Weiler and Atherton whose general approach of processing lists of vertices is incorporated into this algorithm. A very good treatment of the operations of intersection, union, and difference was provided by Margalit and Knott. More recently, Rivero and Feito developed an efficient method of operation based on representing polygons through simplices, and Peng et al. provided performance improvements. However, their methodology requires that polygons be translated to the first quadrant before processing. This subtraction or difference algorithm was developed to provide a polygon subtraction (or polygon difference) that works on simple polygons (as defined by Margalit and Knott) in two or three dimensions. Inputs to the algorithm are two lists of vertices—each list representing a polygon. The output from the algorithm is a list of polygons (each of which is a list of vertices) that represent the areas inside one of the original polygons but not the other. The general methodology is to begin by finding a point on the first polygon that is outside the other polygon. Starting from that point, construct the output polygon by tracing around first polygon until hitting a point of intersection with other polygon. Switch to other polygon and continue adding to the output polygon by tracing backward until hitting a point of intersection with original polygon. Switch back to original polygon and continue tracing. Continue tracing and switching until arriving back at starting point (closing the output polygon). After all points in the first polygon have been processed, the process is repeated for the second polygon.

polygon difference algorithm↗