Title: Enlarge a polygon that has colinear vertices in C#

The example Enlarge a polygon in C# shows how you can expand a polygon. The basic idea is to offset each of the polygon's edges away from the polygon's center and then see where adjacent edges intersect as shown in the picture below.

Unfortunately that method has problems if the polygon has three colinear adjacent vertices. In the picture, that happens if pi -> pj and pj -> pk are parallel. In that case the two edges are parallel so the program fails when it tries to find the point where they intersect. Sometimes rounding errors allow the program to find an intersection and this succeeds, but sometimes the code places the point of intersection at infinity and you get a result like the one in the following picture.

To fix this problem, this version of the program makes a couple of changes.

First, when it draws the polygon and the expanded polygon, it draws the polygons' vertices so you can see if three adjacent vertices are colinear. For example, in the picture at the top of the post, the polygon's top is made up of two colinear edges. The expanded polygon's top is made up of a single edge.

Drawing the points helps you visualize the situation, but it doesn't solve the problem. The main changes to the program that address the actual problem are in the FindIntersection and GetEnlargedPolygon methods.

FindIntersection

The FindIntersection method determines where two adjacent offset edges intersect. See the post Determine where two lines intersect in C# for information about the basic method.

This example modifies the FindIntersection method to more accurately determine whether the two segments are parallel. The following snippet shows the key piece of code with the modified code highlighted in blue.

// Solve for t1 and t2 float denominator = (dy12 * dx34 - dx12 * dy34); bool lines_parallel = (Math.Abs(denominator) < 0.001); float t1 = ((p1.X - p3.X) * dy34 + (p3.Y - p1.Y) * dx34) / denominator; if (float.IsNaN(t1) || float.IsInfinity(t1)) lines_parallel = true; if (lines_parallel) { // The lines are parallel (or close enough to it). lines_intersect = false; segments_intersect = false; intersection = new PointF(float.NaN, float.NaN); close_p1 = new PointF(float.NaN, float.NaN); close_p2 = new PointF(float.NaN, float.NaN); return; }

The code calculates a denominator that it will soon use to calculate the value t1, which determines where the two segments intersect. If denominator is close to zero, then the lines are close to parallel, so the code sets lines_parallel to true if denominator is within 0.001 of 0.

If you skip this test (or if you make 0.001 much smaller), then rounding errors sometimes make the lines appear slightly non-parallel and the program can find a point of intersection for them. In that case the expanded polygon gets an extra point that probably lies along the common edge, and that probably doesn't hurt anything. The test shown here lets the program omit those unnecessary points and that makes the result cleaner.

Next the code calculates the value t1. If that value is not a number (NaN) or infinite, the code sets lines_parallel to true.

After those calculations, if lines_parallel is true, then the method sets its return parameters to indicate that the lines do not intersect and returns.

GetEnlargedPolygon

The following code shows where the GetEnlargedPolygon method calls FindIntersection with the changes highlighted in blue.

// See where the shifted lines ij and jk intersect. bool lines_intersect, segments_intersect; PointF poi, close1, close2; FindIntersection(pij1, pij2, pjk1, pjk2, out lines_intersect, out segments_intersect, out poi, out close1, out close2); if (lines_intersect) enlarged_points.Add(poi);

The only difference between this code and the previous version is that this code checks the lines_intersect value that is returned by the FindIntersection method. If the adjacent edges intersect (they are not parallel), then the code adds the point of intersection to the expanded polygon's vertex list. If the edges are parallel, then the code does not add that point (which is probably undefined anyway) to the list.

If you comment out that if test, you'll see the original problem occur for the example's test polygons.

Conclusion

This method is still not perfect. If you expand some polygons enough, the expanded version may intersect itself and that may not be what you want. You can probably clean that up with some post-processing, although it may not be trivial.

You can also avoid this whole issue if you don't allow adjacent colinear points. Before you start, you can loop through the polygon's vertices and remove any vertex that lies along the line between its two neighboring vertices.

Download the example to experiment with it and to see additional details.