在边/顶点列表中找到所有不重叠的多边形 [英] Find all non-overlapping polygons in a list of edges/vertices

问题描述

我有一个边列表和一个顶点列表.每个边引用两个顶点，每个顶点维护一个边列表.

I have a list of edges and a list of vertices. Each edge references two vertices, each vertex maintains a list of edges.

我想找到这张图产生的所有不重叠的多边形.

I want to find all non-overlapping polygons produced from this graph.

一个例子是

0,0)(4,0)(4,2)(4,4)(2,4)(2,2)(4,2)(6,2)(6,6)(0， 6)(0,0)

0,0) (4,0) (4,2) (4,4) (2,4) (2,2) (4,2) (6,2) (6,6) (0,6) (0,0)

此路径应描述在某些顶点上发生碰撞的每个唯一边.在实际图中，顶点是不同的.我需要从这个集合中获得的两个多边形是(0,0)(4,0)(4,2)(2,2)(2,4)(4,4)(4,2)(6,2) (6,6)(0,6)和(2,2)(2,4)(4,4)(4,2)

This path should describe each unique edge with collisions on some verticies. In the actual graph, the vertices are distinct. The two polygons I would need from this set are (0,0) (4,0) (4,2) (2,2) (2,4) (4,4) (4,2) (6,2) (6,6) (0,6) and (2,2) (2,4) (4,4) (4,2)

推荐答案

好吧，我在想...

唯一感兴趣的顶点是具有两个以上边缘的顶点.要查找具有两个以上边缘的所有顶点，则为O(n).然后找到最闭合的闭环与找到给定边线与给定顶点上另一边线之间的最小theta相同(如果顶点为ccw，则这是从当前边沿顺时针方向最小的角度).为了找到所有最紧密的闭环，我需要在边数大于2的顶点处检查所有边ccw边对.这是跟踪的初始化.从这一点开始，轨迹将始终沿顺时针方向选择具有最小theta的下一个边缘.返回路径后，我将移至根顶点中的下一个边对，然后再次路径.选中所有对之后，我将移至边数大于2的下一个顶点.现在，如果我只能确定我是否陷入了已知的循环中而无法追踪.也许如果路径的前两个顶点以相同的顺序出现在已知的多边形中...

The only vertices of particular interest are ones with more than two edges. To find all vertices with more than two edges is O(n). Then to find the tighest closed loop is the same as finding the smallest theta between a given an edge and another edge at a given vertex (if the vertices are ccw, this is the smallest angle clockwise from the current edge). In order to find all tightest closed loops, I need to check all edge ccw edge pairs at a vertex where the edge count is greater than 2. This is the initialization of the trace. From that point on, the trace will always pick the next edge with the smallest theta clockwise. Once the path is returned, I move to the next edge pair in the root vertex, and path again. Once all pairs are checked, I move to the next vertex with an edge count greater than 2. Now, if I can only determine if I am falling into a known loop and not trace. Maybe if the first two vertices of a path occur in the same order in an already known polygon...

听起来如何?我知道这不是djikstra，但是它会起作用，并且希望比发现所有周期的蛮力都快.

How does that sound? I know it's no djikstra, but it will work, and hopefully faster than finding all cycles brute force.

这篇关于在边/顶点列表中找到所有不重叠的多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！