Categories
2D Delaunay Triangulation Examples in C++

Offset Polygons in C++ (Example 13)

Creating an offset polygon without self-intersections is a surprisingly complex task. Therefore, Fade2D provides functions to compute positive or negative offsets for shapes, ensuring that the resulting offset contours are free from self-intersections. In this article, we will explain the source code from Example 13, located in the examples_2D/ex13_polygonOffset.cpp file in the Fade2D package, which demonstrates how to compute positive and negative polygon offsets.

Additionally, we will explore morphological operations such as morphological opening and closing, which are closely related to offset computations. These operations are used to remove small structures or bridge narrow gaps within a Zone2.

How to Compute an Offset Polygon?

To compute the positive or negative offset of a shape, we use the Zone2::getOffsetBoundary() method. This method takes four arguments:

double offsetThe positive or negative offset distance.
vector<Segment2>& vOffBoundaryA vector that stores the resulting segments in arbitrary order, with each segment’s direction oriented counterclockwise around the offset shape.
double mergeAngleDegIf the angle of a circular arc in the offset polygon is smaller than mergeAngleDeg degrees, then its two endpoints are merged, as shown in the two images below. This value must be greater than 0 and cannot exceed 135 degrees.
double angleStepDegSpecifies the angle step used to approximate circular arcs in the offset contour using line segments. Default: 20 degrees, max:135 degrees.
Arguments for the method Zone2::getOffsetBoundary()

The last two arguments require further explanation: Convex vertices of the original shape create circular arcs in the offset polygon, as shown in the image below. However, small arcs may not always be desirable, and the mergeAngleDeg parameter is a threshold: Circular arcs with an angle smaller than this value will have their endpoints merged to eliminate the arc.

Polygon with circular arcs that have not been merged.
Positive offset polygon with mergeAngleDeg=0.01: Convex vertices create circular arcs, and the small merge angle threshold prevents the arcs from disappearing.
Offset polygon: Polygon with arcs below 90 degrees merged into a single point.
Offset polygon with mergeAngleDeg=90.01: The algorithm has merged arcs with up to 90 degrees into single points.

The angleStepDeg parameter defines the angle increments at which a circular arc is approximated using line segments. See the two images below.

An arc, smoothly approximated by line segments, each segment limited to 5 degrees.
Approximation of an offset arc with line segments, constrained to a maximum of 5 degrees per segment
An arc approximated by line segments, each segment under 45 degrees.
Approximation of a circular offset arc using line segments, with each segment limited to at most 45 degrees

The method Zone2::getOffsetBoundary() was introduced in Fade2D, version 2.15. It replaces the older function offsetPolygonPoints(), which did not resolve self-intersections.


Step 1: Creating the Input Zone

Let’s start with the actual Example 13:

First, we need a shape, represented by a Zone2 object, which will serve as input for the offset operations. In this example, we create this original shape using the createInputZone() function, then visualize and save it as a PDF file. You can safely ignore the details of this function and create your own Zone2 instead. The article Polygons And Zones describes the various ways to create zones.

// * Step 1 *   Create an input zone for this example
Fade_2D dt;
Zone2* pInputZone=createInputZone(dt); // Creates some input shape
if(pInputZone==NULL)
{
	cout<<"Empty input zone, returning"<<endl;
	return 1;
}
pInputZone->show("ex13_inputZone.pdf",false,false); // Visualize and save the input shape as .pdf file
Input shape for offset calculation
Input shape for offset calculation (stored in pInputZone)

Step 2: Computing the Positive Offset Polygon

Now we specify the parameters explained above, and use them to call Zone2::getOffsetBoundary(). We then visualize the result as a PDF file.

// * Step 2 *   Compute the positive offset boundary
vector<Segment2> vPosOffBoundary; // Will contain the positive offset boundary
const double OFFSET(3.0); // Positive offset distance
const double MERGE_ANGLE_DEG(3.0);  // Merge two offset points of a vertex if the angle is small enough
const double ANGLE_STEP_DEG(15.0); // Approximate circular arcs using this angle step
pInputZone->getOffsetBoundary(OFFSET,vPosOffBoundary,MERGE_ANGLE_DEG,ANGLE_STEP_DEG);
Visualizer2 visPosOffBoundary("ex13_posOffBoundary.pdf"); // Visualize the positive offset boundary
visPosOffBoundary.addObject(vPosOffBoundary,Color(CRED));
visPosOffBoundary.writeFile();
Positive offset boundary of a polygon shape
Positive Offset Boundary: Self-intersections are automatically resolved

Step 3: Creating the Positive Offset Shape

In the previous step, we computed the offset segments. We now create a ConstraintGraph2 and a Zone2 representing the area inside the offset polygon, and then we visualize and save the positive offset shape as a PDF file.

Technical details: While the order of the segments from the previous step is arbitrary, their orientation is not: Each segment’s direction is counterclockwise (CCW) around the offset shape. This CCW orientation is crucial because it allows us to distinguish the interior from the exterior area of the polygon. Given this property, we can call Fade_2D::createConstraint() with bOrientedSegments=true, informing the resulting ConstraintGraph2 that it deals with oriented segments.

// * Step 3 *   Create the positive offset shape
ConstraintGraph2* pPosCG(dt.createConstraint(vPosOffBoundary,CIS_CONSTRAINED_DELAUNAY,true)); // true: oriented segments!
Zone2* pPosOffShape(dt.createZone(pPosCG,ZL_INSIDE));
pPosOffShape->show("ex13_posOffShape.pdf",false,false); // Visualize the positive offset shape
Positive offset shape created from a polygon using Fade2D.
Positive Offset Shape

Step 4: Computing the Positive Offset Delta

There might be a scenario where you need the delta, i.e., the area that has been added by the offset operation. This area is just the difference between the positive offset shape and the original shape, and computing it is straightforward:

Zone2* pPosDelta(zoneDifference(pPosOffShape,pInputZone));
pPosDelta->show("ex13_posDelta.pdf",false,false); // Visualize the positive offset delta
Positive Delta showing the difference between the positive offset shape and the original shape
Positive Delta: Difference Between Offset and Original Shape

Step 5: Computing a Negative Offset Polygon

When you choose to compute a negative offset, the procedure is similar, and you can use the same parameters as before, but with a negative offset value. Be aware that in case of negative offsets the result might be empty, so ensure you check for this condition before proceeding.

// * Step 5 *   Compute the negative offset boundary
vector<Segment2> vNegOffBoundary;
const double NEG_OFFSET(-1.0); // Negative offset distance
pInputZone->getOffsetBoundary(NEG_OFFSET,vNegOffBoundary,MERGE_ANGLE_DEG,ANGLE_STEP_DEG);
// Ensure that a negative offset boundary exists before proceeding!
if(vNegOffBoundary.empty())
{
	cout<<"Empty offset shape, no negative offset boundary!"<<endl;
	return 0;
}
Visualizer2 visNeg("ex13_negOffBoundary.pdf");
visNeg.addObject(vNegOffBoundary,Color(CGREEN));
visNeg.writeFile();
Negative offset boundary of a polygon shape
Negative Offset Boundary: Observe how the tilde-shaped object at the bottom of the original shape has disappeared due to the large negative offset.

Step 6: Computing the Negative Offset Shape

We once again take advantage of the fact that segments returned by Zone2::getOffsetBoundary() are oriented counterclockwise (CCW) around the offset-shape. This CCW orientation allows us to call Fade_2D::createConstraint() with bOrientedSegments=true. We then create a Zone2 inside this boundary, representing the remaining area after applying the negative offset.

// * Step 6 *   Compute the negative offset shape
ConstraintGraph2* pNegCG(dt.createConstraint(vNegOffBoundary,CIS_CONSTRAINED_DELAUNAY,true)); // true: oriented segments!
Zone2* pNegOffShape(dt.createZone(pNegCG,ZL_INSIDE));
pNegOffShape->show("ex13_negOffShape.pdf",false,false);
Negative offset shape created from a polygon using Fade2D.
Negative Offset Shape.

Step 7: The Negative Delta

The negative delta is the area removed by the negative offset operation. We compute it by subtracting the negative offset shape from the original shape.

// * Step 7 *   Compute the negative delta, i.e., the area removed by the offset operation
Zone2* pNegOffStrip(zoneDifference(pInputZone,pNegOffShape));
pNegOffStrip->show("ex13_negOffDelta.pdf",false,false);
Negative Delta showing the difference between the original shape and the negative offset shape
Negative Delta: Difference Between Original and Offset Shape

Morphological Opening and Closing in C++

You might want to remove small structures in a Zone2 or bridge narrow gaps between components. While simple offset operations could achieve these goals, they aren’t ideal because they change the size of the remaining components. The right tool for these tasks is the use of morphological opening and morphological closing, techniques commonly used in image processing.

Morphological opening involves first eroding a shape using a structural element and then dilating this intermediate result with the same element. This operation removes small details. In contrast, morphological closing first dilates a shape and then erodes it, effectively bridging small gaps between components.

Fade2D simulates dilation and erosion using positive and negative offsets of a shape, i.e., the structural element is always a disk. To avoid circular arcs in the result, a large enough value for the parameter mergeAngleDeg, such as 91 degrees, can be chosen. This way, the result closely resembles classic morphological opening and closing operations.

Example 13, Step 8 and 9, demonstrate how to use Fade2D’s morphological opening and closing in C++:

// * Step 8 *   Create a zone with random rectangles
Fade_2D dtOrg,dtOpen,dtClose;
double mergeAngle(95.0);
double angleStep(10.0);
Zone2* pRectangleZone=createRectangleZone(dtOpen,50);
pRectangleZone->show("ex13_rectangles.pdf",false,false);

// * Step 9 *   Open and close the zone
Zone2* pOpenZone=pRectangleZone->morphOpen(&dtOpen,5,mergeAngle,angleStep);
if(pOpenZone!=NULL)
{
	// Opening has not created an empty zone, show!
	pOpenZone->show("ex13_open.pdf", false, false);
}
Zone2* pCloseZone=pRectangleZone->morphClose(&dtClose,5,mergeAngle,angleStep);
pCloseZone->show("ex13_close.pdf",false,false);

In the code snippet above, Step 8 creates a Zone2, consisting of random rectangles. In Step 9, the calls to morphOpen() and morphClose() return the results for morphological opening and closing as Zone2 objects, created in new Fade_2D instances. The result of the morphological opening operation may be empty, and in this case, morphOpen() would return NULL. This case is checked in Step 9 before proceeding. See the results in the 3 images below.

50 random rectangles
50 random rectangles, used as input for the morphological operations
Morphological Opening: Small details have been removed.
Morphological opening has removed small details
Morphological Closing: Small gaps between rectangles have been filled.
Morphological closing has filled small gaps between the rectangles.

Leave a Reply

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