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. – novice Nov 20 '14 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. – Daniel Lichtblau Nov 20 '14 at 14:49
• In V10 Solve with geometric regions is very comfortable, if a bit slow... – Yves Klett Nov 20 '14 at 14:51
• @Daniel Lichtblau, unfortunately that fails if the polygon is nonconvex. – novice Nov 20 '14 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. – george2079 Nov 20 '14 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 – novice Nov 21 '14 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. – rcollyer Nov 21 '14 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. – novice Nov 21 '14 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) – Rahul Nov 20 '14 at 16:22
• @Rahul Even for r1 = Line[{{10, 10}, {12, 10}}]? I'm on Linux 10.0.1. – Öskå Nov 20 '14 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. – Rahul Nov 20 '14 at 17:01
• @Rahul The last example doesn't give you {False, True}? – Öskå Nov 20 '14 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. – Rahul Nov 20 '14 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]]