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.