12
$\begingroup$

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]}]

enter image description here

Improve this question
$\endgroup$
10
  • $\begingroup$ @Öskå Thanks. I'm working with v9, but I will check v10. $\endgroup$
    – novice
    Nov 20, 2014 at 14:37
  • 2
    $\begingroup$ 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. $\endgroup$
    – Daniel Lichtblau
    Nov 20, 2014 at 14:49
  • $\begingroup$ In V10 Solve with geometric regions is very comfortable, if a bit slow... $\endgroup$
    – Yves Klett
    Nov 20, 2014 at 14:51
  • $\begingroup$ @Daniel Lichtblau, unfortunately that fails if the polygon is nonconvex. $\endgroup$
    – novice
    Nov 20, 2014 at 15:07
  • 2
    $\begingroup$ 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. $\endgroup$
    – george2079
    Nov 20, 2014 at 17:48

6 Answers 6

Reset to default
13
$\begingroup$

As you are using v9, I would suggest using the undocumented function - Graphics`Mesh`IntersectQ which does exactly what you want:

plist = {Line[{{20, 10}, {20, 0}}], Polygon[list]};
Graphics`Mesh`IntersectQ[plist]
Graphics[MapThread[{##} &, {{Red, Blue}, plist}]]
(* False *)

enter image description here

which is also in v10.

Improve this answer
$\endgroup$
3
  • $\begingroup$ @ rcollyer, your method is about 60 times faster than using RegionIntersection in V10 $\endgroup$
    – novice
    Nov 21, 2014 at 2:57
  • $\begingroup$ RegionIntersection returns a region, while Graphics`Mesh`IntersectQ just tests whether they intersect or not. In many ways, the former is a more involved process, so I expect it to be slower. $\endgroup$
    – rcollyer
    Nov 21, 2014 at 3:14
  • 1
    $\begingroup$ @ 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 Graphics`Mesh`IntersectQ 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. $\endgroup$
    – novice
    Nov 21, 2014 at 6:53
12
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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}:

Mathematica graphics

Mathematica graphics

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

False

Mathematica graphics

Side note (aka bug?):

Can someone please confirm this?

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}}]:

Mathematica graphics

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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) $\endgroup$
    – user484
    Nov 20, 2014 at 16:22
  • $\begingroup$ @Rahul Even for r1 = Line[{{10, 10}, {12, 10}}]? I'm on Linux 10.0.1. $\endgroup$
    – Öskå
    Nov 20, 2014 at 16:55
  • $\begingroup$ 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. $\endgroup$
    – user484
    Nov 20, 2014 at 17:01
  • $\begingroup$ @Rahul The last example doesn't give you {False, True}? $\endgroup$
    – Öskå
    Nov 20, 2014 at 17:03
  • $\begingroup$ 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. $\endgroup$
    – user484
    Nov 20, 2014 at 17:07
6
$\begingroup$

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]}]

Mathematica graphics

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.

Improve this answer
$\endgroup$
0
4
$\begingroup$

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
Improve this answer
$\endgroup$
2
$\begingroup$

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]

For your small example,

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

There are no optimizations here. Of course, for a large number of polygons with a large number of edges along with a large number of line segments, this approach is an epic fail.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.