Home Products Download Order Contacts

comp.graphics.algorithms

Subject: Fast search of closest point on a fix 3D polyline



Hi all,

I have the need to implement a solution to find the closest point on a
3D polyline of a given 3D point.
I'm aware that this is not a new topic but my main pain is about how to
optimize the search .
Below you'll get some more details about what I'm looking for.

- The polyline is a FIXED 3D polyline
- The polyline tipically contains a few thousand of points
- The search must be done many many times so it must be very very fast
- The position of the point (whose closest point on the polyline must
be found) between 2 subsequent searches "does not change a lot"
To be more precise let's say that the distance between its two
subsequent positions is no more than 1/1000 of the longest dimension of
the bounding box including the polyline

I have already implemented an algorithm to get the closest point based
on the idea of an hierarchy of bounding boxes
(http://www.cs.utah.edu/research/techreports/1997/pdf/UUCS-97-003.pdf -
Section 3.1).
The implementation works fine but I want to increase the performances
of my solution.
I guess that somehow I can do that taking into account that the
position of the input point does not change
too much between 2 searches and so the closest point of a new search is
likely to be close to the one of the previous search.

Is there anybody who had to solve a similar problem?
Any suggestion is appreciated!

Thanks a lot.

Jonni


Reply


View All Messages in comp.graphics.algorithms

path:


Replies:
Re: Fast search of closest point on a fix 3D polyline
Re: Fast search of closest point on a fix 3D polyline
Re: Fast search of closest point on a fix 3D polyline

Copyright 2006 WatermarkFactory.com. All Rights Reserved.