我猜我的问题与“凸包”有关，但并不完全相同。图中的所有形状都是具有相同宽度和高度的矩形。许多矩形是相邻的。我想将这些相邻的矩形组合成多边形。与“凸包”不同，结果的多边形可能在内部是空心的。
是否有任何开源算法可用？
8个回答
13
我不得不编写一个算法来合并相邻的多边形，作为使用HTML5画布进行实验项目的一部分（没有什么光荣的，就是一个拼图游戏 :-) ）。结果多边形中的孔自然得到支持。Javascript例程可以在www点raymondhill点net / puzzle-rhill / jigsawpuzzle-rhill-3点js中的名为Polygon.prototype.merge()的函数中找到。
关键是删除重复但方向相反的线段。简单解释：一个点是{x:?,y:?}，一个线段是{ptA:?,ptB:?}，一个轮廓是{pts:[]}（连接的点对象集合），一个多边形是{contours:[]}（轮廓对象集合）。
合并算法将所有线段收集到一个大的Segment对象池中，其中消除了重复项。首先，将定义多边形A的所有轮廓的所有线段添加到池中。然后，将定义多边形B的所有轮廓的所有线段添加到池中，但我们会测试并删除重复项（使用Point对象作为哈希键很容易实现）。
然后我们从池中取出一段（随机的也可以），并“走”它直到我们到达一个“死路”，也就是说，没有更多的段可以连接。这形成了一个轮廓对象。我们重复这个过程，直到整个段集合被使用完为止。当使用段时，它们会从池中移除。“走”一段意味着我们取其端点，并查找起点匹配的段。
正如所说，结果我们有了一组定义多边形的轮廓对象。一些轮廓将被填充，一些可能为空心的。确定轮廓是填充还是空心只是测试轮廓是顺时针还是逆时针，或者它的面积是正还是负的问题。在我的情况下，顺时针轮廓是填充的，逆时针轮廓是空心的。
这是我的实现，去掉了具体细节和错误处理。希望我复制/粘贴的足够让您立即使用，否则请参考上面的JS文件以获取上下文：
// Point object
function Point(a,b) {
// a=x,b=y
if (b) {
this.x=a;
this.y=b;
}
// a=Point or {x:?,y:?}
else if (a) {
this.x=a.x;
this.y=a.y;
}
// empty
else {
this.x=this.y=0;
}
}
Point.prototype.toHashkey = function() {
return this.x+"_"+this.y;
};
Point.prototype.clone = function() {
return new Point(this);
};
// Segment object
function Segment(a,b) {
this.ptA = new Point(a);
this.ptB = new Point(b);
}
// Contour object
function Contour(a) {
this.pts = []; // no points
if (a) {
if (a instanceof Array) { // assume array of Point objects
var nPts = a.length;
for (var iPt=0; iPt<nPts; iPt++) {
this.pts.push(a[iPt].clone());
}
}
}
}
Contour.prototype.clone = function() {
return new Contour(this);
};
Contour.prototype.addPoint = function(p) {
this.pts.push(p);
};
// Polygon object
function Polygon(a) {
this.contours = []; // no contour
if (a) {
if (a instanceof Polygon) {
var contours = a.contours;
var nContours = contours.length;
for ( var iContour=0; iContour<nContours; iContour++ ) {
this.contours.push(new Contour(contours[iContour]));
}
}
else if ( a instanceof Array ) {
this.contours.push(new Contour(a));
}
}
}
Polygon.prototype.merge = function(other) {
// A Javascript object can be used as an associative array, but
// they are not real associative array, as there is no way
// to query the number of entries in the object. For this
// reason, we maintain an element counter ourself.
var segments={};
var contours=this.contours;
var nContours=contours.length;
var pts; var nPts;
var iPtA; var iPtB;
var idA; var idB;
for (var iContour=0; iContour<nContours; iContour++) {
pts = contours[iContour].pts;
nPts = pts.length;
iPtA = nPts-1;
for ( iPtB=0; iPtB<nPts; iPtA=iPtB++ ) {
idA = pts[iPtA].toHashkey();
idB = pts[iPtB].toHashkey();
if (!segments[idA]) {
segments[idA]={n:0,pts:{}};
}
segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]);
segments[idA].n++;
}
}
// enumerate segments in other's contours, eliminate duplicate
contours = other.contours;
nContours = contours.length;
for ( iContour=0; iContour<nContours; iContour++ ) {
pts = contours[iContour].pts;
nPts = pts.length;
iPtA=nPts-1;
for (iPtB=0; iPtB<nPts; iPtA=iPtB++) {
idA = pts[iPtA].toHashkey();
idB = pts[iPtB].toHashkey();
// duplicate (we eliminate same segment in reverse direction)
if (segments[idB] && segments[idB].pts[idA]) {
delete segments[idB].pts[idA];
if (!--segments[idB].n) {
delete segments[idB];
}
}
// not a duplicate
else {
if (!segments[idA]) {
segments[idA]={n:0,pts:{}};
}
segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]);
segments[idA].n++;
}
}
}
// recreate and store new contours by jumping from one point to the next,
// using the second point of the segment as hash key for next segment
this.contours=[]; // regenerate new contours
var contour;
for (idA in segments) { // we need this to get a starting point for a new contour
contour = new Contour();
this.contours.push(contour);
for (idB in segments[idA].pts) {break;}
segment = segments[idA].pts[idB];
while (segment) {
contour.addPoint(new Point(segment.ptA));
// remove from collection since it has now been used
delete segments[idA].pts[idB];
if (!--segments[idA].n) {
delete segments[idA];
}
idA = segment.ptB.toHashkey();
if (segments[idA]) {
for (idB in segments[idA].pts) {break;} // any end point will do
segment = segments[idA].pts[idB];
}
else {
segment = null;
}
}
}
};
当我们“走”线段以创建轮廓时，有一种情况是一个线段可以连接到多个线段：
+------+-------+
| Poly A | two segments sharing same start point Z
| |
+ +---<---Z---->---+
| | | Poly B |
| | | |
+ +-------+--------+
| |
| |
+------+-------+--------+
这可能会导致两个有效结果（上述算法将随机导致其中之一）：
结果1，一个填充轮廓：
+------+--->---+
| Poly A |
| |
+ +---<---+---->---+
| | | |
| | | |
+ +--->---+ +
| |
| |
+------+---<---+--------+
结果2，一个填充轮廓，一个空心轮廓：
+------+--->---+
| Poly A |
| |
+ +---<---+---->---+
| | Hole A| |
| | | |
+ +--->---+ +
| |
| |
+------+---<---+--------+
这应该不是问题，因为你的代码已经准备好处理洞。
另一个重要细节是：上面的算法不会去除中间点（“+”），实际上它们是期望的，否则算法将无法工作，就像下面的情况一样：
+------>-------+
| Poly A |
| |
| | +---->---+
| | | Poly B |
| | | |
| | +----<---+
| |
| |
+------<-------+
我的理解是你已经有了这个。我认为算法可以通过预先查找并添加相交点来扩展以支持这种情况（在我的情况下是不必要的）：
+------>-------+
| Poly A |
| |
| + +---->---+
| | | Poly B |
| | | |
| + +----<---+
| |
| |
+------<-------+
希望这可以帮到你。
P.S.：您可以使用拼图来“测试”算法，通过将拼图块拼接在一起生成空洞等等：http://www.raymondhill.net/puzzle-rhill/puzzle-rhill.php?puzzlePieces=16&puzzleComplexity=1&puzzleURL=http://www.public-domain-photos.com/free-stock-photos-4/travel/los-angeles/los-angeles-skyline.jpg&puzzleRotate=0&puzzleVersion=3
- rhill
1
谢谢您的回答，我已经成功地在OpenLayers库中将该算法应用于地图制图上下文。 - Laurent Jégou
5
我建议你研究一下类似于General Polygon Clipper这样的工具。你要做的基本上是联合（或）多边形操作。事实上，它们都是矩形，这使得数学运算变得更容易，但可以很容易地使用GPC等工具完成。此外，该网站提供了许多语言包装器。
- Reed Copsey
1
如果您正在使用空间处理库（如JTS [java]、NTS [.net]或GEOS [c ++]，这些库都是开源的，可用于商业应用程序，不像GPC），则可以将矩形联合起来。
通用的方法是构建输入（矩形）边缘的图形，执行交集，将边缘标记为结果内部或外部，并仅保留外部边缘。我不知道有没有特定的算法来处理矩形，但它可能是类似的，除了数学会更简单。
- codekaizen
0
如果您的边界合理，可以使用二维边缘计数数组，否则必须使用嵌套字典。
因为所有宽度和高度都相同，您可以通过x、y和方向（垂直或水平）的组合唯一地标识边缘。
示例伪代码： list_of_edges = 新列表 arr_count = 新int [] [] []
因为所有宽度和高度都相同，您可以通过x、y和方向（垂直或水平）的组合唯一地标识边缘。
示例伪代码： list_of_edges = 新列表 arr_count = 新int [] [] []
fill_with_zeroes(arr_count )
foreach rect
foreach edge
arr_count [edge.x][edge.y][edge.orientation] += 1
foreach edge in arr_count
if count[edge] = 1
list_of_edges.add(edge]
当然，如果你想要对边进行排序，那么你需要再次遍历数组。
foreach edge in arr_count
if count[edge] = 1
add_recursive(edge)
add_recursive(x,y):
for both horizontal and vertical orientations of edge starting at x, y:
count[edge] = 0
if (edge.orientation is horizontal)
return add_recursive( x+1, y)
else
return add_recursive( x, y+1 )
非常抱歉，这段伪代码写得有些粗糙，但是你应该能够理解大概的意思。
- Jimmy
0
不妨尝试以下方法。如果设计得当，我认为这将起作用。
找到最小的包围矩形，基本上是max-x、min-x和max-y和min-y。这将成为我们绘图的画布。初始化一个2D位数组dx X dy，其中dx、dy是外部矩形的宽度，全部设置为0。
我们的目标是找到轮廓，基本上是一些矩形的角落，以便我们可以将此问题缩小到可以计算处理的级别，一旦我们有了这些点，我们就可以扩大规模以获得实际坐标。
扫描上述2D数组，并在其中标记一个点1，如果它包含在给定的一个矩形中。
现在扫描2D数组，并查找其邻域具有3:1分割的点，即在3个方向上具有1，而在一个方向上具有0或反之亦然。这些点将定义轮廓。
我认为，如果我们明智地缩小问题的规模，复杂性将是可管理的。
- Anil
0
我找到了一种更简单的方法：
- 创建一个黑色图像。
- 在图像上用白色填充矩形。这样所有重叠的矩形都将连接在一起。
- 查找斑点的轮廓。
就是这样！
- TeckWee
0
我曾经遇到过类似的问题。虽然我不知道你的点是如何对齐的，但我的点总是相隔5米。
我的解决方法是按照x坐标将点排序。
有两个列表，一个叫做previous，另一个叫做current。
如果current为空，则将该点添加到current中。如果current不为空，则检查该点是否与current中的某个点相邻(向后遍历列表，因为最近的点更可能相邻)。
如果该点与current中的任何点都不相邻，则检查current中的任何点是否与previous列表中的任何点相邻。如果是，则合并(concatenate)它们，否则将点从previous移动到另一个保持完整多边形的列表中，然后设置previous=current，清空current，并将正在处理的点添加到current中。
根据您的点如何处理(顺序)，您可能需要再次运行所有最终多边形，以检查它们是否与其他多边形相邻。
抱歉内容比较长，请让我知道你是否想编写代码，它是用C#编写的，而且不是非常干净。
- Kennedine
-1
简单地测试矩形是否相交，然后在它们的点的并集上运行凸包算法。
或者您也可以手动测试矩形的哪一侧相交，并按正确的顺序将点添加到多边形对象中。
这些假设封闭的多边形足以满足要求（不能有洞）。
- Ben S
1
如果他想保留空洞，那么这样做是行不通的。想象一下有一个3x3的矩形块，但中心矩形缺失 - 凸包将填充它。 - Reed Copsey
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接