[C# Helper]
Index Books FAQ Contact About Rod
[Essential Algorithms, Second Edition]

[The Modern C# Challenge]

[WPF 3d, Three-Dimensional Graphics with WPF and C#]

[The C# Helper Top 100]

[Interview Puzzles Dissected]

[C# 24-Hour Trainer]

[Beginning Software Engineering]

[C# 5.0 Programmer's Reference]

[MCSD Certification Toolkit (Exam 70-483): Programming in C#]

Title: Enlarge a polygon in C#

[Enlarge a polygon in C#]

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 how much to enlarge the polygon. The original polygon appears in red and the enlarged polygon appears in green.

The Idea

[Enlarge a polygon in C#]
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.

[Enlarge a polygon in C#]
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.

[Enlarge a polygon in C#]

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 defines 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 the loop to consider the next point in the original polygon.

(It's interesting to see what happens if the polygon is concave or if you allow negative offsets.)

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

© 2009-2022 Rocky Mountain Computer Consulting, Inc. All rights reserved.