11,584,208 members (50,855 online)

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

, 28 Apr 2012 CPOL 18.4K 398 14
 Rate this:
Split a segment into smaller parts in order to check if the segment crosses a polygon or not.

## 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.

## 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.

#### 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 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.

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.

## Share

 Vietnam
Oops!

## You may also be interested in...

 First Prev Next
 My vote of 5 Southmountain3-Sep-13 11:13 Southmountain 3-Sep-13 11:13
 There are much more robust ways of doing this leon de boer2-Dec-12 22:53 leon de boer 2-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.
 Intersection with polygon corners coldfirero11-Jun-12 23:02 coldfirero 11-Jun-12 23:02
 what motivated you to write this? John Orendt31-May-12 17:42 John Orendt 31-May-12 17:42
 A possible algorithm. Member 419459328-Apr-12 11:23 Member 4194593 28-Apr-12 11:23
 Your first pseudo code is only true for convex polygons Andreas Gieriet26-Apr-12 22:20 Andreas Gieriet 26-Apr-12 22:20
 Re: Your first pseudo code is only true for convex polygons Duc Huy Nguyen26-Apr-12 23:45 Duc Huy Nguyen 26-Apr-12 23:45
 A little bit mistake at the second pseudo-code :) Duc Huy Nguyen24-Apr-12 1:21 Duc Huy Nguyen 24-Apr-12 1:21
 Last Visit: 31-Dec-99 18:00     Last Update: 7-Jul-15 10:16 Refresh 1