3

我有一组坐标组成一个二维多边形。坐标是有序的,并确定了多边形的绘制方式。

对于另一个具有比第一个顶点更多的顶点的二维多边形,我有一个类似的坐标数组。

假设两个多边形在 2D 空间中彼此居中。

如何找到从较小形状“匹配”到较大形状的哪些顶点,同时保持多边形的顺序一致?匹配基于顶点从一个多边形到下一个多边形的接近程度。

0____________1
|------------|
|------------|
|------------|
3____________2

------0---------
-----/-\--------
---1/---\____6--
---|----7----|--
---|------4__|--
---|-------\-5--
---2________3---

EX solution:
0 : Null
1 : 0
2 : 3
3 : 2
4 : Null
5 : Null
6 : 1
7 : Null

我已经为这个问题苦苦挣扎了一个多星期,并且可以使用一些帮助。谢谢。

4

1 回答 1

1

该问题可以表示为试图在第一个多边形中的顶点和第二个多边形中的顶点之间找到最小成本的最大匹配,并增加了不相交边的要求。

这篇论文应该会有所帮助:http ://home.deib.polimi.it/malucell/papers/NCM.pdf

于 2013-05-26T14:16:28.623 回答