作为 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