Мне пришлось написать алгоритм для объединения смежных полигонов как часть экспериментального проекта с HTML5 canvas (ничего особенного, головоломка :-) Отверстия в полученном многоугольнике естественно поддерживаются. Подпрограмма Javascript находится в функции с именем Polygon.prototype.merge () в www dot raymondhill dot net / puzzle-rhill / jigsawpuzzle-rhill-3 dot js
Ключ в том, чтобы удалить повторяющиеся сегменты, но противоположного направления. Грубое объяснение: точка - это {x:?, Y:?}, Сегмент - это {ptA:?, PtB:?}, Контур - это {pts: []} (набор связанных объектов Point), многоугольник {contours: []} (коллекция объектов Contour.)
Алгоритм слияния собирает всех сегментов в большой пул объектов Segment, где удаляются дубликаты. Сначала все сегменты всех контуров, определяющих полигон A, добавляются в пул. Затем все сегменты всех контуров, определяющих полигон B, добавляются в пул, но мы проверяем и удаляем дубликаты (это легко сделать, используя объект Point в качестве хеш-ключа).
Затем мы берем сегмент из пула (в порядке случайности) и «проходим» его до тех пор, пока не достигнем «тупика», то есть ни один сегмент больше не может быть подключен. Это образует один объект Contour. Мы повторяем, пока не будет использована вся коллекция сегментов. Поскольку сегменты используются, они удаляются из пула. «Прогулка» по сегменту означает, что мы берем его конечную точку и ищем сегмент, точка начала которого ему соответствует.
Как уже говорилось, в результате мы имеем коллекцию объектов 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 |
| | | |
| + +----<---+
| |
| |
+------<-------+
Надеюсь, это поможет.
P.S .: Вы можете «проверить» алгоритм с помощью головоломки, сложив кусочки вместе, чтобы создать дыры, и т. Д .: 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