comp.graphics.algorithms

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

"Jonni" wrote in message
> 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
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