如果我知道一个点周围的所有线，如何找到覆盖多边形
How to find the covering polygon if I know a point all the lines around it
我的图表中有一组线条，我也有一个观点。我想要的是一组线，它们将通过有序遍历一起形成一个多边形。我不需要实现或我想要的只是有人指导我使用我可以使用的算法。
有人问过类似的问题，但对我不起作用，因为
一个常见的问题是，给定一个多边形，我需要确定该点是否位于其中，但这对我不起作用，因为我没有任何多边形，我只有一个集合行。
最终的多边形也可能是凸面的，因此简单地从该点在每一侧绘制光线并找到交点是行不通的，我需要更高级的东西。
抱歉造成所有混淆：为了清楚起见，请参阅此内容https://ibb.co/nzbxGF
您需要将段集合存储在合适的数据结构中。即，选择的数据结构应该支持faces, as you're looking for a way to find the face in which a given point resides. One such data structure is the Doubly Connected Edge List的概念。
双向连接边列表是一种数据结构，包含平面的细分。特别是，它包含细分的每个面、边和顶点的记录。它还支持逆时针绕着脸走动，这使您可以知道哪些部分绑定了特定的脸（例如包含您正在搜索的点的脸）。
例如，您可以使用 Sweep Line Algorithm to construct the Doubly Connected Edge List in O(nlog(n)+klog(n)) where n is the number of segments and k is the complexity of the resulting subdivision (the total number of vertices, edges, and faces). You don't have to code it from scratch as this data structure and its construction algorithm have already been implemented many times (you can use CGAL's DCEL implementation。
使用双连接边列表数据结构，您可以通过应用您在 post 中建议的方法来解决您的问题：给定一个输入点，为每个面解决 Point in Polygon problem双连接边列表和 return 包围您找到的面的线段集。然而，这种方法虽然对于一些简单的细分可能足够好，但对于复杂的细分来说效率不高。
更好的做法是将Doubly Connected Edge List转化为专门用于点位置查询的数据结构：The Trapezoidal Map. This data structure can be constructed in O(nlog(n)) expected time and for any query point the expected search time is O(log(n)). As with the Doubly Connected Edge List, you don't have to implement it yourself (again, you can use CGAL's Trapezoidal Map implementation).
我的图表中有一组线条，我也有一个观点。我想要的是一组线，它们将通过有序遍历一起形成一个多边形。我不需要实现或我想要的只是有人指导我使用我可以使用的算法。 有人问过类似的问题，但对我不起作用，因为
一个常见的问题是，给定一个多边形，我需要确定该点是否位于其中，但这对我不起作用，因为我没有任何多边形，我只有一个集合行。
最终的多边形也可能是凸面的，因此简单地从该点在每一侧绘制光线并找到交点是行不通的，我需要更高级的东西。
抱歉造成所有混淆：为了清楚起见，请参阅此内容https://ibb.co/nzbxGF
您需要将段集合存储在合适的数据结构中。即，选择的数据结构应该支持faces, as you're looking for a way to find the face in which a given point resides. One such data structure is the Doubly Connected Edge List的概念。
双向连接边列表是一种数据结构，包含平面的细分。特别是，它包含细分的每个面、边和顶点的记录。它还支持逆时针绕着脸走动，这使您可以知道哪些部分绑定了特定的脸（例如包含您正在搜索的点的脸）。
例如，您可以使用 Sweep Line Algorithm to construct the Doubly Connected Edge List in O(nlog(n)+klog(n)) where n is the number of segments and k is the complexity of the resulting subdivision (the total number of vertices, edges, and faces). You don't have to code it from scratch as this data structure and its construction algorithm have already been implemented many times (you can use CGAL's DCEL implementation。
使用双连接边列表数据结构，您可以通过应用您在 post 中建议的方法来解决您的问题：给定一个输入点，为每个面解决 Point in Polygon problem双连接边列表和 return 包围您找到的面的线段集。然而，这种方法虽然对于一些简单的细分可能足够好，但对于复杂的细分来说效率不高。
更好的做法是将Doubly Connected Edge List转化为专门用于点位置查询的数据结构：The Trapezoidal Map. This data structure can be constructed in O(nlog(n)) expected time and for any query point the expected search time is O(log(n)). As with the Doubly Connected Edge List, you don't have to implement it yourself (again, you can use CGAL's Trapezoidal Map implementation).