我想我的问题与"凸壳"有关,但不一样.图中的所有形状都是具有相同宽度和高度的矩形.许多人彼此相邻.我想将那些相邻的矩形组合成多边形.与"凸包"不同,被修复的多边形可能在内部是"空心的".
有没有可用的开源算法？
小智 12
我必须编写一个算法来合并相邻的多边形,作为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<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 之类的工具轻松完成。
那里也有许多语言的语言包装器。
