I have two sets of line segments that should basically overlap, but not exactly, and I want to see where they don't match up well.

I've come up with this idea to flag the locations where there is a bad match. For each line segment in set A, find the point on that line segment that is farthest from any point on any line segment in set B, and find the distance from that point to the closest line segment in set B. That distance is the badness score for that line segment. Then I can rank the line segments in A based on that score, or have a threshold, or whatever. And I can run the same algorithm the other way to find bad line segments in B.

I've found algorithms for finding the nearest line segment to a point, but not for finding the point on a line segment that is furthest from its nearest line segment.

12/20/12 Here's a picture I'm adding to clarify things because I couldn't put preformatted text in the comments.

____________________ A
_____          _____
B                  C

CoffeMath's answer isn't exactly what I am looking for. If I understand correctly, his algorithm would say there's a point on A that is 15 units away from B, and there's a point on A that is 15 units away from C. Take the min of those, so the score is 15. But the endpoint of A that is 15 units away from B is really close to a point on C, and vice versa. What I'm looking for is that there is a point in the middle of A that is 5 units away from B and 5 units away from C. It has the maximum distance from any point on B or C.

Imagine I have two roadmaps in vector graphics format (bags of line segments) and I want to find places on one map that have no overlapping places on the other map, but I can't compare the line segments one to one because they are chopped up into line segments differently.

  • $\begingroup$ I'm not exactly sure what you are looking for, but the maximum distance between two points, each on a line segment, will occur between two end-points, so at worst you need to check four distances. $\endgroup$
    – copper.hat
    Dec 19 '12 at 23:24
  • $\begingroup$ I think I see better what you're going for. I'll try to have a go at it. $\endgroup$
    – coffeemath
    Dec 20 '12 at 20:25

What I was looking for is called Hausdorff Distance. It is described well in this paper:



For each pair of intetrvals $(I,J)$ with $I \in A$ and $J \in B$, compute the four squared distances between each endpoint of $I$ and each endpoint of $J$, and let the maximum of these four squared distances be called $m(I,J)$. Now for each fixed $I$ find the minimum of the numbers $m(I,J)$ and call that $f(I)$. Then $f(I)$ is the square of the score for interval $I$. The interval $I$ with the largest value of $f(I)$ is in some sense the "worst" of the intervals $I \in A$, and a similar thing can be done for each fixed $J \in B$, to find the "worst" of the intervas $J \in B$.

The suggestion to use squared distances is made since some programming situations have trouble with accuracy on comparing squareroots of decimal numbers.

The fact that max distance between a particular $I$ and $J$ occurs at an endpoint is fairly easy to see by making a few pictures.

By the way I just noticed that copper.hat in a comment made the same remark about the max distance occuring at an endpoint.

  • $\begingroup$ Thanks for the answer, but it doesn't exactly solve the problem I have. I've added more to the question to make it clearer. $\endgroup$ Dec 20 '12 at 18:24
  • $\begingroup$ Actually, your answer is useful because it is an upper bound on the answer. $\endgroup$ Dec 20 '12 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.