This example shows how you can enlarge a polygon by a certain distance. For example, you can use it to move the edges of the polygon outward by 10 pixels.

The program lets you use the mouse to define the polygon. Left-click to add points to the polygon. Right-click to finish the polygon. Then use the scroll bar at the bottom to determine by how much to enlarge the polygon. The original polygon appears in red and the enlarged polygon appears in green.

# The Idea

Before I describe the `EnlargedPolygon` method, which does most of the work, here’s the basic idea. Look at the polygon shown in Figure 1 and consider the corner at point pj. The goal is to find a new location for the point pj.

The first step is to create new “offset edges” parallel to the edges adjacent to point pj. The offset edges are shown in green in Figure 2.

To find a line parallel to the pi-pj edge, the program first finds vectors perpendicular to that edge. To do that, it finds the vector along the edge and switches its X and Y components. It then sets the result vector so it has the desired offset length (the amount we are enlarging the polygon) and adds it to the original points pi and pj to get the offset edge.

The program then repeats those steps for the pj-pk edge. The offset vectors are shown in blue in Figure 2.

Next the program extends the two offset edges into lines and calculates their point of intersection pj2, as shown in Figure 3. That point of intersection is the point in the new enlarged polygon that corresponds to the original point pj.

# The Code

The following code shows the `GetEnlargedPolygon` method. It takes as inputs a list of `PointF` that defines a polygon and returns a new list of `PointF` that define the enlarged polygon.

// Return points representing an enlarged polygon. private List<PointF> GetEnlargedPolygon( List<PointF> old_points, float offset) { List<PointF> enlarged_points = new List<PointF>(); int num_points = old_points.Count; for (int j = 0; j < num_points; j++) { // Find the new location for point j. // Find the points before and after j. int i = (j - 1); if (i < 0) i += num_points; int k = (j + 1) % num_points; // Move the points by the offset. Vector v1 = new Vector( old_points[j].X - old_points[i].X, old_points[j].Y - old_points[i].Y); v1.Normalize(); v1 *= offset; Vector n1 = new Vector(-v1.Y, v1.X); PointF pij1 = new PointF( (float)(old_points[i].X + n1.X), (float)(old_points[i].Y + n1.Y)); PointF pij2 = new PointF( (float)(old_points[j].X + n1.X), (float)(old_points[j].Y + n1.Y)); Vector v2 = new Vector( old_points[k].X - old_points[j].X, old_points[k].Y - old_points[j].Y); v2.Normalize(); v2 *= offset; Vector n2 = new Vector(-v2.Y, v2.X); PointF pjk1 = new PointF( (float)(old_points[j].X + n2.X), (float)(old_points[j].Y + n2.Y)); PointF pjk2 = new PointF( (float)(old_points[k].X + n2.X), (float)(old_points[k].Y + n2.Y)); // 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); Debug.Assert(lines_intersect, "Edges " + i + "-->" + j + " and " + j + "-->" + k + " are parallel"); enlarged_points.Add(poi); } return enlarged_points; }

The method creates the `enlarged_points` list and then loops through the polygon’s original points to create the new enlarged polygon’s points.

For each point (pj in the figures), the code finds the index of the points (pi and pk) before and after the point. It then needs to find the offset vectors (the blue arrows in the figures).

First it subtracts pj – pi to find the vector from point pi to point pj. It calls the vector’s `Normalize` method to give the vector length 1. It then multiplies the vector by the offset distance so the result has the desired length.

The method then sets the vector’s X and Y components to -Y and X respectively. That gives a vector with the same length but perpendicular to the original vector. The result is the desired offset vector `n1`.

Note that this step assumes the original polygon’s points are arranged counter-clockwise. If they are arranged clockwise, then this step gives a vector that points into the polygon instead of out of the polygon. The program uses the technique described in the post Determine whether a polygon is oriented clockwise or counterclockwise in C# to ensure that the polygon is properly oriented.

Next the method uses the offset vector `n1` to find the offset points `pij1` and `pij2`. The code then repeats those steps to find the other edges offset points `pjk1` and `pjk2`.

The code then uses the `FindIntersection` to see where the two offset edges intersect. See the post Determine where two lines intersect in C# to see how that method works.

The method adds the point of intersection to the output list of `PointF` and continues to the loop to consider the next point in the original polygon.

Take a few minutes to download the example and experiment with it. It’s interesting to see what happens if the polygon is concave or if you allow negative offsets.

Just wanted to thank you for this excellent method – it works perfectly. There is one issue I found though – it will fail for collinear segments. If you have a part of the polgyon made, for example, of three collinear points, then when you push the points out the line-intersection test will return the case stating that they are parallel lines (which the technically are) and thus will not return an intersection point.

I got around this by adding a special case in my line-intersection test stating that if we were parallel, and the end and beginning of the two line segments were identical, then return that point as the intersection.

Hi there! I’m having the same problem you describe when a polygon has multiple point on the same line.

I tried implementing your solution by your description but I’m not getting it to work. I know your comment is from some years ago, but by any chance, do you still have the solution to fix this problem?

Thanks you for your help!

Have a nice day.

Hey Karianne,

It’s been a few years but I managed to dig up my implementation of Rod’s algorithm, which includes the special case check for collinear points. I can’t be 100% sure it works in all cases, but I hope it’s helpful!

Thanks, Gelo!

Thank you so much Gelo for your quick reply!!! I was so excited the other day when I read your had replied :D!

By the time I had some free time to test it out, Rod Stephens also added his updated version of the solution. At the moment, I’m testing with his solution, but I’m very appreciative to have yours too!

See this example for an improved version:

Enlarge a polygon that has colinear vertices in C#

Hello,

It’s interesting that I use your code all the time! Here are the “howto_segment_intersection”, “howto_point_segment_distance” and “howto_enlarge_polygon” open in the taskbar.

I’m working on an automatic floor plan generator routine that will be part of a genetic algorithm.

I think if I get rich from that, a few hundred thousand dollars will be for you.

Many thanks,

Pal.

Pingback: Enlarge a polygon that has colinear vertices in C# - C# HelperC# Helper