# How to check if a line segment intersects with a polygon?

The naive method is to bisect the line segment iteratively as asked here, and then check the bisection points using How to check if a 2D point is in a polygon?.

Would there be an other way?

I'm using v9.

For example,

list = {{4.4, 14}, {6.7, 15.25}, {6.9, 12.8}, {9.5, 14.9}, {13.2,
11.9}, {10.3, 12.3}, {6.8, 9.5}, {13.3, 7.7}, {0.6, 1.1}, {1.3,
2.4}, {2.45, 4.7}};
Graphics[{Red, Line[{{0, 10}, {20, 0}}], Black, Polygon[list]}]


• @Öskå Thanks. I'm working with v9, but I will check v10. Nov 20, 2014 at 14:37
• Why do you need to bisect? (1) Check if an endpoint is inside. If not, then (2) Check if the segment intersects a segment bounding the polygon. Nov 20, 2014 at 14:49
• In V10 Solve with geometric regions is very comfortable, if a bit slow... Nov 20, 2014 at 14:51
• @Daniel Lichtblau, unfortunately that fails if the polygon is nonconvex. Nov 20, 2014 at 15:07
• relevant : mathematica.stackexchange.com/questions/51391/…. Note for non-convex polygons the point-inside test is only useful if you find one end in and one out. Nov 20, 2014 at 17:48

As you are using v9, I would suggest using the undocumented function - GraphicsMeshIntersectQ which does exactly what you want:

plist = {Line[{{20, 10}, {20, 0}}], Polygon[list]};
GraphicsMeshIntersectQ[plist]
(* False *)


which is also in v10.

• @ rcollyer, your method is about 60 times faster than using RegionIntersection in V10 Nov 21, 2014 at 2:57
• RegionIntersection returns a region, while GraphicsMeshIntersectQ just tests whether they intersect or not. In many ways, the former is a more involved process, so I expect it to be slower. Nov 21, 2014 at 3:14
• @ rcollyer, for the case of contact, they give different answers. e.g. Line[{{9.10, 11.34}, {14, 9}}] (contacts with the polygon)RegionIntersection gives True, while GraphicsMeshIntersectQ gives False. How to include the contact case into the intersect? When the line lies completely inside in the polygon they also give different answers. Nov 21, 2014 at 6:53

In v10 this is a one-liner:

RegionDimension@RegionIntersection[Line[{{0, 10}, {20, 0}}], Polygon[list]]] > -∞


because an empty region has dimension $-\infty$. I do wish there was a NonemptyQ predicate one could use directly, though.

A "solution" using v10 would be: RegionQ@DiscretizeRegion@RegionIntersection[r1, r2].

For example:

r1 = Line[{{0, 10}, {20, 0}}];
r2 = Polygon[{{4.4, 14}, {6.7, 15.25}, {6.9, 12.8}, {9.5, 14.9}, {13.2, 11.9},
{10.3, 12.3}, {6.8, 9.5}, {13.3, 7.7}, {0.6,1.1}, {1.3, 2.4}, {2.45, 4.7}}];
g = Show[Graphics[{r1, r2}]];
ri = DiscretizeRegion@RegionIntersection[r1, r2];
RegionQ@ri

True


With r1 = Line[{{0, 10}, {-20, 0}}]; one will have False.

Showing the intersection if it exists:

If[RegionQ@ri,
Show[
DiscretizeRegion /@ {r1, r2},
HighlightMesh[DiscretizeRegion[ri], Style[#, Red] & /@ {0, 1}]],
g]


will give the following figures for {20, 0} and {-20, 0}:

With r1 = Line[{{10, 10}, {12, 10}}]:

False


Side note (aka bug?):

RegionQ[DiscretizeRegion@ RegionIntersection[#, r2]] & /@
{Line[{{5, 10}, {12, 10}}], Line[{{5, 10.1}, {12, 10}}]}


DiscretizeRegion::drf: DiscretizeRegion was unable to discretize the region RegionIntersection[<<2>>]. >>

{False, True}


While it does intersect with Line[{{5, 10}, {12, 10}}]:

• Strange, I get True for all cases, even the ones that don't intersect. Which makes sense to me: an empty region is still a region, just like an empty set/list/graph is still a set/list/graph. (v10.0.1 on Mac, by the way)
– user484
Nov 20, 2014 at 16:22
• @Rahul Even for r1 = Line[{{10, 10}, {12, 10}}]? I'm on Linux 10.0.1.
– Öskå
Nov 20, 2014 at 16:55
• Wait, no, now everything is working as expected. And I was sure I restarted the kernel and checked, too... Maybe I made a mistake somewhere. Sorry for the confusion.
– user484
Nov 20, 2014 at 17:01
• @Rahul The last example doesn't give you {False, True}?
– Öskå
Nov 20, 2014 at 17:03
• Oh, yes it does. By "as expected" I meant "as in your answer". Yes, it does look like a bug. RegionDimension correctly returns 1, though.
– user484
Nov 20, 2014 at 17:07

Another partial (see caveat) V10-based answer using Solve. The nice feature here is that exact solutions are returned (provided the input is exact, too). Caveat: Will only return intersection points on the border of the polygon. Plus, slow.

I took the liberty to change the initial line into an InfiniteLine to add some spice. Essentially this solves for line-polyline intersection:

vtx = {{4.4, 14}, {6.7, 15.25}, {6.9, 12.8}, {9.5, 14.9}, {13.2,
11.9}, {10.3, 12.3}, {6.8, 9.5}, {13.3, 7.7}, {0.6, 1.1}, {1.3,
2.4}, {2.45, 4.7}} // Rationalize;

line = InfiniteLine[{{0, 10}, {20, 20}}];

sol = Solve[{x, y} ∈ line && {x, y} ∈ Line@Append[vtx, vtx[[1]]], {x, y}]

(*{{x -> 736/185, y -> 2218/185}, {x -> 3493/510,
y -> 13693/1020}, {x -> 721/80, y -> 2321/160}, {x -> 4663/485,
y -> 14363/970}}*)

Graphics[{Polygon[vtx], Thick, Red, line, Green, PointSize[0.05], Point[{x, y} /. sol]}]


For a Polygon-based approach Solve seems only to work with triangles (so an exact solution will still be possible with some additional work). Hopefully this functionality will be much enhanced in the future.

As of V11.1 you can use RegionDisjoint.

polygon = Polygon[{{4.4, 14}, {6.7, 15.25}, {6.9, 12.8}, {9.5, 14.9}, {13.2, 11.9},
{10.3, 12.3}, {6.8, 9.5}, {13.3, 7.7}, {0.6, 1.1}, {1.3, 2.4}, {2.45, 4.7}}];

line = Line[{{0, 10}, {20, 0}}];

!RegionDisjoint[line, polygon]

True


For a version 9 solution, consider two line segments, the first between $\{x_1,y_1\}$ and $\{x_2,y_2\}$, the second between $\{u_1,v_1\}$ and $\{u_2,v_2\}$. Parameterize points on the two segments with $\{x_1,y_1\}+s~ (\{x_2,y_2\}-\{x_1,y_1\})$ and $\{u_1,v_1\}+t~(\{u_2,v_2\}-\{u_1,v_1\})$, where the parameters $s$ and $t$ must lie between 0 and 1, inclusive. The two segments intersect if there exists a common point on both lines with parameters $s$ and $t$ within their bounds. The common point is found by equating the two expressions, breaking into two equations in two unknowns, and solving for $s$ and $t$.

IntersectSegmentsQ[{{x1_,y1_}, {x2_,y2_}}, {{u1_,v1_}, {u2_,v2_}}] :=
With[{st={{v1-v2, u2-u1},{y1-y2, x2-x1}}.{u1-x1,v1-y1}/((x2-x1)(v1-v2)-(y2-y1)(u1-u2))},
(0. <= st[[1]] <= 1.) && (0. <= st[[2]] <= 1.) == True]


Map[IntersectSegmentsQ[{{0,10},{20,0}},#]&, Partition[Join[list, {list[[1]]}], 2, 1]]