Re: Looking for algo. to find points along alignment


Daniel Lidstrom wrote:
elrabin@xxxxxxxxx wrote:
You could try a sort of adaptive algorithm, recursively chopping the
segment in half. Pick the two endpoints and see if the projection of
the vectors between the point and the endpoints onto the line
connecting the two endpoints are in opposite directions. If so, you
recurse until you find a single segment or the group of segments no
longer contain a normal point.

This algorithm also sounds promising, but I found a case where it seems
to fail.

It can be adapted of course to compare the vectors to the tangents at
the endpoints. But it would still not work for other reasons.
What you are really looking for is the point on the path that is
nearest to the station point. That the line connecting the station to
that nearest point is usually perpendicular to the path is a red
herring - it need not be so since the path is not necessarily smooth,
and the nearest point could be one of the end points of a segment.

No, I would also go for a divide and conquer method, but using bounding
rectangles as in the other reply.
Pre-compute the bounding rectangle for any consecutive segments in the
path.

Given a bounding rectangle and the station point, you can work out what
range the distance could be between the point and the path inside the
rectangle. Put simply, it is somewhere between the distance to furthest
cornerpoint and the distance to the nearest corner point. (If the
station lies inside the rectangle, it is between 0 and the distance to
the furthest corner (*). )

Now do a divide and conquer algorithm. I.e. split the path into two
(**), and check the distance range to each one. Unfortunately the
distance ranges will overlap, so you can't throw away either one. Split
both into two parts again, and check the distance ranges to each of the
new bounding rectangles. If the nearest point of one is further than
the furthest point of another, you can discard the first.

Maybe you need to keep these ranges in two sorted lists - one sorted by
shortest distance, one sorted by furthest.

Anyway, once it is divided as far as it can go, you have a list of
bounding rectangles, each containing one segment of the path. These
will have to be individually checked to find the actual closest one.

(*) I think you can do better than this but I haven't really thought
about it.
(**) It is probably faster to do the first division into 3 or 4 parts
directly.

.

Relevant Pages

  • Re: Minimum Distance of Random Points on a Line
    ... before the distance calculation begins, ... one point from each set is contained in that segment. ... distance between those endpoints. ... The minimum distance between any two points on the line, ...
    (sci.math)
  • Re: Distance between segments
    ... the parts of the two segments that are near a certain distance. ... if the segment A is defined by its two ending points Pa0=, ... where the foot of the perpendicular lies ... The distances between endpoints are easy. ...
    (sci.math)
  • Re: Length and area..
    ... A line in Euclidean geometry can't be the ... distance between two points, because a line has infinite length. ... line segment has finite length. ... endpoints of the line segment. ...
    (sci.math)
  • Re: OT:Three questions for Scott
    ... and then left her for a younger woman (Cindy). ... watching that segment it is hard to see "Country First". ... It had to do with Congress laying restrictions ... on long distance flights to and from NAtional ...
    (rec.audio.opinion)
  • Re: OT:Three questions for Scott
    ... and then left her for a younger woman (Cindy). ... watching that segment it is hard to see "Country First". ... It had to do with Congress laying restrictions ... on long distance flights to and from NAtional ...
    (rec.audio.opinion)