Enlarge a polygon in C#

[polygon]

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



[polygon]
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.



[polygon]
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.



[polygon]
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.


Download Example   Follow me on Twitter   RSS feed   Donate




About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, drawing, graphics, mathematics and tagged , , , , , , , , , , , , , . Bookmark the permalink.

One Response to Enlarge a polygon in C#

  1. Gelo says:

    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.

Leave a Reply

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