Click here to Skip to main content
15,867,686 members
Articles / Programming Languages / C#

A brute-force approach to check if a line segment crosses a simple polygon

Rate me:
Please Sign up or sign in to vote.
4.79/5 (5 votes)
28 Apr 2012CPOL4 min read 53.9K   1K   18   8
Split a segment into smaller parts in order to check if the segment crosses a polygon or not.

Check a big segment by checking one of its small part

Introduction 

Checking if a line segment really crosses or is inside a polygon is always a hard geometric problem for programmers to solve. We can hardly find a general algorithm for line segment-polygon intersection checking. My article is to suggest an idea for testing whether a line segment crosses a polygon or not, it can be applied for only simple computer graphics polygons (including convex and concave ones).

Background

Conventions

The pseudo-code I am using in this article is a Java-like language. It is a mixture between structural programming and object oriented programming. Suppose that point, line segments (from now on I will use 'segment'), and polygons are implemented with basic methods such as segment-segment intersection, segment containing a point, polygon containing a point, length of a segment, midpoint…

Acknowledgements

A segment crosses a polygon if one of its parts crosses that polygon. A segment crosses a polygon if it cuts or is inside that polygon. A segment cuts a polygon if it has at least one intersection that is not the end point of the segment. A segment is inside a polygon if every point of the segment is inside the polygon (end points of the segment can lay on the boundary of the polygon). These edges of a polygon are not inside this polygon.

Figure 1 - Segments cross polygon

Figure 2 - Segments do not cross polygon

New Solution

Idea

Directly from the acknowledgements, we have these clauses:

  • A segment crosses a polygon if it cuts or is inside that polygon.
  • A segment is inside a polygon if every point of the segment is inside the polygon.

The conclusion is: if a part of the segment is inside the polygon, the segment crosses the polygon. So, our work is to split the original segment into smaller parts in order to check if there is a part that is inside the polygon.

Which kind of segment can be inside a polygon?

If a segment is totally inside or outside a polygon, then it has no intersection with the edges of the polygon (end points of the segment can lay on the boundary of the polygon). We can determine only that kind of segment is inside/outside a polygon.

Figure 3 - Segments that do not intersect edges of polygon

How to split a segment?

With each segment, we try to find its intersection with an edge of the checking polygon. If the intersection exists and is not an end point of this segment, split the segment into two small parts, one is from Begin to the intersection, another from the intersection to the End (Begin and End the end points of the segment). Do these steps recursively until the segment has no intersection with the edges of the polygon.

Figure 4 - How we split a segment into parts

Figure 4 is a good example: Segment MN intersects edge AB and O is the intersection. We split MN into MO and ON.

Check if a part is inside a polygon

The segment s, that we are checking, is a small part of a big segment. The condition is "segment s and polygon p have no intersection" (it is OK if end points of segment s lay on the boundary of the polygon p). 

If the part is an edge of the polygon, it is not inside. Otherwise, every point of the part is on the same side (end points can lay on the boundary of the polygon). We can pick up an arbitrary point (I chose midpoint), the whole part will be on the same side to this point. Pseudo-code:

C#
public boolean Cover(Polygon p, Segment s)
{
    // if segment is a edge of this polygon
    for (int i=0; i< p.Edges.count; i++)
        if (s == p.Edges[i])
            return false;
    // segment cannot be spitted
    // so, if the midpoint is inside polygon, whole segment will inside
    Point mid = s.MidPoint();
    if (p.Contains(mid))
        return true;
    else
        return false;
}

Check if a segment crosses a polygon

Step 1: Try to split the segment into two parts. If it is possible, go to step 2, otherwise go to step 4.

Step 2: Recursively check if the first part crosses the polygon. If it does not, go to step 3, otherwise the segment crosses the polygon. Stop the algorithm.

Step 3: Recursively check if the second part crosses the polygon. If it does not, the segment does not cross the polygon, otherwise the segment crosses the polygon. Stop the algorithm.

Step 4: Check if the segment is inside the polygon. If it is inside, the segment crosses the polygon, otherwise it does not. Stop the algorithm.

Pseudo-code:

C#
public boolean Cross(Segment s, Polygon p) {
    // split the big segment into parts
    Point split_point = null;
    for (int i=0; i< p.Edges.count; i++)
    {
        Segment edge = p.Edges[i];
        // find intersection that is not end point of segment
        split_point = s.InterSectionExceptThisEnds(edge);
        if (split_point != null)
            break;
    }
    // if we can split
    if (split_point != null) // then check each part
    {
        boolean first_part = Cross(new Segment(s.p1,split_point), p);
        // a part intersects means whole segment intersects
        if (first_part == true)
            return first_part;
        // if first part doesn't intersect, it depends on second one
        boolean second_part = Cross(new Segment(split_point,s.p2), p);
        return second_part;
    } 
    // cannot split this segment
    else
    {
        boolean result = Cover (p, s);
        return result;
    }
}

Back to Figure 4 for an example. Let’s do it step by step.

Figure 5 - How we determine that segment MN crosses the polygon

  1. First, we split MN into MO and ON.
  2. Then we check MO. MO cannot be split and it is outside the polygon.
  3. So we have to check ON.
  4. ON can be split into OP and PN.
  5. OP cannot be split and it is inside the polygon.
  6. OP is a part of ON, so ON is crossing the polygon.
  7. ON is the second part of MN, then we determine that MN crosses the polygon.

Conclusion

This algorithm can check if a segment crosses a polygon, and the programmer can modify it to determine that the segment is inside or cuts the polygon and gets the intersections if they exist. Do not apply this to a complex polygon (a polygon that intersects itself or has holes in it). But programmers can separate a self-intersecting polygon into some simple polygons and determine holes as polygons, then apply and modify this algorithm for their own purposes. I used to spend a lot of time searching for a geometric algorithm on the internet, which is time-consuming, so I am sharing my experience and hoping that it is helpful. I am waiting for positive comments to make the article better. Have fun. 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Vietnam Vietnam
Oops!

Comments and Discussions

 
GeneralMy vote of 5 Pin
Southmountain3-Sep-13 11:13
Southmountain3-Sep-13 11:13 
QuestionThere are much more robust ways of doing this Pin
leon de boer2-Dec-12 22:53
leon de boer2-Dec-12 22:53 
QuestionIntersection with polygon corners Pin
coldfirero11-Jun-12 23:02
coldfirero11-Jun-12 23:02 
Questionwhat motivated you to write this? Pin
John Orendt31-May-12 17:42
John Orendt31-May-12 17:42 
QuestionA possible algorithm. Pin
Member 419459328-Apr-12 11:23
Member 419459328-Apr-12 11:23 
QuestionYour first pseudo code is only true for convex polygons Pin
Andreas Gieriet26-Apr-12 22:20
professionalAndreas Gieriet26-Apr-12 22:20 
AnswerRe: Your first pseudo code is only true for convex polygons Pin
Duc Huy Nguyen26-Apr-12 23:45
Duc Huy Nguyen26-Apr-12 23:45 
BugA little bit mistake at the second pseudo-code :) Pin
Duc Huy Nguyen24-Apr-12 1:21
Duc Huy Nguyen24-Apr-12 1:21 
Wrong version is :

Java
public boolean Cross(Segment s, Polygon p) {
    // split the big segment into parts
    Point split_point = null;
    for (int i=0; i< p.Edges.count; i++)
    {
        Segment edge = p.Edges[i];
        // find intersection that is not end point of segment
        split_point = s.InterSectionExceptThisEnds(edge);
        if (split_point != null)
            break;
    }
    // if we can split
    if (split_point != null) // then check each part
    {
        boolean first_part = Intersect(new Segment(s.p1,split_point), p);
        // a part intersects means whole segment intersects
        if (first_part == true)
            return first_part;
        // if first part doesn't intersect, it depends on second one
        boolean second_part = Intersect(new Segment(split_point,s.p2), p);
        return second_part;
    } 
    // cannot split this segment
    else
    {
        boolean result = Cover (p, s);
        return result;
    }
}


Right version is:

Java
public boolean Cross(Segment s, Polygon p) {
    // split the big segment into parts
    Point split_point = null;
    for (int i=0; i< p.Edges.count; i++)
    {
        Segment edge = p.Edges[i];
        // find intersection that is not end point of segment
        split_point = s.InterSectionExceptThisEnds(edge);
        if (split_point != null)
            break;
    }
    // if we can split
    if (split_point != null) // then check each part
    {
        boolean first_part = Cross(new Segment(s.p1,split_point), p);
        // a part intersects means whole segment intersects
        if (first_part == true)
            return first_part;
        // if first part doesn't intersect, it depends on second one
        boolean second_part = Cross(new Segment(split_point,s.p2), p);
        return second_part;
    } 
    // cannot split this segment
    else
    {
        boolean result = Cover (p, s);
        return result;
    }
}

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.