On Apr 2, 10:15=A0am, Miss Elaine Eos <M...@[EMAIL PROTECTED]
>
wrote:
> In article <65h402F2fkqt...@[EMAIL PROTECTED]
>,
> =A0"Jens Hilwig" <jhil...@[EMAIL PROTECTED]
> wrote:
> > Im looking for a fast =A0algorithm for detecting all Intersections of
mu=
ltiple
> > 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:
> =A0 =A0dist2D =3D sqrt ((dx * dx) + (dy * dy))
> =A0 =A0dist3D =3D 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
|
