I guess that my problem is related to "convex hull", but no the same. All shapes in the drawing are rectangles with same width and height. Many are adjacent to each other. I want to combine those adjacent rectangles into polygons. Unlike "convex hull", the resuled polygons could be "hollow" inside.
Is there any open source algorithm available?
作为 HTML5 画布的实验项目的一部分，我不得不编写一个合并相邻多边形的算法（没什么光彩的，一个拼图游戏 :-) 生成的多边形中的孔自然是受支持的。Javascript 例程位于 www dot raymondhill dot net /uzzle-rhill / jigsawpuzzle-rhill-3 dot js 中名为 Polygon.prototype.merge() 的函数中
关键是删除重复但方向相反的段。粗略解释：一个Point是{x:?,y:?}，一个Segment是{ptA:?,ptB:?}，一个Contour是{pts:[]}（连接的Point对象的集合），一个Polygon是{contours:[]}（Contour 对象的集合。）
合并算法将所有段收集到一个段对象的大胖池中，其中重复项被消除。首先，将定义多边形 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 |
| | | |
| + +----<---+
| |
| |
+------<-------+
希望这有帮助。
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
我会研究像General Polygon Clipper这样的东西。你基本上是在做联合（OR）多边形操作。它们都是矩形的事实只是让数学变得更容易一些，但它可以很容易地用 GPC 之类的东西来完成。
那里也有许多语言的语言包装器。
如果您使用的是空间处理库（如 JTS [java]、NTS [.net] 或 GEOS [c++]，它们都是开源且可用于商业应用程序，与 GPC 不同），您只需合并矩形即可。
执行此操作的通用方法是构建输入（矩形）的边缘图，执行交集，将边缘标记为结果的内部或外部，并仅保留外部边缘。我不知道处理矩形的特定算法，但它可能是相似的，除非如前所述，数学会更简单。
如果您的界限合理，请使用 2D 边数数组，否则您必须使用嵌套字典。
因为所有的宽度和高度都相同，您可以通过 x、y 和方向（垂直或水平）的组合来唯一标识一条边
示例伪代码：list_of_edges = new list arr_count = new 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 )
对不起，这个伪代码很草率，但你应该明白大体的想法
How about trying the following. I think this will work if designed properly.
Find the smallest emclosing rectangle, basically max-x, min-x and max-y and min-y. This will be our canvas for drawing. Initialise a 2D array of bits dx X dy where dx, dy are width of this outer rectangle, to all 0s.
Our objective is to find the contour, basically some corners of the rectangles so we can scale down this problem to a level where we can handle it computationally, once we have the points we can scale up to get the actual coordinates.
Scan through the above 2D array and mark a point 1 if it is contained in one of the given rectangle.
Now scan the 2D array and look for points whose neighbourhood has a 3:1 split, that means on 3 sides it has 1s and on one side 0s or vice versa. These points are those that will define the contour.
I think the complexity will be managiable if we can scale down the problem wisely.
我之前也遇到过类似的问题。我不知道你的点是如何对齐的，但我的点总是彼此间隔 5 米。
我的解决方案是按 x 坐标排序。
有两个列表，一个称为先前列表，一个称为当前列表。
如果当前为空，则将该点添加到当前。如果 current 不为空，则检查该点是否与 current 中的一个点相邻（向后运行列表，因为最近的点相邻的可能性更高）
如果该点与 current 中的任何点都不相邻，则检查 current 中的任何点是否与先前列表中的任何点相邻。如果是，则合并（连接）它们，如果不是，则将点从先前的移动到另一个包含完整多边形的列表，然后设置先前 = 当前，清空当前并将正在处理的点添加到当前。
根据您的点的处理方式（顺序），您可能需要再次运行所有最终多边形以检查它们是否与任何其他多边形相邻。
对不起，长长的文字墙，如果你想编码，请告诉我，它是用 c# 编写的，不是很干净。
我找到了一个更简单的方法：
而已！
只需测试矩形是否接触，然后在它们的点的联合上运行凸包。
或者您也可以手动测试以查看矩形的哪一侧正在接触，然后以正确的顺序将点添加到多边形对象。
这些假设封闭的多边形就足够了（其中不能有孔）。