问题描述
我想我的问题与凸包有关，但不一样。图形中的所有形状都是具有相同宽度和高度的矩形。许多人彼此相邻。我想将这些相邻的矩形组合成多边形。与凸包不同，多余的多边形可能在里面是空心的。是否有任何开源算法可用？
编写一个算法来合并相邻的多边形，作为HTML5 canvas实验项目的一部分（没有什么光荣的，拼图游戏:-)自然支持生成的多边形中的孔。 Javascript例程可以在www dot raymondhill dot net / puzzle-rhill / jigsawpuzzle-rhill-3 dot js中找到名为Polygon.prototype.merge（）的函数。
关键是删除重复但方向相反的段。粗略解释：一个点是{x：？，y：？}，一个段是{ptA：？，ptB：？}，轮廓是{pts：[]}（连接点对象的集合），一个多边形是{Contours：[]}（一个Contour对象的集合）。
合并算法收集一大段Segment对象中的所有段，其中重复项被删除。首先，将定义多边形A的所有轮廓的所有分段添加到池中。然后，定义多边形B的所有轮廓的所有片段都被添加到池中，但我们测试并删除重复（使用Point对象作为hashkey很容易完成）。
然后我们从游泳池中取出一段（随机很好），然后我们走它，直到我们到达死胡同，也就是说，没有更多的段可以连接。这形成一个Contour对象。我们重复，直到整个部分的集合已被使用。随着细分被使用，它们被从池中移除。 走一段意味着我们接受它的终点，并且我们会查找一个起点与它匹配的段。如前所述，因此我们收集了定义多边形的轮廓对象。有些轮廓会被填满，有些可能是空洞的。确定轮廓是否填满或空洞只是测试轮廓是顺时针还是逆时针，或者其面积是正面还是负面。这是一个惯例，在我的情况下，顺时针轮廓被填满，逆时针轮廓是空的。
这是我的实现，减去具体细节和减去错误处理。希望我复制/粘贴足够让你立即工作，否则请参阅我的JS文件上下文： / / Point对象
函数Point（a，b）{
// a = x，b = y
if（b）{
this.x = a;
this.y = b;
}
// a =点或{x：？，y：？}
else if（a）{
this.x = a.x;
this.y = a.y;
}
//空
其他{
this.x = this.y = 0;
Point.prototype.toHashkey = function（）{
return this.x +_+ this.y;
};
Point.prototype.clone = function（）{
return new Point（this）;
};
//段对象
函数段（a，b）{
this.ptA = new Point（a）;
this.ptB = new Point（b）;
}
//轮廓对象
函数轮廓（a）{
this.pts = []; （a）{
if（一个数组的实例）{//假定Point对象的数组
var nPts = a.length;
for（var iPt = 0; iPt< nPts; iPt ++）{
this.pts.push（a [iPt] .clone（））;
$ b Contour.prototype.clone = function（）{
返回新的Contour（this）;
};
Contour.prototype.addPoint = function（p）{
this.pts.push（p）;
};
//多边形对象
函数多边形（a）{
this.contours = []; //没有轮廓
if（a）{
if（多边形的一个实例）{
var contour = a.contours;
var nContours = contours.length;
for（var iContour = 0; iContour< nContours; iContour ++）{
this.contours.push（new Contour（contour [iContour]））;
else if（数组的一个实例）{
this.contours.push（new Contour（a））;
Polygon.prototype.merge = function（other）{
// Javascript对象可以用作关联数组，但
//它们不是真正的关联数组，因为没有办法
//查询对象中的条目数。对于这个
//的原因，我们维护一个元素counterof自己。
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 = contour [iContour] .pts;
nPts = pts.length;
iPtA = nPts-1; （iPtB = 0; iPtB< nPts; iPtA = iPtB ++）{
idA = pts [iPtA] .toHashkey（）;
。
idB = pts [iPtB] .toHashkey（）;
if（！segments [idA]）{
segments [idA] = {n：0，pts：{}};
}
段[idA] .pts [idB] =新段（pts [iPtA]，pts [iPtB]）;
段[idA] .n ++;
}
}
//枚举其他轮廓中的线段，消除重复的
轮廓= other.contours;
nContours = contours.length;
for（iContour = 0; iContour< nContours; iContour ++）{
pts = contour [iContour] .pts;
nPts = pts.length;
iPtA = nPts-1; （iPtB = 0; iPtB< nPts; iPtA = iPtB ++）{
idA = pts [iPtA] .toHashkey（）;
。
idB = pts [iPtB] .toHashkey（）;
//重复（我们在相反方向消除相同的片段）
if（segments [idB]&& segments [idB] .pts [idA]）{
删除片段[idB] .PTS [IDA];
if（！ - segments [idB] .n）{
删除分段[idB];
//不重复
else {
if（！segments [idA]）{
segments [idA] = {n： 0，PTS：{}};
}
段[idA] .pts [idB] =新段（pts [iPtA]，pts [iPtB]）;
段[idA] .n ++;
//通过从一个点跳到另一个点重新创建和存储新轮廓
//使用段的第二个点作为散列下一个分段的关键
this.contours = []; //重新生成新轮廓
var contour;
for（idA in segments）{//我们需要这个来获得新轮廓的起点
contour = new Contour（）;
this.contours.push（等高线）;
for（idB in segments [idA] .pts）{break;}
segment = segments [idA] .pts [idB];
while（segment）{
contour.addPoint（new Point（segment.ptA））;
//从集合中删除，因为它已被使用
删除分段[idA] .pts [idB];
if（！ - segments [idA] .n）{
delete segments [idA];
}
idA = segment.ptB.toHashkey（）;
if（segments [idA]）{
for（idB in segments [idA] .pts）{break;} //任何结束点将执行
segment = segments [idA] .pts [idB前];
}
else {
segment = null;
}
}
}
};
当我们走动该段以创建轮廓时，会出现段可以连接到多个细分市场：
+ ------ + ------- +
| Poly A |两段共享相同的起点Z
| |
++ --- ---< --- Z ----> --- +
| | | Poly B |
| | | |
++ ------- + -------- +
| |
| |
+ ------ + ------- + -------- +
这可能导致两个有效的结果（上面的算法会随机导致一个或另一个）：结果1，一个实心轮廓：
+ ------ + ---> --- +
| Poly A |
| |
++ + ---< --- + ----> --- +
| | | |
| | | |
++ ---> --- + +
| |
| |
+ ------ + ---< --- + -------- +
结果2，一个填充轮廓，一个凹陷轮廓：
+ ----- - + ---> --- +
| Poly A |
| |
++ + ---< --- + ----> --- +
| |孔A | |
| | | |
++ ---> --- + +
| |
| |
+ ------ + ---< --- + -------- +
这应该不是问题，因为你的代码已经准备好处理漏洞了。
其他重要细节：算法上面没有摆脱中间点（'+'），实际上它们是预期的，否则算法将不起作用，如以下情况：
+ ------> ------- +
| Poly A |
| |
| | + ----> --- +
| | | Poly B |
| | | |
| | + ----< --- +
| |
| |
+ ------< ------- +
我的理解是，这就是你所拥有的。我想可以通过预先找到并添加相交点来扩展算法以支持这种情况（在我的例子中这是不必要的）：
+ ------> ------- +
| Poly A |
| |
| + + ----> --- +
| | | Poly B |
| | | |
| ++ + ---- | |
| |
+ ------< ------- +
希望得到这个帮助。
PS：你可以用拼图游戏'测试'算法，通过将棋子咬合在一起来产生洞等。
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?
I had to write an algorithm for merging adjacent polygons as part of an experiment project with HTML5 canvas (nothing glorious, a jigsaw puzzle :-) Holes in the resulting polygon are naturally supported. The Javascript routine is found in the function named Polygon.prototype.merge() in www dot raymondhill dot net / puzzle-rhill / jigsawpuzzle-rhill-3 dot js
The key is to remove segments which are duplicate, but of opposite direction. Rough explanation: A Point is {x:?,y:?}, a Segment is {ptA:?,ptB:?}, a Contour is {pts:[]} (a collection of connected Point objects), a Polygon is {contours:[]} (a collection of Contour objects.)
The merge algorithm collect all segments in a big fat pool of Segment objects, where duplicates are eliminated. First, all the segments of all the contours defining Polygon A are added to the pool. Then, all the segments of all contours defining Polygon B are added to the pool, but we test and remove for duplicate (easily done using a Point object as a hashkey).
Then we take a segment from the pool (randomly is fine), and we "walk" it until we reach a "dead end", that is, no more segment can be connected. This form one Contour object. We repeat until the whole collection of segments has been used. As segments are used, they are removed from the pool. "Walk" a segment means we take its end point, and we look up a segment which start point matches it.
As said, as a result we have a collection of Contour objects which define the Polygon. Some contours will be filled, some might be hollow. To determine whether a Contour is filled or hollow is just a matter of testing whether the Contour is clockwise or counterclockwise, or whether its area is positive or negative. It's a convention, in my case clockwise contours are filled, counterclockwise are hollow.
Here is my implementation, minus the specifics and minus error handling. Hopefully I copied/pasted enough for you to make it work right away, else refer to my JS file above for context:
// 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;
}
}
}
};
When we "walk" the segment to create a contour, there is a case where a segment can connect to more than one segment:
+------+-------+
| Poly A | two segments sharing same start point Z
| |
+ +---<---Z---->---+
| | | Poly B |
| | | |
+ +-------+--------+
| |
| |
+------+-------+--------+
Which can lead to two valid results (the algorithm above will lead randomly to one or the other):
Result 1, one filled contour:
+------+--->---+
| Poly A |
| |
+ +---<---+---->---+
| | | |
| | | |
+ +--->---+ +
| |
| |
+------+---<---+--------+
Result 2, one filled contour, one hollow contour:
+------+--->---+
| Poly A |
| |
+ +---<---+---->---+
| | Hole A| |
| | | |
+ +--->---+ +
| |
| |
+------+---<---+--------+
This shouldn't be a problem though, as your code should already be ready to handle holes.
Other important detail: The algorithm above doesn't get rid of intermediate points ('+'), in fact they are expected or else the algorithm won't work, as in the following case:
+------>-------+
| Poly A |
| |
| | +---->---+
| | | Poly B |
| | | |
| | +----<---+
| |
| |
+------<-------+
My understanding is that this is what you have. I imagine the algorithm could be extended to support such case by finding and adding the intersecting points beforehand (it was unnecessary in my case):
+------>-------+
| Poly A |
| |
| + +---->---+
| | | Poly B |
| | | |
| + +----<---+
| |
| |
+------<-------+
Hope this help.
P.S.: You can 'test' the algorithm with the jigsaw puzzle, by snapping pieces together to generate holes, etc.: 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
这篇关于将相邻矩形合并为多边形的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！