|
1
4
求包含所有m+n点的最小面积的凸多边形。说到这里,请查看
http://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/ 格雷厄姆扫描: http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
|
|
|
2
3
为了获得有效的解决方案,可以采用单调链方法( https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain )具体如下:
总运行时间由以下因素决定:
因此,复杂度为O(n+m),这不是最优的,但对于您的目的来说可能已经足够好了(当多边形不重叠时,可以使用更复杂的O(Log(n+m)解决方案,但对于较小的多边形大小来说,不值得大惊小怪)。
在本例中,合并的结果只是链的串联,但可能会出现更复杂的情况。
|
|
|
3
0
找到这两个集的凸包可行,但以下方法可能更快,因为它只需要按顺序访问多边形顶点:
|
|
|
user1255410 · 生成外凸多边形 9 年前 |
|
|
Cheva · 以百分比调整矩形大小,同时保持其纵横比 9 年前 |
|
|
A. Bykov · 将两个凸的不相交多边形合并为一个 9 年前 |
|
|
Paul Reiners · 从给定集合中找到具有最大点密度的最小圆 9 年前 |
|
|
praveen kr · 找出一个点属于哪个四面体元素 9 年前 |
|
|
Bernardo Marques · 计算两个多边形之间的9相交矩阵 11 年前 |
|
|
Simon Kuang · 计算到多个点的最小距离地图 11 年前 |