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

我想我的问题与"凸壳"有关,但不一样.图中的所有形状都是具有相同宽度和高度的矩形.许多人彼此相邻.我想将那些相邻的矩形组合成多边形.与"凸包"不同,被修复的多边形可能在内部是"空心的".

有没有可用的开源算法？

我必须编写一个算法来合并相邻的多边形,作为HTML5画布的实验项目的一部分(没有任何光荣,一个拼图游戏:-)自然支持生成的多边形中的孔.Javascript例程位于www dot raymondhill dot net/puzzle-rhill/jigsawpuzzle-rhill-3 dot js中名为Polygon.prototype.merge()的函数中.

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

合并算法收集Segment对象的大型胖池中的所有段,其中消除了重复项.首先,将定义Polygon A的所有轮廓的所有线段添加到池中.然后,定义Polygon B的所有轮廓的所有段都被添加到池中,但我们测试并删除重复(使用Point对象作为hashkey轻松完成).

然后我们从池中取一段(随机都很好),我们"走"它直到我们达到"死胡同",也就是说,不再连接任何段.这形成一个Contour对象.我们重复,直到使用了整个分段集合.使用段时,它们将从池中删除."走"一段表示我们采用它的终点,我们查找一个与起点匹配的段.

如上所述,因此我们有一组定义Polygon的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

当我们"走"段以创建轮廓时,有一种情况是段可以连接到多个段:

+------+-------+
|   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 |
|              | |        |
|              + +----<---+
|              |
|              |
+------<-------+


希望这有帮助.

PS:您可以使用拼图游戏"测试"算法,将棋子拼凑在一起以生成洞等.: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