Offset Polygons in C++ (Example 13)

Creating an offset polygon without self-intersections is an important but surprisingly complex task. To provide a solution, Fade2D includes functionality to compute positive or negative offsets for shapes, ensuring that the resulting offset contours are always free from self-intersections. Example 13, located in examples_2D/ex13_polygonOffset.cpp in the downloadable Fade2D package, shows how to compute both positive and negative polygon offsets.

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:

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, these arcs may not always be desirable. The mergeAngleDeg parameter allows us to specify a threshold angle. Circular arcs with an angle smaller than this value will have their endpoints merged to eliminate the arc.

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

The method Zone2::getOffsetBoundary() was introduced in Fade2D, version 2.15. It replaces the old 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 an input shape, represented by a Zone2 object, which will serve as the original shape for the offset operations. In this example, we create it using the createInputZone() function and 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

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();

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, 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

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

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();

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);

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);