In 2D (and only there), you can use the undocumented function Graphics`Mesh`FindIntersections
to find the point of intersection. This is often an order of magnitude faster than RegionIntersection
. If there isn't any intersection point, then an empty list is returned.
plot[l1_, l2_] := Graphics[{Thick, PointSize[0.025], Darker@Green, Point @@ l1, l1, Darker@Red, l2, Point @@ l2}];
l1 = Line@RandomReal[{-1, 1}, {2, 2}];
l2 = Line@RandomReal[{-1, 1}, {2, 2}];
pt = Graphics`Mesh`FindIntersections[{l1, l2}];
Graphics[{l1, l2, Red, Point[pt]}]
So something like
LineIntersectionQ2[l1_, l2_] := Length[Graphics`Mesh`FindIntersections[{l1, l2}]] > 0
could be quite a lot faster on average.
Apparently, this finds only intersection points if they are isolated. The following examples shall illustrate this:
plot[l1_, l2_] := Graphics[{Thick, PointSize[0.025],
Darker@Green, Point @@ l1, l1,
Darker@Blue, l2, Point @@ l2,
Red, Point[Graphics`Mesh`FindIntersections[{l1, l2}]]
},
Frame -> True];
l1 = Line[{{-1., 0}, {1., 0.}}];
l2 = Line[{{0., 1.}, {0., -1}}];
plot[l1, l2]
l1 = Line[{{-1., 0}, {1., 0.}}];
l2 = Line[{{1., 2.}, {1., 0.}}];
plot[l1, l2]
l1 = Line[{{-1., 0}, {1., 0.}}];
l2 = Line[{{0., 2.}, {0., 0.}}];
plot[l1, l2]
l1 = Line[{{0., 0.}, {2., 0.}}];
l2 = Line[{{1., 0.}, {3., 0.}}];
plot[l1, l2]
l1 = Line[{{0., 0.}, {2., 0.}}];
l2 = Line[{{2., 0.}, {4., 0.}}];
plot[l1, l2]
l1 = Line[{{0., 0.}, {2., 0.}}];
l2 = Line[{{3., 0.}, {5., 0.}}];
plot[l1, l2]
l1 = Line[{{0., 1.}, {2., 1.}}];
l2 = Line[{{1., 0.}, {3., 0.}}];
plot[l1, l2]
I am not sure whether this is what you are looking for. You say that you want to know when the line segments intersect at a point
. Do you happen to mean intersect at a single point
? In that case Graphics`Mesh`FindIntersections
seems to be your friend.
Anyways, Graphics`Mesh`FindIntersections
is still super slow. It can only test a few thousand line pairs per second. I recently wrote an C++ implementation of the Gilbert–Johnson–Keerthi distance algorithm. That one can test up to 20 million line segment pairs per second. Just to give you an idea how far one can push this.
Line
objects in the plane (2D) only, or also in 3D or even nD? $\endgroup$