я должен был написать алгоритм для объединения смежных полигонов в рамках эксперимента проекта с 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, которые определяют 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 |
| | | |
| + +----<---+
| |
| |
+------<-------+
Надежда этой помощь.
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
Язык программирования? –
Периметр любого прямоугольника смежных прямоугольников делает многоугольник. Возникает вопрос: «Как мне отобразить сегменты линий, которые определяют периметр набора связанных прямоугольников?» или что-то другое? – mbeckish
Когда вы говорите «многие примыкают друг к другу», что это значит? Они просто касаются краев или могут перекрывать прямоугольники? Являются ли прямоугольники на какой-либо сетке или могут быть их вершины в любом месте? –