Lau*_*t K 26 language-agnostic algorithm geometry polygon
我有一组S点(2D:由x和y定义),我想找到P,最小的(意思是:具有最小的点数)多边形包围集合的所有点,P是有序的子集S.
有没有任何已知的算法来计算它？(我在这个领域缺乏文化是令人惊讶的...)
谢谢你的帮助
Ral*_*ach 30
这个问题有很多算法.它被称为" 最小边界框 ".你会发现寻找" 凸壳 "的解决方案,特别是在这里.
一种方法是找到最左边的点然后重复以搜索所有其他点位于线p(n-1)p(n)右侧的点.
Eva*_*ers 6
这是一个简单的解决方案......
从任意三个点开始形成三角形.使用以下操作将每个附加点添加到多边形:
将边分成两条连续的路径,其中在一条路径中,每条边的线将要添加的点与多边形的其余部分分开(让我们称之为"分离路径"),在另一条路径中,每条边的线分开该点与多边形位于同一侧.
(注意:只要你的形状保持凸起,它必须是这样,这两条路径将是连续的并形成整个形状)
如果分离路径没有边,则该点位于多边形内部,应忽略,否则,从多边形中移除分离路径.将其替换为两段,将分离路径的每个端点连接到新点.
当当!:)
归档时间：
16 年，7 月 前
查看次数：
29217 次
最近记录：