**comp.graphics.algorithms**

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

"Jonni"

news:1146727115.317605.129410@i39g2000cwa.googlegroups.com...

> So lets say that:

> - the polyline represents the centerline of a path that your car should

> follow

> - the input point is a point of the car or in front of the car (not too

> far)

>

> In this scenario, situations like the one you described are not likely

> to happen (I think).

> Of course I need to have a robust solution meaning that in certain

> unlucky cases (don't know what they are now) I HAVE to do safe search

> without taking into account the position of the previous input point.

Yes, you should use as much information as you can

about your polylines. The situation you describe is

analogous to keyframe animation, where you take

advantage of time coherency. Given an ordered

sequence of positions/times, (P[0],t[0]) through

(P[n],t[n]), and given a desired time T for interpolation,

you search for the index i for which t[i] <= T < t[i+1].

The positions P[i] and P[i+1] are interpolated to produce

a position associate with time T. If the search starts at

i = 0 every frame, you have a slow animation. The search

is O(N). However, using time coherency, you save the last

index i_last from the previous search and use it as the

starting index for the current search. With time coherency,

you now have an O(1) lookup (and a faster animation).

In you situation, you can save the index into the polyline

for the segment that was closest on the last query, and

start a search from this segment for the current query.

Unlike the animation case, you might have to search

"forward" and "backward", perhaps alternating between

segments in each direction.

To monitor whether or not you need to be "robust" with

a global search, keep track of the "curvature" of the

polyline. If the segments located near the closest segment

do not deviate much in curvature/direction from the closest

segment, there is a large probability that the localized

search will produce the correct result. But if the segments

start changing direction drastically, you can fall back to a

global search.

--

Dave Eberly

http://www.geometrictools.com

Reply

View All Messages in

**comp.graphics.algorithms**

path:

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 =>

Replies:

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

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.