When working with polygons, correctly determining their enclosed area is crucial. However, self-intersections and inconsistent edge orientations introduce uncertainty regarding this area.
To repair corrupt polygons, Fade2D provides a Polygon Clipper. This tool efficiently supports polygons that may contain holes, resolving self-intersections and correctly orienting polygon edges around the enclosed area. The properties it generates ensure the polygons are suitable for subsequent Zone2
creation. Additionally, the Polygon Clipper can restrict a polygon to a defined region.
Note: This example and the article have been updated since the last software release. While similar code is included in the download package under examples_2D/ex14_polygonRepair.cpp, please download the latest code for Example 14 here.
Self-Intersections in Polygons: Causes, Effects and Solutions
Polygon corruption often stems from subtle computational and data-handling errors that distort the coordinates. Here are some main causes:
- Rounding Errors: Small inaccuracies during calculations can misalign vertices, causing gaps or overlaps between edges. Techniques that calculate each polygon vertex only once can help prevent these issues.
- Precision Loss: Saving 64-bit coordinates to 32-bit formats cuts precision, possibly introducing self-intersections.
- Parsing from ASCII Files: Reading coordinates from ASCII files, even with high decimal precision, can introduce rounding errors. Using binary file formats that support 64-bit precision is preferable.
- Inaccurate Input: Users may draw inaccurate segments in GUI widgets.
These issues cause polygons to develop self-intersections that make them unreliable for geometric operations.
The Importance of Proper Polygon Orientation
Not only is the absence of intersections critical, but the orientation of the individual edges is also very important. The essential property of a polygon with edges oriented counterclockwise (CCW) is that the area lies to the left of each edge. See the image below…
However, this property does not hold for self-intersecting polygons, like the one shown at the top of the image below.
When a Zone2
is created from a self-intersecting polygon, the outside area can mistakenly appear as being inside this polygon. To avoid this, we must resolve all self-intersections by splitting the edges at their intersection points. After that, the orientation of the polygon edges must be adjusted. The PolygonClipper
handles this process automatically, yielding reliable polygons.
Correctly Creating A Zone After Polygon Clipping
In Fade2D, a Zone2
object represents a specific region in a triangulation. The most common type of a Zone2
uses a ConstraintGraph2
object as a boundary. Provided you are certain that the ConstraintGraph2
is properly oriented and free of self-intersections, you should create a Zone2
as follows:
Fade_2D dt; // Delaunay triangulation std::vector<Segment2> vSeg; // Polygon edges ConstraintGraph2* pCG; pCG=dt.createConstraint(vSeg,CIS_CONSTRAINTED_DELAUNAY,true); Zone2* pZone=dt.createZone(pCG,ZL_INSIDE); // Inside region
Super important: We call createConstraint()
with true
as the third argument, which corresponds to bool bOrientedSegments
. This indicates to the function that the segments are already oriented counterclockwise around the polygon area.
If this parameter is false
or not specified, the function orients the edges automatically, but this requires the polygon to be simple. A simple polygon features no self-intersections and consists of one connected component without holes, with each vertex appearing exactly once as corner point. Luckily, you can overcome this limitation using the PolygonClipper
to split and orient the edges upfront, and then specifying bOrientedSegments=true
as shown in the above code snippet when calling createConstraint()
.
Step-by-Step: Using the Polygon Clipper to Fix Polygons (C++)
Let’s dive right into Example 14
, included in the download package. You will agree that the source code for this example is quite straightforward.
int ex14_polygonRepair_main() { // Step 1: Create and visualize a vector of unoriented Segment2's vector<Segment2> vSegmentSoup; createInputSegments(vSegmentSoup); Visualizer2 v("example14_dirtyInput.pdf"); v.addObject(vSegmentSoup,Color(CBLACK)); for(size_t i=0;i<vSegmentSoup.size();++i) { // Add the indices v.addObject(Label(vSegmentSoup[i].getSrc(),to_string(i).c_str(),true,11),Color(CBLACK)); } v.writeFile(); // Step 2: Create a PolygonClipper, providing the self-intersecting // segment soup and, optionally, a small threshold for the minimum // segment length. Segments shorter than this threshold will be // collapsed in the input set. PolygonClipper clipper(vSegmentSoup,1e-6); // Step 3: Retrieve the outer hull of the repaired polygon. Note // that this hull may consist of multiple polygons if the result // is disjoint. Regardless, the resulting Segment2s are oriented // counterclockwise around the polygon area. This property is // crucial as it enables the creation of a Zone2 object, where // inside/outside knowledge is essential. vector<Segment2> vHullSeg; clipper.getOuterSegments_CCW(vHullSeg); visualize("hullPolygon",vHullSeg); // * Step 4 * Retrieve all inner and outer segments of the repaired // polygon. These segments are oriented counterclockwise around // the polygon area. The output vector may contain multiple polygons, // but this output is still suitable for defining a Zone2, as the // orientation of the Segment2s provides the necessary inside/outside // information. vector<Segment2> vFullSeg; clipper.getSegments_regionOriented(vFullSeg); visualize("completePolygon",vFullSeg); return 0; }
In Step 1, we create a vector of unoriented and self-intersecting Segment2
objects that define a corrupt polygon. The details of the used createInputSegments()
function are not essential for this discussion, as you will be inserting your own polygon here. The image below shows the corrupt polygon, consisting of multiple components.
In Step 2, we generate a PolygonClipper
by passing both the segments and a distance threshold to its constructor. The distance threshold sets a minimum edge length, causing the PolygonClipper
to collapse any edges shorter than this value. You can specify 0 to disable collapsing or -1 for an automatically determined collapse distance based on the coordinates’ numerical uncertainty. The next two steps demonstrate two different options for retrieving the edges of the repaired polygon:
Retrieving the Repaired Polygon: Outer Hull or Complete Polygon
In Step 3, we retrieve the segments of the polygon’s outermost boundary while ignoring any inner layers that may exist. Use this function if you are certain that the polygon has no holes or if you wish to discard them. The image below illustrates the result.
In contrast, Step 4 retrieves all layers of the polygon, including any holes. The image below shows the complete polygon along with its inner layers.
In any case, all returned segments orient counterclockwise (CCW) around the polygon’s area. Observe in the image that the boundaries of holes are therefore globally oriented clockwise (CW).
Clipping: Limiting a Polygon to a Certain Region
In Step 5, the code demonstrates how to limit polygons to a certain region. For simplicity, we use the polygon vFullSeg
from the previous step as input and define a box-shaped region as Zone2 pWindow
. We pass pWindow
and vFullSeg
to the function clipPolygon()
. The result is stored in the output vector vClippedResult
, which is then drawn and saved as a .PDF file (see the image below).
// * Step 5 * We want to limit vFullSeg to the region 'pWindow' // - Create a box-shaped Zone2, 'pWindow' vector<Segment2> vBox; vBox.emplace_back(Segment2(Point2(0,-60),Point2(80,-60))); vBox.emplace_back(Segment2(Point2(80,-60),Point2(80,30))); vBox.emplace_back(Segment2(Point2(80,30),Point2(0,30))); vBox.emplace_back(Segment2(Point2(0,30),Point2(0,-60))); Fade_2D dt; ConstraintGraph2* pCG; pCG=dt.createConstraint(vBox,CIS_CONSTRAINED_DELAUNAY,true); Zone2* pWindow=dt.createZone(pCG,ZL_INSIDE); // Limit vInputPolygon to pWindow vector<Segment2> vClippedResult; clipPolygon(pWindow, vFullSeg, false, vClippedResult); Visualizer2 v2("example14_clipped.pdf"); v2.addObject(vClippedResult,Color(CBLACK,.001,true)); v2.writeFile();
The clipped polygon meets the required correctness properties for further processing. It is ready for creating a Zone2
, as it is free of self-intersections and has correctly oriented segments.
Analyzing a Polygon Layer-by-Layer
In this advanced topic, we will explore the PolygonTree
data structure within the PolygonClipper
and demonstrate how it can be used to traverse and analyze a polygon layer by layer. By working through this example, you will gain valuable insights into the relationships between the nodes of the PolygonTree
and the corresponding polygon layers. Let’s dive straight into the source code:
void analyzePolygonTree() { // Step 1: Retrieve a nested input polygon with multiple layers // and components vector<Segment2> vNestedInput; getNestedInput(vNestedInput); // Step 2: Use the PolygonClipper to create a PolygonTree that // organizes the input into a root node and hierarchical children, // representing the layers of the polygon. PolygonClipper clipper(vNestedInput,0); PolygonTree* pRootNode(clipper.getPolygonTree()); // Step 3: Retrieve all nodes from the PolygonTree and assign // unique colors for subsequent visualization. map<PolygonTree*,Color> mNodeToColor; vector<PolygonTree*> vAllNodes; pRootNode->getChildrenRecursive(vAllNodes); for(PolygonTree* pNode:vAllNodes) { mNodeToColor[pNode]=Color(Color::getNextColorName()); } // Step 4: Visualize each polygon layer in a distinct color to // enable easy identification in the PolygonTree Visualizer2 vis("polygonTree.pdf"); for(PolygonTree* pNode:vAllNodes) { vector<Segment2> vSegments; pNode->getSegments_regionOriented(vSegments); vis.addObject(vSegments,mNodeToColor[pNode]); } // Step 5: Visualize the PolygonTree structure itself, starting // from the root node. Point2 parentPosition(50,-50); vis.addObject(Label(parentPosition,"Root Node",true,15),Color(CBLACK)); showChildren_recursive(&vis,mNodeToColor,pRootNode,parentPosition); vis.writeFile(); }
In Step 1 we use the getNestedInput()
function to generate a nested polygon composed of multiple layers and components. In Step 2, we create a PolygonClipper
by passing the segments generated in the previous step, and retrieve the root node of the PolygonTree
, which represents the resulting polygon. During Step 3, we assign distinct colors for visualization purposes. Then, in Step 4 we visualize each layer of the polygon in its unique color, as shown in the following image.
In Step 5, we traverse the PolygonTree
hierarchically, starting from the root node. The root node has the layer number -1 and has no geometric counterpart. Its immediate child nodes, at layer 0, represent the components of the outermost hull of the polygon (2 components in the present example). The next layer of children, at layer 1, corresponds to the next polygon layer moving inward, and so forth. This step involves drawing the polygon layers as nodes of the PolygonTree
. We use the same colors assigned earlier to illustrate the relationship between the nodes of the PolygonTree
and the corresponding polygon layers. Compare the polygon image above with the following image of the PolygonTree
.
Traversing the PolygonTree Recursively
In Step 5, the showChildren_recursive()
function requires some explanation. It takes as arguments: a Visualizer2
object (the PDF writer), a map that stores colors for the visualization, the current parent node, and the geometric position of that parent node in the drawing. The function first retrieves the child nodes of the current parent node. For each child node, it draws a connection from the parent to the child, followed by rendering the polygon layer associated with that child node. Then, the function calls itself recursively, using the child node as the new parent.
void showChildren_recursive( Visualizer2* pVis, map<PolygonTree*,Color>& mNodeToColor, PolygonTree* pParent, Point2 parentPosition) { // Retrieve pParent's child-nodes vector<PolygonTree*>& vChildren(pParent->getChildren()); // For each child node for(size_t i=0;i<vChildren.size();++i) { PolygonTree* pChild(vChildren[i]); // Determine the child position and color (just visual details) Color childColor=mNodeToColor[pChild]; int childLayer(pChild->getLayer()); double xRange(100.0/(childLayer+1)); double childX(parentPosition.x()); if(vChildren.size()>1) { childX=childX-xRange/2+i*xRange/(vChildren.size()-1); } double childY(parentPosition.y()-25.0*(childLayer+1)); Point2 childPosition(childX,childY); // Draw a connection from the parent to the child node pVis->addObject(Segment2(parentPosition,childPosition),Color(CGRAY)); // Draw a label and the segments of the child node pVis->addObject(Label(childPosition,("Layer "+to_string(childLayer)).c_str()),childColor); vector<Segment2> vSeg; pChild->getSegments_regionOriented(vSeg); Vector2 moveVec(childPosition-getCenter(pChild)); for(Segment2& seg:vSeg) { pVis->addObject(Segment2(seg.getSrc()+moveVec,seg.getTrg()+moveVec),childColor); } // Call the function recursively using the child node as the new parent showChildren_recursive(pVis,mNodeToColor,pChild,childPosition); } }
This recursive function might seem complicated, but it is simply a classic depth-first traversal of a tree data structure, paired with visualization code to draw it.
Conclusion
In this article, we explored the PolygonClipper
tool, illustrating how to repair and reorient a possibly self-intersecting polygon. We demonstrated how to restrict a polygon to a defined region. Additionally, we examined the PolygonTree
structure, demonstrating how to traverse this hierarchical data structure – and thereby the polygon – layer by layer. This exploration highlighted the connections between the levels of the PolygonTree and their corresponding polygon layers, clarifying their relationships.