Click here to Skip to main content
Click here to Skip to main content
Go to top

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

, 28 Apr 2012
Rate this:
Please Sign up or sign in to vote.
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:

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:

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)

Share

About the Author

Duc Huy Nguyen

Vietnam Vietnam
Oops!

Comments and Discussions

 
GeneralMy vote of 5 PinmemberSouthmountain3-Sep-13 11:13 
QuestionThere are much more robust ways of doing this Pinmemberleon de boer2-Dec-12 22:53 
Okay first general comments create a structure, record of object that contains the min,max co-ordinates as a 2D or 3D square depending on if you are working in 2D or 3D.
 
By having the 4 min,max for 2D or 6 min max of 3D you have simple trivial rejections of PolygonA and PolygonB
 
if PolygonB xmax < PolygonA xmin then PolygonB is completely left of PolygonA so reject it
if PolygonB xmin > PolygonA xmax then PolygonB is completely right of PolygonA so reject it
if PolygonB ymax < PolygonA ymin then PolygonB is completely above PolygonA so reject it
if PolygonB ymin > PolygonA ymax then PolygonB is completely below PolygonA so reject it
 
For 3D you can also do trivial rejections in the Z plane
 
if PolygonB zmax < PolygonA zmin then PolygonB is completely above PolygonA depth so reject it
if PolygonB zmin > PolygonA zmax then PolygonB is completely below PolygonA depth so reject it
 
You have now eliminated all the trivial answers so the two polygon containment squares now overlap and the only robust way to test both convex, concave and self overlapping polygons is to to a scanline conversion over the range of the smaller of the two polygons.
 
If you do alot of reading you will find various tests most of them are listed in "graphics gems 4" ( for ref http://erich.realtimerendering.com/ptinpoly/ )
 
The key point is scanline conversion is as fast as any other on around 9 point or more polygons and is the only one guaranteed robust. You also get a number of bonuses by setting up the scanline procedures you can fill any arbritary polygon using the procedure, you can check if a point is within a polygon by simply checking that the given point is within one of the scan line segements and finally you can check if the two polygons are within each other because every scanline of the smaller polygon should be within a scanline of the larger polygon if that is not the case then the smaller polygon is not within the larger one and is outside it or overlapping it.
QuestionIntersection with polygon corners Pinmembercoldfirero11-Jun-12 23:02 
Questionwhat motivated you to write this? PinmemberJohn Orendt31-May-12 17:42 
QuestionA possible algorithm. PinmemberMember 419459328-Apr-12 11:23 
QuestionYour first pseudo code is only true for convex polygons PinmemberAndreas Gieriet26-Apr-12 22:20 
AnswerRe: Your first pseudo code is only true for convex polygons PinmemberDuc Huy Nguyen26-Apr-12 23:45 
BugA little bit mistake at the second pseudo-code :) PinmemberDuc Huy Nguyen24-Apr-12 1:21 

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

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

| Advertise | Privacy | Mobile
Web04 | 2.8.140926.1 | Last Updated 28 Apr 2012
Article Copyright 2012 by Duc Huy Nguyen
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid