geometry - 将相邻矩形合并为多​​边形的算法

Question

我想我的问题与“凸包”有关，但不一样。图中的所有形状都是具有相同宽度和高度的矩形。许多彼此相邻。我想将这些相邻的矩形组合成多边形。与“凸包”不同，生成的多边形内部可能是“空心的”。

有没有可用的开源算法？

Answer 1

我不得不编写一个算法来合并相邻的多边形，作为使用 HTML5 Canvas 的实验项目的一部分(没什么好看的，一个拼图游戏 :-) 生成的多边形中的孔自然得到支持。 Javascript 例程位于 www dot raymondhill dot net/puzzle-rhill/jigsawpuzzle-rhill-3 dot js 中名为 Polygon.prototype.merge() 的函数中

关键是删除重复但方向相反的段。粗略解释:A Point 是 {x:?,y:?}，一个 Segment 是 {ptA:?,ptB:?}，一个 Contour 是 {pts:[]}(连接的 Point 对象的集合)，一个 Polygon 是{contours:[]}(Contour 对象的集合。)

合并算法将所有段收集在一个很大的 Segment 对象池中，其中重复项被消除。首先，将定义多边形 A 的所有轮廓的所有段添加到池中。然后，定义多边形 B 的所有轮廓的所有段都添加到池中，但我们测试并删除重复项(使用 Point 对象作为哈希键很容易完成)。

然后我们从池中取出一个段(随机就可以)，我们“走”它直到我们到达一个“死胡同”，即没有更多的段可以连接。这形成了一个 Contour 对象。我们重复，直到使用了整个段集合。使用段时，它们将从池中删除。 “走”一个段意味着我们取它的终点，我们查找一个起点匹配它的段。

如上所述，因此我们有一组定义多边形的 Contour 对象。一些轮廓将被填充，一些可能是空心的。确定一个轮廓是填充的还是空心的只是测试轮廓是顺时针还是逆时针，或者它的面积是正还是负。这是一个约定，在我的情况下，顺时针轮廓填充，逆时针轮廓是空心的。

这是我的实现，减去细节和错误处理。希望我复制/粘贴的内容足以让您立即使用，否则请参阅上面的 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