我的图表中有一组线条，我也有一点。我想要的是一组线，它们将通过有序的遍历一起形成一个多边形。我不需要实现或任何我想要的只是有人指导我使用我可以使用的算法。有人问过类似的问题，但对我不起作用，因为
一个常见的问题是，给定一个多边形，我需要找出点是否在其中，但这对我不起作用，因为我没有任何多边形，我只有一组线。
最终的多边形也可以是凸的，所以简单地从该点在每一侧绘制光线并找到交叉点是行不通的，我需要更高级的东西。
抱歉所有的混乱：为了清楚起见，请参阅此https://ibb.co/nzbxGF
问问题
90 次
1 回答
2
您需要将您的段集合存储在合适的数据结构中。也就是说，选择的数据结构应该支持faces的概念，因为您正在寻找一种方法来找到给定点所在的面。一种这样的数据结构是双向连接边列表。
双连通边列表是一种数据结构，它包含平面的细分。特别是，它包含细分的每个面、边和顶点的记录。它还支持逆时针绕着一张脸走，这样您就可以知道哪些片段绑定了一张特定的脸（例如包含您正在搜索的点的脸）。
您可以使用扫描线算法来构建双向连接边列表，O(nlog(n)+klog(n))其中n是分段数，k是生成的细分的复杂度（顶点、边和面的总数）。您不必从头开始编写代码，因为这个数据结构及其构造算法已经实现了很多次（例如，您可以使用CGAL 的 DCEL 实现）。
使用双连通边列表数据结构，您可以通过应用您在帖子中建议的方法来解决您的问题：给定一个输入点，为双连通边列表中的每个面解决多边形中的点问题并返回一组包围您找到的人脸的片段。然而，这种方法虽然对于一些简单的细分可能足够好，但对于复杂的细分来说效率不高。
更好的方法是将双连通边列表转换为专门用于点位置查询的数据结构：梯形图。该数据结构可以在O(nlog(n))预期时间内构建，对于任何查询点，预期搜索时间为O(log(n))。与双连通边列表一样，您不必自己实现它（同样，您可以使用CGAL 的梯形图实现）。
于 2017-03-26T17:34:26.230 回答