# comp.graphics.algorithms

## 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.
>
> Jonni

Hi All,

I implemented the 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).
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?

Thanks

Jonni