识别联合多边形的原始边
我有很多多边形，在将所有这些多边形合并后，我得到一个新的大多边形。联合算法是一个黑匣子，使用第三方库过程，我无法控制，我也不希望从进度中提取任何信息。
有没有有效的方法让我知道，对于那个巨大的联合多边形的每条边，其中哪一条属于较小多边形的哪条边？
解决此问题的一种强力方法是将联合多边形的每条边与每个较小的多边形进行比较，但这将非常低效。还有其他更有效的技术吗？
我的直觉告诉我，扫线算法可能会有所帮助，尽管我完全不知道该怎么做它。
编辑：小n多边形可以重叠，因此联合多边形可以包含位于小多边形边缘的点，但这些点可能不是原始多边形的顶点。
其屏幕截图如下所示：
I have a lot of polygons, and after I do a union of all these polygons, I get a new, big polygon. The union algorithm is a black box and using third-party-library process, which I couldn't control, and neither can I hope to extract any information out kind of progress.
Is there efficient way for me to know, for every edge of that big gigantic unionized polygon, which of it is belonging to which edge of the smaller polygon?
A brute force way to solve this problem is to compare every edge of the unionized polygon with each of the smaller polygons, but this is going to be very inefficient. Any other more efficient techniques?
My hunch tells me that sweep line algorithm may help here, although I have absolutely no idea how to do it.
Edit: The small npolygons can overlap, so the union polygon can contain points that are located at the edges of the small polygons, but these points may not be the vertexes of the original polygons.
A screenshot of this is shown below:
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这是一种解决方案。
取出每个原始边缘。它们可以由 3 个东西（过度）指定：
第一步是对向量进行归一化（例如，乘以标量，以便
x的绝对值中较大者和y为 1)。然后将所有边存储到一个散列中，其键是这些向量，其值是具有该向量的边数组。 （如果您有很多边，您可以考虑使用间隔树 对于边。）现在给定组合多边形上的一条边，您可以计算出它的向量，查看散列，并且通常在原始多边形中只有少量具有该精确向量的边，因此浏览它们并找出哪个并不难那些重叠了。
请注意，虽然此解决方案可以让您相当有效地查找边缘沿边界延伸的情况，但它会错过多边形仅在一个角处接触组合多边形边界的情况。希望这对你来说并不重要。
Here is one solution.
Take each original edge. They can be (over)specified by 3 things:
The first step is to normalize the vectors (eg multiply by a scalar so that the larger in absolute value of
xandyis 1). Then store all of your edges into a hash whose keys are those vectors, and whose values are an array of edges with that vector. (If you have a lot of edges, you might consider using an interval tree for the edges.)Now given an edge on the combined polygon, you can figure out its vector, look in your hash, and you'll generally have only a small number of edges in the original polygon with that exact vector, so it isn't too hard to go through them and figure out which ones overlapped.
Note that while this solution will let you fairly efficiently find cases where the edge runs along the boundary, it will miss cases where a polygon just touches the boundary of the combined polygon at one corner. Hopefully that doesn't matter for you.
由于联合中出现了新的边和顶点，这种朴素的方法不起作用（请参阅旧的答案和注释），因此我们需要采用更复杂的数据结构。
这个想法是识别输入集中包含输出集边缘的边缘。我所说的“包含”是指输出集的边的两个顶点都需要位于输入集的边上。因此，我们需要在输入边集中搜索包含一条穿过我们正在考虑的边的两个顶点的线段的边。
过滤掉大量搜索边集的一个简单方法是使用边界框：如果我们正在检查的顶点不在由边的两个顶点形成的边界框内，那么我们可以规则它出去。主要算法为：
输入：输出多边形 E1 的一条边，以 V1 和 V2 作为端点。
输出：输入多边形的一条边，其中 V1 和 V2 都在边上。
第二步是显而易见的。对于第一个，有几个地方需要注意。 KD 树（体积对象）看起来可以解决这个问题。或者可能是 R 树。另请检查 stackoverflow 中的类似问题。不幸的是，我不太熟悉空间算法，无法提出合适的算法。
旧答案：
我认为您不需要任何花哨的数据结构来处理这种情况。我假设联合中顶点的坐标与原始集中顶点的坐标相同。因此，您可以执行以下操作：为输入数据创建一个顶点列表，其中每个顶点记录它所属的多边形。让这些易于搜索：一种简单的方法是首先按一个坐标对它们进行排序，然后再按另一个坐标排序。你可以用这种方式在 O(log n) 中找到任何顶点。
现在，对于联合多边形的任何给定边，搜索该边的第一个顶点，然后搜索另一个顶点。取它们所属多边形的集合交集，即可得到原始多边形。为了加快第二个顶点的搜索速度，您还可以将连接的顶点列表添加到原始列表中，这样就不必再次进行完整搜索。
最后的优化是预计算：只需运行上述算法，并记录每条边的结果，然后删除所有顶点和边表。如果不需要预先计算的表，则可以过滤掉未出现在并集中的顶点的原始顶点集。
Since the naive approach doesn't work because of new edges and vertexes appearing in the union (see the old answer and comments), we will need to employ a more complicated data structure.
The idea is to identify an edge in the input set that contains the edge of the output set. By "contains" I mean both vertexes of the edge from the output set needs to be on the edge from the input set. So, we need to search the input edge set for one that contains a line segment that passes through both vertexes of the edge we are considering.
A simple way to filter out a large number of the edge set for the search is to use bounding boxes: if the vertex we are checking doesn't lie inside the bounding box formed by the two vertexes of an edge, then we can rule it out. The main algorithm, then is:
INPUT: An edge from the output polygon, E1, with V1 and V2 as the end points.
OUTPUT: An edge from the input polygons where both V1 and V2 are on the edge.
Second step is obvious. There are a few places to look at for the first one. A K-D tree (the volumetric object) looks like it would solve the problem. Or maybe an R-tree. Also check stackoverflow for similar questions. Unfortunately, I am not very well-versed in the spatial algorithms to suggest a suitable one.
OLD ANSWER:
I don't think you need any fancy data structures to handle the case. I am assuming that the coordinates of the vertexes in the union are identical to the ones in your original set. So you can do something like: create a list of vertexes for your input data, where each vertex records the polygon(s) it belongs to. Make these easily searchable: a naive approach would be to sort them by one coordinate first, and then the other. You can find any vertex in O(log n) that way.
Now, for any given edge of the union polygon, search for the first vertex of the edge, then search the other. Take the set intersection of the polygons they belong to, and you get the original polygon. To speed up the searching for second vertex, you can also add a list of connected vertexes to the original list, so that you don't do a full search again.
A final optimization is pre-calculation: just run the above algorithm, and record the results for each edge, then get rid of all the vertex and edge tables. If you don't need a pre-calculated table, you can filter out the original vertex set for vertexes that don't appear in the union.
您可以制作BSP，或更具体的四叉树，带有多边形边缘。对于每条边，请记住它在哪个多边形中使用。
对于输出多边形中的每条边，执行树搜索并检查仅与四叉树叶节点中的边重叠的边。
假设原始多边形中有
n条边，输出多边形中有m条边。创建树需要O(n log n)，搜索边的重叠需要O(m log n)。总体O((m+n)*log n)。注意：如果在 2 个初始多边形中使用整条边，则它不在输出多边形边界中。这样您就可以从四叉树中删除重复的边。没有必要。
可以用其他方式实现。创建输出多边形边的四叉树，并搜索初始多边形的每条边。运行时间为
O((m+n)*log m)，速度更快。但是使用上面的方法，如果将来需要的话，您可以从输入多边形中提取更多信息。You can make BSP, or more concrete quadtree, with polygons edges. For each edge remember in which polygon(s) it is used.
For each edge in output polygon perform tree search and check for edge overlapping only with edges in quadtree leaf node(s).
Lets there be
nedges in original polygons, andmedges in output polygon. To create treeO(n log n)is needed and to search overlapping of edgesO(m log n)is needed. OverallO((m+n)*log n).Note: if a whole edge is used in 2 initial polygons than it is not in output polygon boundary. With this you can remove duplicated edges from quadtree. Not necessary.
It is possible to make it other way. Create quadtree of output polygon edges, and search for each edge of initial polygons. Running time is
O((m+n)*log m), which is faster. But with upper approach you can extract more informations from input polygons if you will need it in the future.