# How to determine if lines intersects

This is more a math question than a GN one but in order to fully answered this question, I need to know how to do this. In 3D space, I have points witch supports velocity vectors, so I need to know if the straight lines witch pass by those points and have the same direction of there vectors intersects. How to do that in GN? Thank you for your help.

• Are you intersecting lines in 2D or 3D? As always open to correction.. 2D can give a definite answer.. 3D very prone to floating-point error, needs some sort of margin, which in turn, needs some sort of volume-search.... Maybe geometry proximity can do that for you, though Jan 6, 2023 at 12:38
• @RobinBetts In 3D of course. Frankly I have no idea how to use Geometry Proximity in this case, so please fell free to lead me... Jan 6, 2023 at 12:45
• I vaguely remember a @quellenform answer for 2D intersections, but couldn't find it now. There's a design task/work-in-progress patch for a new Curve Intersections node, hopefully we get that soon: developer.blender.org/T102050 Jan 6, 2023 at 12:57
• @Kuboå I hope they patch it soon.Thanks for the info... Jan 6, 2023 at 13:01
• Also there's this very weird little trick where if you have a bunch of intersecting curve lines (but no "breaks" where they intersect) and you resample them with at least a Count—3, then use Fill Curve, it breaks the lines where they intersect so you get intersection points... but it also flattens the whole thing, making it into a 2D curve... I said it was weird: i.imgur.com/HailjAP.gif Jan 6, 2023 at 13:02

Looking back at my own question from some time ago:

Geometry Nodes: How the nearest face/edge is found?

One of the conclusions was the nearest edge is found without any approximations, though this was a point-to-edge comparison, not edge-to-edge. Therefore you need to subdivide an edge a lot to get a decent approximation, however that's just one edge, which is crucial (having $$10'000$$ comparisons might seem expensive, but it's way faster than $$10'000² = 100'000'000$$ comparisons; it's actually way more than 10 thousand faster because of similar logic to economies of scale but opposite effect)

Using quellenform's technique:

Viewer Node shows only the status of the connected geometry instead of the final result (Blender 3.4)

What you do with the statistic further is up to you: does $$0.00001$$ distance mean the edges touch? If you want to be very rigorous about it, you can compare the minimum distance with 0, and εpsilon of 0 - this, however, will be extremely unlikely with "just" 10 000 samples. You would need more like a trillion samples… It all depends on the length of the sampled edge and where they touch: in the worst case scenario you could have a very long edge, let's say a kilometer long, very near but not at the origin, with the ends positioned in such a way, that samples never quite hit the spot. The smallest float32 value is:

>>> import numpy as np
>>> np.nextafter(np.float32(0), np.float32(1))
1e-45

>>> f"{_:0.50f}"
'0.00000000000000000000000000000000000000000000140130'


So the number of samples for an edge of length $$1$$ is roughly the reciprocal of the above value, $$10^{45}$$ or $$1000000000000000000000000000000000000000000000$$

It's actually almost irrelevant if the edge is longer than 1 unit and instead is 1000 units (1 kilometer) long, as that adds just 3 zeroes to the above behemoth.

However:

>>> log2(10**(45+3))
159.4525485545934

>>> pow(2, 160)
1.461501637330903e+48


What this means is that if you resample the curve to just 3 points, you can then remove the point with the maximum distance, and repeat the process… You would need 160 such repetitions which is a lot, but unlike the 1000000000000000000000000000000000000000000000 samples scenario, this one is actually doable.

• that's a lot of statistics ;) I will try your method, and let you know if was able to apply it in the case of this question: blender.stackexchange.com/questions/282887/… Thanks a lot Markus. Jan 6, 2023 at 20:34
• @Nathan Where did your solution goes? iIt seam to be very interesting... Jan 7, 2023 at 18:39

Edit: Another way to determine if lines intersect is to use normal, first see if they are co-planar with a Convex Hull, I was hopping that if the Convex Hull have just 2 faces it was co-planar.

But even if it is co-planar the Convex Hull had more than 2 faces some times. So we have to had another condition if the 2 first faces (those 2 are on the same side) have the same normal (there distance is null). And with those 2 conditions we are able to determine if it's co-planar:

Then by convert those mesh lines into curve to select and convert there last point into an instance (a grid mesh), after realizing those instances it's easy to compare there normal. If there normal are not equal they will intersect at some point. But of course we have to get rid of the case when the normal are directly opposed (lines are parallel in this case). So if they are co-planar and if there direction is different they intersect or will intersect at some point:

This method is not fully tested and there is two consecutive approximations so it's not so precise...

The updated .blend

In order to move the end points of the line use the empties named Ctrl-1 and Ctrl-2, if they intersect or will intersect at some point 2 planes will appear...

• In your .blend file the two lines L1 and L2 don't intersect and yet the 2 planes appear (which is supposed to mean they intersect). Could you add some explanation how to use this example, e.g. the steps to move lines around to see how the setup reacts to lines starting/stopping to intersect? If this works for exact intersection tests, it will be much better than my solution; I wasn't motivated to make the mathematical solution because I don't think it's a realistic need to find an exact intersection of two lines, but since the thread got some attention I might reconsider… Jan 8, 2023 at 12:33
• @Markus von Broady : Thank you so much for your feed-back.I doubt seriously that this method is better for an exact intersection test (those 2 consecutive approximations cause me trouble). But it's another way, any way... I hope the edit is better than the first version. Jan 8, 2023 at 13:53
• I see by a line you mean a mathematical definition of a line, which is infinite? So if the lines lay on the same plane, they don't intersect only if they are parallel? Jan 8, 2023 at 16:01
• @Markus von Broady, You right in this case I consider lines as infinite, and If they are co-planar and not parallel they definitely intersect. Jan 8, 2023 at 16:09