Subject: Re: Fast search of closest point on a fix 3D polyline
Jonni ha scritto:
> 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.
I implemented the algorithm to get the closest point based
on the idea of an hierarchy of bounding boxes
I'm not satisfied with the performances of my implementation and I feel
I might have made some stupid mistakes.
Does anyone know about any free implementation around?
View All Messages in comp.graphics.algorithms
Fast search of closest point on a fix 3D polyline =>
Copyright © 2006 WatermarkFactory.com. All Rights Reserved.