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