我如何组合复杂的多边形？ [英] How do I combine complex polygons?

问题描述

给定两个多边形：

  POLYGON（（1 0，1 8，6 4，1 0））
（POLYGON）（（4 1，3 5，4 9，9 5，4 1），（4 5，5 7，6 7，4 4，4 5））
  pre> 
 
 
如何计算联合（合并多边形）？ 
 
 
  
 
 
 
  Dave的例子使用SQL服务器来产生联合，但我需要在代码中完成同样的工作。我正在寻找任何暴露实际数学的语言的数学公式或代码示例。我试图制作将国家动态地结合到地区的地图。我在这里问了一个相关的问题：分组地理形状 
解决方案
这是一个非常好的问题。前段时间我在c＃上实现了相同的算法。该算法构造两个多边形的共同轮廓（即，构造无孔的联合）。这是它。
 
 
 
 
 
 
  
 
 
 
第1步。创建描述多边形的图形。
 
 
 
输入：first多边形（n个点），第二个多边形（m个点）。输出：图形。顶点 - 多边形的交点。 
 
 
 
我们应该找到十字路口。遍历两个多边形中的所有多边形边[O（n * m）]并找到任何交点。 
 
 
 
 
 
 
如果找不到交点，只需添加顶点并将它们连接到
。如果找到任何交点，按长度排列它们的起点，添加所有
顶点（起点，终点和交点）并将它们连接起来（已经以
排序顺序）到边缘。 
  
 
 
 
 
 
 
第2步。检查构造图
 
 
 
如果我们在构建图时没有找到任何交点，我们有下列情况之一：  
 
 
 
 
 Polygon1包含polygon2  -  return polygon1 
 
 
 Polygon2包含polygon1  -  return polygon2 
 
 
 Polygon1和polygon2不相交。返回多边形1和多边形2。第3步：找到左下角的顶点。 
 
 
找到最小的顶点x和y坐标（minx，miny）。然后找到（minx，miny）和多边形点之间的最小距离。这一点将是左下角的一点。 
 
 
 
  
 
 
 
第4步：构造常见的轮廓线。
 
 
 
我们从左下角开始遍历图形，直到返回进去。在开始时，我们将所有边缘标记为未访问。在每次迭代中，您应该选择下一个点并将其标记为已访问。 
 
 
 
要选择下一个点，请选择逆时针方向最大内角的边。
 
 
 
我计算了两个矢量：vector1用于当前边缘，vector2用于每个下一个未访问边缘（如图所示）。 
 
 
对于向量，我计算：
 
 
标量产品（点积）。它返回一个与矢量之间的角度相关的值。 
 
 
向量产品（跨产品）。它返回一个新的向量。如果这个
向量的z坐标是正的，则标量乘以逆时针方向以
给出直角。否则（z坐标为负值），I 
计算矢量之间的角度，作为标量
乘积的360°角。
 
 
 
 
因此，我得到一个最大角度的边（和一个对应的下一个顶点）。  
 
 
我将结果列表添加到每个传递的顶点。结果列表是联合多边形。 
  
 
 
 
备注
 
 
 
 
 
这个算法允许我们合并多个多边形 - 到
迭代地应用多边形对。
 
 
如果您有一条由许多贝塞尔曲线和线组成的路径，您应该首先将这条路径拉平。
 
 
 
Given two polygons:
POLYGON((1 0, 1 8, 6 4, 1 0))
POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5))
How can I calculate the union (combined polygon)?



Dave's example uses SQL server to produce the union, but I need to accomplish the same in code. I'm looking for a mathematical formula or code example in any language that exposes the actual math. I am attempting to produce maps that combine countries dynamically into regions. I asked a related question here: Grouping geographical shapes
解决方案
This is a very good question. I implemented the same algorithm on c# some time ago. The Algorithm constructs a common contour of two polygons (i.e. Constructs a union without holes). Here it is.





Step 1. Create graph that describes the polygons.

Input: first polygon (n points), second polygon (m points). Output: graph. Vertex - polygon point of intersection point. 

We should find intersections. Iterate through all polygon sides in both polygons [O(n*m)] and find any intersections. 


If an intersection is not found, simply add vertices and connect them
to the edge. 
If any intersections are found, sort them by length to their start point, add all 
vertexes (start, end and intersections) and connect them (already in 
sorted order) to the edge.



Step 2. Check constructed graph

If we did not find any intersection points when graph was built, we have one of the following conditions:

Polygon1 contains polygon2 - return polygon1
Polygon2 contains polygon1 - return polygon2
Polygon1 and polygon2 do not intersect. Return polygon1 AND polygon2. 


Step 3. Find left-bottom vertex.

Find the minimum x and y coordinates (minx, miny). Then find the minimum distance between (minx, miny) and the polygon's points. This point will be the left-bottom point. 

 

Step 4. Construct common contour.

We start to traverse the graph from the left-bottom point and continue until we get back into it. At the beginning we mark all edges as unvisited. On every iteration you should select the next point and mark it as visited. 

To choose the next point, choose an edge with a maximum internal angle in counter-clockwise direction.

I calculate two vectors: vector1 for current edge and vector2 for each next unvisited edge (as presented in the picture).

For vectors I calculate:

Scalar product (dot product). It returns a value related to an angle between vectors. 
Vector product (cross product). It returns a new vector. If z-coordinate of this
vector is positive, scalar product gives me right angle in
    counter-clockwise direction. Else (z-coordinate is negative), I
    calculate get angle between vectors as 360 - angle from scalar
    product.
As a result I get an edge (and a correspond next vertex) with the maximum angle. 

I add to result list each passed vertex. Result list is the union polygon.


Remarks


This algorithm allows us to merge multiple of polygons - to
apply iteratively with polygon's pairs.
If you have a path that consists of many bezier curves and lines, you should flatten this path first.


                        
这篇关于我如何组合复杂的多边形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！