Categories
2D Delaunay Triangulation Examples in C++

Polygon Clipper – Repairing Polygons, Example 14

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:

  1. 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.
  2. Precision Loss: Saving 64-bit coordinates to 32-bit formats cuts precision, possibly introducing self-intersections.
  3. 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.
  4. 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…

Counterclockwise (CCW) oriented polygon. The area is on the left side of each edge.
With counterclockwise (CCW) edge orientation, the polygon’s area consistently lies to the left of each edge.

However, this property does not hold for self-intersecting polygons, like the one shown at the top of the image below.

Top: Polygon with a self-intersection; Bottom: Same polygon repaired to ensure proper orientation.
At the top: A polygon with a self-intersection, resulting in a small loop with incorrect edge orientations. Below: The repaired version of the polygon with correct orientations, clearly defining the inside and outside.

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.

A corrupt input polygon consisting of two separate connected components. The polygon is not correctly oriented and exhibits self-intersections.
A corrupt input polygon: Its edges lack correct orientation, and self-intersections are present.

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.

Repaired polygon with only the outer hull visible, inner parts removed.
Repaired polygon: Only the outer hull remains, with no inner parts.

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.

Repaired polygon with inner components.
Repaired polygon: It consists of both inner segments and the outer hull. Some vertices are shown with two labels to indicate the order in which the polygon traverses them.

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();
Polygon Clipping: A polygon restricted to a defined region
Polygon Clipping: The input polygon is restricted to a defined region.

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.

Nested polygon with multiple layers and components, displayed in different colors and levels.
Hierarchically nested polygon with colored layers illustrating the relationship between the layers and the nodes of the PolygonTree.

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.

PolygonTree representing the layers of a polygon hierarchically, colored to illustrate the relationship between the nodes and the polygon layers
PolygonTree representing the layers of a polygon hierarchically, colored to illustrate the relationship between the nodes and the polygon layers

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.

Leave a Reply

Your email address will not be published. Required fields are marked *