**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.