我有大量的顶点,其中一些是边缘,一些是多余的(形状内部),我想删除它们。
我能想到的最简单的算法是一一检查它们是否撞到了其他人形成的形状。但这应该是一个非常慢的算法。
我考虑从边缘选择一个(每个示例中距原点最远的一个)并计算从这一点开始的最长路径......应该得到边缘路径,对吧?
有什么建议吗?
多面体算法的技巧是选择一种适合您的输入和所需输出的算法,因为表示多面体的方法不止一种,并且在表示之间进行转换可能会很昂贵。在这种情况下,您从点开始并希望以顶点结束,因此格雷厄姆扫描 http://en.wikipedia.org/wiki/Graham_scan计算顶点的算法凸包 http://en.wikipedia.org/wiki/Convex_hull应该可以解决这个问题,尽管可能需要一些努力才能将其扩展到二维情况之外。是奥(n log n) 输入顶点的数量。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)