确定工会多边形的原边 [英] Identifying the original edge of a union polygon

问题描述

我有很多面的，以后我做所有这些多边形的工会，我得到一个新的，大的多边形。工会的算法是一个黑盒子，使用第三方库的过程中，这是我无法控制的，我也不能希望提取信息的任何一种进步。

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.

编辑：小npolygons可以重叠，所以联合多边形可以包含位于的小多边形的边点，但这些点可能不是原来多边形的顶点。

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:

推荐答案

下面是一个解决方案。

每次取原边。它们可以是（超过）由以下三个因素规定的：

Take each original edge. They can be (over)specified by 3 things:

1. 在一个向量表示方向
2. 起点
3. 在终点

的第一步是正常化矢量（如由标量乘，使得在绝对值较大X 和是 1）。然后所有的边缘存储到一个哈希的键是那些向量，其值与向量边的数组。 （如果你有一个的很多的边缘，你可能会考虑使用区间树为边缘。）

The first step is to normalize the vectors (eg multiply by a scalar so that the larger in absolute value of x and y is 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.

这篇关于确定工会多边形的原边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！