Мне пришлось написать алгоритм для объединения смежных полигонов в рамках проекта эксперимента с холстом HTML5 (ничего особенного, головоломка :-) Дыры в получившемся многоугольнике, естественно, поддерживаются. Подпрограмма 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, которые определяют Polygon. Некоторые контуры будут заполнены, некоторые могут быть полыми. Чтобы определить, является ли Контур заполненным или пустым, достаточно проверить, вращается ли Контур по часовой стрелке или против часовой стрелки, или его площадь положительная или отрицательная. Это условность, в моем случае контуры по часовой стрелке закрашены, против часовой стрелки - полые.
Вот моя реализация без специфики и без обработки ошибок. Надеюсь, я скопировал / вставил достаточно, чтобы он сразу заработал, иначе обратитесь к моему 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
person
Community
schedule
11.06.2009