The problem is to find the closest features between two 2d concave polygons. The features can be vertex, edge. So result can be any combination of features. Is there any simple solution with complexity better than O(m*n)? where m, n - number of edges of polygons respectively. The polygons are coplanar.
Asked
Active
Viewed 896 times
3
-
What is `n`, here? Are the polygons coplanar? – cheeken Feb 16 '12 at 22:58
-
corrected complexity formula. – innochenti Feb 16 '12 at 23:02
-
What is `n`? Isn't the number of polygons always 2? – Alex Churchill Feb 16 '12 at 23:09
-
Oh, I see. `m` is the number of edges/vertices of the first, `n` is the number of the second. – Alex Churchill Feb 16 '12 at 23:12
-
What is meant by "closest features"? – Patrick Lorio Feb 16 '12 at 23:15
-
@Patrick he is asking for minimum L2 distance between the (potentially concave) polygonal sets. – Alex Churchill Feb 16 '12 at 23:16
-
Hmm... if you just care about vertices, you can do in O(n log m + m log n) -- see http://www.sciencedirect.com/science/article/pii/0167865583900417. You could always find two pairs of closest vertices, then only work with the edges between the two in the polygons, but since they are concave, that number could still be O(m), but for most cases, you would be O(m log n + n log m). – Alex Churchill Feb 16 '12 at 23:20
-
@alex c unfortunately, I don't have access to sciencedirect – innochenti Feb 17 '12 at 11:51
-
Glad to see @IOranger found it elsewhere. That's his first link -- same paper. – Alex Churchill Feb 20 '12 at 23:03
1 Answers
1
An algorithm in O(n.log(m)) seems to exists, please see this paper, and this question.
An optimization of mine you could try: (not tested)
If your polygons are most of the time far apart enough, you can build the two convex hull and fall back on the easiest problem of finding the Hausdorff distance between two convex polygons (solution in O(n+m)). If the distance is 0, you have to fall back to the O(m.log(n)) case, but it's worth it if you are most of the time in the "convex hull" case with a positive distance.
Post-Scriptum. I just realized that in order of the postulate to work, you also need to check that the closest features from the convex hulls belongs to the original concave polygon. If not, it's easy to find a counter-example (imagine a polygon in shape of the letter C with another round just nearby: CO).
The updated postulate is then: The Hausdorff distance d between two concave polygons is the Hausdorff distance between their convex hulls, if d > 0, and both closest features are part of the original polygons.
The proof of this is left as an exercice to the reader.
Community
- 1
- 1
Laurent Grégoire
- 4,006
- 29
- 52
-
Unfortunately, at least in the pathological case, I'm fairly sure this postulate implies that this approach will never be better than O(mn). Imagine the following setup: we have {(0, 0.1)} and {(-1, 0), (a, -0.5), (1, 0)} for all a = -n to n, a not equal to 0. Then (-1, 0) and (1,0) are the closest points via the convex approach, but the true closest point is on the opposite side of the convex hull (and is actually the farthest edge from the two closest vertices). That said, the convex hull approach is almost always a good approximation. – Alex Churchill Feb 20 '12 at 23:12
-
Yes, that was the point of my remark: *belongs to the original concave polygon*. And if you have this, the case you expose is covered, falling back on the `O(m.log(n))` case (and not `O(nm)`). My optimization will obviously not bring anything if you happen to be *always* in the *pathological* case, but as experience shows, lots of the time in real data you have to support pathological cases less than few percents of the time -- but still you have to support it. – Laurent Grégoire Feb 22 '12 at 07:58
-
Your analysis is completely right for the problem of arbitrary (possibly concave) vertices, however remember that the `O(m log(n))` -- or more precisely the `O(m log(n) + n log(m))` -- case doesn't deal with edges, but rather discrete sets (equivalent to vertices). My pathological case is designed such that the closest feature would be an edge -- and I'm not aware of an `O(m log(n))` algorithm for nondiscrete concave sets. – Alex Churchill Feb 22 '12 at 22:53