Clip a line segment to a polygon in C#

[polygon]

This example finds the pieces of a line segment that lie inside and outside of a polygon. It draws the parts of the segment that lie outside of the polygon with a pink background and it draws parts of the segment within the polygon in yellow.

The basic idea is to find all of the points of intersection between the line segment and the polygon’s edges. The FindIntersection method used by the example calculates a value t between 0.0 and 1.0 that indicates the position of the point of intersection along line segment. The value 0.0 means the intersection is at the segment’s first end point, 1.0 means the intersection is at the segment’s second end point, and values between 0.0 and 1.0 mean the intersection is in between.

After calculating the points of intersection between the segment and the polygon’s edges, the program sorts those intersections by their t values. The sorted points of intersection are places where the segment alternately enters and leaves the polygon.

The following code shows the ClipLineWithPolygon method that finds the points of intersection.

// Return points where the segment enters and leaves the polygon.
private PointF[] ClipLineWithPolygon(
    out bool starts_outside_polygon,
    PointF point1, PointF point2,
    List<PointF> polygon_points)
{
    // Make lists to hold points of
    // intersection and their t values.
    List<PointF> intersections = new List<PointF>();
    List<float> t_values = new List<float>();

    // Add the segment's starting point.
    intersections.Add(point1);
    t_values.Add(0f);
    starts_outside_polygon =
        !PointIsInPolygon(point1.X, point1.Y,
            polygon_points.ToArray());

    // Examine the polygon's edges.
    for (int i1 = 0; i1 < polygon_points.Count; i1++)
    {
        // Get the end points for this edge.
        int i2 = (i1 + 1) % polygon_points.Count;

        // See where the edge intersects the segment.
        bool lines_intersect, segments_intersect;
        PointF intersection, close_p1, close_p2;
        float t1, t2;
        FindIntersection(point1, point2,
            polygon_points[i1], polygon_points[i2],
            out lines_intersect, out segments_intersect,
            out intersection, out close_p1, out close_p2,
            out t1, out t2);

        // See if the segment intersects the edge.
        if (segments_intersect)
        {
            // See if we need to record this intersection.

            // Record this intersection.
            intersections.Add(intersection);
            t_values.Add(t1);
        }
    }

    // Add the segment's ending point.
    intersections.Add(point2);
    t_values.Add(1f);

    // Sort the points of intersection by t value.
    PointF[] intersections_array = intersections.ToArray();
    float[] t_array = t_values.ToArray();
    Array.Sort(t_array, intersections_array);

    // Return the intersections.
    return intersections_array;
}

This method is reasonably self-explanatory.

For information on the PointIsInPolygon method, see the post Determine whether a point is inside a polygon in C#.

For information on the FindIntersection method, see the post Determine where two lines intersect in C#.

Note that I haven’t tested this example on special cases such as the segment passing through a polygon vertex, the segment starting or ending exactly on a polygon edge, or the segment coinciding with part of a polygon edge.


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.

Leave a Reply

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