Search NASA⌕ Search

DOE OSTI · 1131385

Polygon Subtraction in Two or Three Dimensions

Abstract

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.

Explore related subjects

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Wilson, John E.. 2013-10-01. Polygon Subtraction in Two or Three Dimensions. https://doi.org/10.2172/1131385. https://searchnasa.com/record/osti%3A1131385/polygon-subtraction-in-two-or-three-dimensions

Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Search NASA by Indiciae: BibTeX · RIS.