fast algorithm for detecting all Intersections of multiple linesegments
Jens Hilwig
Im looking for a fast algorithm for detecting all Intersections of multiple
linesegments.(only linesegments nothing else)
In 2D there is a fast sweep line algorithm by Bentley-Ottmann but I did not
found a fast alogorithm for the 3D space.
Can you help me ?
regards
jens
Miss Elaine Eos
"Jens Hilwig" <jhi...@gmx.de> wrote:
Same algorithm, modify for 3 dimensions.
Example of modifying 2D to 3D:
dist2D = sqrt ((dx * dx) + (dy * dy))
dist3D = sqrt ((dx * dx) + (dy * dy) + (dz * dz))
--
Please take off your pants or I won't read your e-mail.
I will not, no matter how "good" the deal, patronise any business which sends
unsolicited commercial e-mail or that advertises in discussion newsgroups.
IsaacKuo
wrote:
> In article <65h402F2fkqt...@mid.uni-berlin.de>,
> "Jens Hilwig" <jhil...@gmx.de> wrote:
> > Im looking for a fast algorithm for detecting all Intersections of multiple
> > linesegments.(only linesegments nothing else)
What do you need this for? Assuming you're using doubles, then
generally line segments don't interesect at all (except for line
segments
which share an endpoint, or which are coplanar on a plane normal to a
coordinate axis). The probability of exactly intersecting lines is
low.
For a typical application, what you'd really need is to determine
whether two line segments are "close enough" to each other.
> > In 2D there is a fast sweep line algorithm by Bentley-Ottmann but I did not
> > found a fast alogorithm for the 3D space.
> > Can you help me ?
> Same algorithm, modify for 3 dimensions.
> Example of modifying 2D to 3D:
> dist2D = sqrt ((dx * dx) + (dy * dy))
> dist3D = sqrt ((dx * dx) + (dy * dy) + (dz * dz))
Does not even make sense, much less work.
However, Bentley-Ottmann is a good start. First, you use Bentley-
Ottmann
while ignoring the Z dimension to determine candidate intersections.
Then
you calculate the distance between the lines of the candidates to
determine
whether they are "close enough".
The distance between two line segments is calculated by first
determining the unit normal. Do this by calculating the cross
product of the line segment vectors, and normalize to a length
of one. This gives you a unit vector which is perpendicular to
both of the line segments. Then, take the difference between
two points of either line (i.e. take either endpoint of each line
segment), and dot product it with that unit normal. The
absolute value of this dot product is the distance between the
two lines. If that value is less then "epsilon", your arbitrary
value for "close enough", then the line segments intersect.
Isaac Kuo
Geoffrey Summerhayes
>
<* snip*>
>
> However, Bentley-Ottmann is a good start. First, you use Bentley-
> Ottmann
> while ignoring the Z dimension to determine candidate intersections.
> Then
> you calculate the distance between the lines of the candidates to
> determine
> whether they are "close enough".
>
> The distance between two line segments is calculated by first
> determining the unit normal. Do this by calculating the cross
> product of the line segment vectors, and normalize to a length
> of one. This gives you a unit vector which is perpendicular to
> both of the line segments. Then, take the difference between
> two points of either line (i.e. take either endpoint of each line
> segment), and dot product it with that unit normal. The
> absolute value of this dot product is the distance between the
> two lines. If that value is less then "epsilon", your arbitrary
> value for "close enough", then the line segments intersect.
Actually, since you have a possible point of intersection
(x-y) wouldn't it be simpler to determine the z on both
lines at that point and compare the difference to epsilon?
If they do intersect, it has to occur at that point.
The only problem is that Bentley-Ottmann doesn't really
work in 3d. Unlike 2d, it's possible for the 'above' and
'below' lines not to intersect, but still have others that
do, so you can't reject it during the search.
So the only way I can see of using the algorithm, is to
keep all the possible intersections during the xy pass
and run through the points and the lines that intersected
there and check the z afterwards.
---
Geoff
IsaacKuo
> On Apr 2, 12:25 pm, IsaacKuo <mech...@yahoo.com> wrote:
> > However, Bentley-Ottmann is a good start. First, you use Bentley-
> > Ottmann
> > while ignoring the Z dimension to determine candidate intersections.
> > Then
> > you calculate the distance between the lines of the candidates to
> > determine
> > whether they are "close enough".
> > The distance between two line segments is calculated by first
> > determining the unit normal. Do this by calculating the cross
> > product of the line segment vectors, and normalize to a length
> > of one. This gives you a unit vector which is perpendicular to
> > both of the line segments. Then, take the difference between
> > two points of either line (i.e. take either endpoint of each line
> > segment), and dot product it with that unit normal. The
> > absolute value of this dot product is the distance between the
> > two lines. If that value is less then "epsilon", your arbitrary
> > value for "close enough", then the line segments intersect.
> Actually, since you have a possible point of intersection
> (x-y) wouldn't it be simpler to determine the z on both
> lines at that point and compare the difference to epsilon?
> If they do intersect, it has to occur at that point.
That's a possibility, but it's has more aliasing effects. By
calculating the true distance, you're essentially looking for
intersections between cylinders. There very tips of the
cylinders are chopped off in a way which isn't symmetric,
but that's a pretty small "error".
What you suggest will make the critical distance sensitive
to line segment alignment. For line segments which are
mostly parallel to the XY plane, then the segments need
to be closer than epsilon. But if a line segment is angled
at theta from the Z axis, then the critical distance is
epsilon/sin(theta).
Depending on the application, that might mean an artificially
low number of intersections with line segments that are
mostly aligned to the Z axis and/or an artificially high number
of intersections with line segments that are roughly parallel
to the XY plane.
> The only problem is that Bentley-Ottmann doesn't really
> work in 3d. Unlike 2d, it's possible for the 'above' and
> 'below' lines not to intersect, but still have others that
> do, so you can't reject it during the search.
> So the only way I can see of using the algorithm, is to
> keep all the possible intersections during the xy pass
> and run through the points and the lines that intersected
> there and check the z afterwards.
Right, with the caveat that checking for 3d intersections
afterward may not be so obvious. It's going to depend on
exactly what you're doing with the results.
Isaac Kuo
Geoffrey Summerhayes
Ok, I'll admit that, hadn't really thought that all the
way through. Might make an early acceptance test, but I'm
not sure if it would save any processing time.
> > The only problem is that Bentley-Ottmann doesn't really
> > work in 3d. Unlike 2d, it's possible for the 'above' and
> > 'below' lines not to intersect, but still have others that
> > do, so you can't reject it during the search.
> > So the only way I can see of using the algorithm, is to
> > keep all the possible intersections during the xy pass
> > and run through the points and the lines that intersected
> > there and check the z afterwards.
>
> Right, with the caveat that checking for 3d intersections
> afterward may not be so obvious. It's going to depend on
> exactly what you're doing with the results.
Depends a lot on the input data too, I can think of some
degenerate cases where AABB + line-to-line testing would
come out on top.
----
Geoff
John Nagle
> Hello,
>
> Im looking for a fast algorithm for detecting all Intersections of multiple
> linesegments.(only linesegments nothing else)
Why?
It sounds like you're trying to do some kind of collision detection,
but aren't familiar with how that's done.
John Nagle
Animats
Jens Hilwig
>
> It sounds like you're trying to do some kind of collision detection,
> but aren't familiar with how that's done.
Hello,
Im realy not familar with the different kinds of collision detection. In my
case I have a kind of water pipesystem (3D Lines) and I have to check the
connections and intersections of the lines. Because its a closed system,
there are many connections and intersections between the lines.
There are no other elemets than 3D lines, so I think a classic collision
detection is "too good" for my special problem. Im wrong here ?
If you know a "simple" collection detection that can handle my problem,
please let me know.
Thanx
Jens
"John Nagle" <na...@animats.com> schrieb im Newsbeitrag
news:47f5c930$0$36350$742e...@news.sonic.net...
IsaacKuo
> Im realy not familar with the different kinds of collision detection. In my
> case I have a kind of water pipesystem (3D Lines) and I have to check the
> connections and intersections of the lines. Because its a closed system,
> there are many connections and intersections between the lines.
You mean some sort of static model of water pipes (i.e. not moving)?
The pipes have a certain thickness--you surely have to account for
that, right?
This scenario has a few interesting complications, in that each line
segment will typically share endpoints with at least two other
segments.
Thus, the "special" case where intersections are at the endpoints
is actually the normal case.
Also, in a typical water pipe system, most pipes will be aligned with
a coordinate axis, and will exactly share a coordinate plane with many
other pipes. This increases the chances of an intersection.
> There are no other elemets than 3D lines, so I think a classic collision
> detection is "too good" for my special problem. Im wrong here ?
> If you know a "simple" collection detection that can handle my problem,
> please let me know.
From what it sounds like, you need reliability and simplicity more
than you need speed. Personally, I'd go with a dumb O(n^2)
check between each pair of pipes. That's the easiest to implement
and debug. You simply check each pipe against each other pipe
with a couple nested FOR loops. That way, you just need to
debug the collision detection routine; the rest is practically
foolproof.
How many line segments are we talking about, here? I suspect
performance will not be an issue, compared to simplicity and
reliability.
Isaac Kuo
Miss Elaine Eos
<58ae07f8-ceb5-4d92...@c65g2000hsa.googlegroups.com>,
IsaacKuo <mec...@yahoo.com> wrote:
> On Apr 4, 4:25 am, "Jens Hilwig" <jhil...@gmx.de> wrote:
>
> > Im realy not familar with the different kinds of collision detection. In my
> > case I have a kind of water pipesystem (3D Lines) and I have to check the
> > connections and intersections of the lines. Because its a closed system,
> > there are many connections and intersections between the lines.
> You mean some sort of static model of water pipes (i.e. not moving)?
> The pipes have a certain thickness--you surely have to account for
> that, right?
>
> This scenario has a few interesting complications, in that each line
> segment will typically share endpoints with at least two other
> segments.
> Thus, the "special" case where intersections are at the endpoints
> is actually the normal case.
>
> Also, in a typical water pipe system, most pipes will be aligned with
> a coordinate axis, and will exactly share a coordinate plane with many
> other pipes. This increases the chances of an intersection.
...But greatly simplifies detection! Also, it matters a lot if the
pipes are allowed to be anywhere, or have to be placed on a grid. That
is, can I have 2 pipes exactly parallel, but one of them is 1/4
pipe-diameter higher than the other? Or does the grid require that
parallel pipes either occupy the same space fully or fully-not?
Etc. There are lots of things that can simplify the answer, if we knew
more about your game.
> > There are no other elemets than 3D lines, so I think a classic collision
> > detection is "too good" for my special problem. Im wrong here ?
> > If you know a "simple" collection detection that can handle my problem,
> > please let me know.
> From what it sounds like, you need reliability and simplicity more
> than you need speed. Personally, I'd go with a dumb O(n^2)
> check between each pair of pipes. That's the easiest to implement
> and debug. You simply check each pipe against each other pipe
> with a couple nested FOR loops. That way, you just need to
> debug the collision detection routine; the rest is practically
> foolproof.
>
> How many line segments are we talking about, here? I suspect
> performance will not be an issue, compared to simplicity and
> reliability.
Agreed on simplicity and reliability. But, also, if his pipes are on a
gridwork (as with many plumbing games, or the pipes screen saver), he
can do much better. On a grid, each pipe pretty-much becomes its own
bounding box!
I'd concur with your "go with dumb algorithm" to start, but keep it in a
cleanly separate method, to allow optimisation later, if that proves
necessary.
(But optimise LAST!)
John Nagle
>> Why?
>>
>> It sounds like you're trying to do some kind of collision detection,
>> but aren't familiar with how that's done.
>
> Hello,
>
> Im realy not familar with the different kinds of collision detection. In my
> case I have a kind of water pipesystem (3D Lines) and I have to check the
> connections and intersections of the lines. Because its a closed system,
> there are many connections and intersections between the lines.
>
> There are no other elemets than 3D lines, so I think a classic collision
> detection is "too good" for my special problem. Im wrong here ?
> If you know a "simple" collection detection that can handle my problem,
> please let me know.
If the lines have no thickness in a 3D space, intersection detection is
not a useful concept. If they have thickness, you need real
collision detection.
There are many good collision detection packages out there. You're
probably better off downloading one rather than trying to develop
something yourself.
Real 3D collision detection is incredibly fast when done right.
John Nagle
Animats