Consider two 3D polylines, A and B. I am interested in computing a distance/similarity between them (from their current positions, no need to find the "best overlap" first). I have come up with some reasonable approximations (average distance between all points on A to their closest points on B, etc.), but I am surprised to have not been able to find any algorithms that do this more formally. I often seen the Frechet distance (see https://mathoverflow.net/a/199742), but I don't want a maximal distance like that, but rather a "total" distance. It seems to me like we should be trying to find the surface between A and B and finding its area, but I haven't seen any algorithms described that do that. Has anyone seen something like this?

enter image description here

  • $\begingroup$ One problem is that two polylines in 3D don't define a unique surface. Another problem is that, even in the plane where the "area between" is well-defined, if A and B are parallel line segments (e.g. - -) then the area between them is zero no matter how far apart they are. $\endgroup$ – Rahul May 27 '16 at 13:03
  • $\begingroup$ @Rahul Sure, agreed. However, there are plenty of use cases where those "degeneracies" are not expected. The "minimum area" surface would be the surface of interest in the non-degenerate cases, and the area of this surface is exactly what I'm looking for :) $\endgroup$ – David Doria May 27 '16 at 13:05
  • $\begingroup$ Any reason why you're not happy with your "average distance to closest points" idea? You could make it symmetric and invariant to reparametrization/subdivision by using $\frac12 (\int_{a\in A} d(a,B)\,\mathrm d\ell + \int_{b\in B} d(b,A)\,\mathrm d\ell)$ instead, which is equal to the "area between $A$ and $B$" for some simple cases (e.g. two edges of a rectangle). $\endgroup$ – Rahul May 27 '16 at 13:18
  • $\begingroup$ @Rahul The average distance doesn't consider the length of the curves. The sum of the distances is sensitive to the sampling rates unless you divide by the length of one of the curves or something, but it just seems a little loose/informal. That integral is exactly what I want, but determining the pairs and section of line segments on which to compute it is the tricky part that I was hoping that someone had already figured out a procedure for. $\endgroup$ – David Doria May 27 '16 at 13:33

Your Answer

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

Browse other questions tagged or ask your own question.