ansaurus

Question

The Algorithm to Find the Point of Intersection of Two 3D Line Segment

Answer 1

A:

You might find it useful to take a look at a corresponding article in Wikipedia - it does not have a code, but the algorithm is described pretty well, imho (but you should know some math anyway).

http://en.wikipedia.org/wiki/Bentley%e2%80%93Ottmann_algorithm

Update: funny enough is that Russian version of the same Wikipedia entry contains more details (and formular) and an algorithm description is pseudo-code as well. Here's a link to translation of this entry to English (via Google Translate):

http://translate.google.com/translate?hl=en&sl=ru&tl=en&u=http%3A%2F%2Fru.wikipedia.org%2Fwiki%2F%25D0%259F%25D0%25B5%25D1%2580%25D0%25B5%25D1%2581%25D0%25B5%25D1%2587%25D0%25B5%25D0%25BD%25D0%25B8%25D0%25B5_%25D0%25BE%25D1%2582%25D1%2580%25D0%25B5%25D0%25B7%25D0%25BA%25D0%25BE%25D0%25B2

AlexS 2010-02-23 08:11:06

The wiki entry contains only description of 2D one

Ngu Soon Hui 2010-02-23 08:13:29

Man, I said that you should know some math - it's easy to draw a generalized version (you just need to add one more component (coordinate))

AlexS 2010-02-23 08:19:54

Seems to me like Ottmann algorithm actually describes the strategies how to to find efficiently the lists intersection points if there are a list of lines, but as to how to actually find the intersection point, it doesn't say. See the pseudo code here for my point: http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm#Bentley-Ottmann%20Algorithm

Ngu Soon Hui 2010-02-23 08:37:25

Answer 2

A:

But finding the point of intersection for two 3D line segment is not, I afraid.

I think it is. You can find the point of intersection in exactly the same way as in 2d (or any other dimension). The only difference is, that the resulting system of linear equations is more likely to have no solution (meaning the lines do not intersect).

You can solve the general equations by hand and just use your solution, or solve it programmatically, using e.g. Gaussian elemination.

Jens 2010-02-23 08:34:31

If we extend the 2D way of doing things, you will have three equations (`x`,`y` and `z`) for two unknowns (`u`,`v`). It is definitely nontrivial to solve it.

Ngu Soon Hui 2010-02-23 08:39:31

Well... as trivial as the 2d case. You could just use the first two equations to determine u and v, and then check if the last equation holds with these values for u and v. If it does, you have found your intersection. If it does not, the lines do not intersect. I do not see any difficulty here.

Jens 2010-02-23 08:59:28

In Linear Algebra, this is considered trivial. For an algorithm some care must be taken, though. For example, if the two lines both lived in the x=0, y=0 or z=0 plane, one of those three equations will not give you any information. (Assuming the equations are some_point_on_line_1 = some_point_on_line_2)

Derek E 2010-02-23 21:45:58

@Derek, that's something I strive to avoid by having a generic solution; I don't want to check the edge cases all over my code.

Ngu Soon Hui 2010-02-24 01:30:42

Answer 3

A:

I found a solution: it's here.

The idea is to make use of vector algebra, to use the dot and cross to simply the question until this stage:

a (V1 X V2) = (P2 - P1) X V2

and calculate the a.

Note that this implementation doesn't need to have any planes or axis as reference.

Ngu Soon Hui 2010-02-23 09:16:58

Answer 4

+1 A:

Most 3D lines do not intersect. A reliable method is to find the shortest line between two 3D lines. If the shortest line has a length of zero then you know that the two original lines intersect.

A method for finding the shortest line between to 3D lines can be found on Paul Bourke's website which is an excellent geometry resource.

http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/

Doug Ferguson 2010-02-23 09:18:57

ansaurus

tags:

views:

answers:

The Algorithm to Find the Point of Intersection of Two 3D Line Segment

related questions