最好算法找到顶点的边缘（多边形） [英] Best Algorithm to find the edges (polygon) of vertices

问题描述

我有一个大阵顶点，其中有些是边缘的，有些是多余的（里面的造型），我想删除这些文件。

I have a large array of vertices, some of them are edges, some are redundant (inside the shape) and I want to remove those.

最简单的算法，我能想到的一个检查之一，如果他们打的人形成的形状。但是，它应该是一个非常缓慢的算法。

The simplest algorithm I could think of is checking one by one if they hit the shape formed by the others. But it should be a very slow algorithm.

我想到了从边缘（每例如产地之一最远），选择其中的一个，并从这个开始计算最长路径......应该得到的边缘的路径，对吧？

I thought about picking one from the edge (the one farthest from origin per example) and calculate the longest path from this start... should get the edge path, right?

任何建议？

推荐答案

与多面体算法诀窍是选择一个与你的输入和所需输出适合，因为是重新present多面体的方法不止一种和重新presentations之间转换可以是昂贵的。在这种情况下，您从开始点，并希望结束与顶点，所以 Graham扫描算法计算凸包应该做的伎俩的顶点，尽管它可能需要一些努力扩大它过去的2-D的情况下。这是O（ñ日志N 的）输入顶点的数量。

The trick with polyhedral algorithms is choosing one that fits with your input and your desired output, since there is more than one way to represent a polyhedron and converting between the representations can be expensive. In this case, you are starting with points and want to end with vertices, so the Graham scan algorithm to compute the vertices of the convex hull should do the trick, though it might take some effort to extend it past the 2-D case. It's O(n log n) in the number of input vertices.

这篇关于最好算法找到顶点的边缘（多边形）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！