Алгоритм для слияния смежных прямоугольников в полигон
Если x - это кадр данных с вашими данными, то следующее будет делать то, что вы хотите:
require(reshape)
recast(x, Category ~ ., fun.aggregate=sum)
6 ответов
Я изучил бы что-то как Общий полигон Clipper . Вы в основном делаете операции полигона (ИЛИ) объединение. То, что они - все прямоугольники просто, делает математику немного легче, но она могла легко быть сделана с чем-то как GPC.
существуют обертки языка для большого количества языков там, также.
Если Вы пользуетесь пространственной библиотекой обработки (как JTS [Java], NTS [.NET] или GEOS [C++], которые являются всем открытым исходным кодом и применимый для коммерческих приложений, в отличие от GPC), Вы можете просто Объединение прямоугольники.
способ общего назначения сделать это должно создать график краев исходных данных (прямоугольники), выполнить пересечения, маркировать края как на внутренней или внешней части результата и просто сохранить внешние края. Я не знаю об определенном алгоритме для обработки прямоугольников, но это, вероятно, был бы simiar, кроме, как отмечено, математика будет более простой.
если бы Ваши границы являются разумным использованием 2D массив граничных количеств, иначе необходимо было бы использовать вложенные словари.
потому что все ширины и высоты являются тем же, можно однозначно определить край комбинацией x, y, и ориентацию (вертикальный или горизонтальный)
демонстрационный псевдокод: list_of_edges = новый список arr_count = новый интервал [] [] []
fill_with_zeroes(arr_count )
foreach rect
foreach edge
arr_count [edge.x][edge.y][edge.orientation] += 1
foreach edge in arr_count
if count[edge] = 1
list_of_edges.add(edge]
конечно, если бы Вы хотите заказать края, затем необходимо было бы пройти через массив другое время
foreach edge in arr_count
if count[edge] = 1
add_recursive(edge)
add_recursive(x,y):
for both horizontal and vertical orientations of edge starting at x, y:
count[edge] = 0
if (edge.orientation is horizontal)
return add_recursive( x+1, y)
else
return add_recursive( x, y+1 )
извините, этот псевдокод довольно неаккуратен, но необходимо в общих чертах понять
Просто протестируйте, если прямоугольники касаются и затем выполняют выпуклую оболочку на объединении их точек.
Или Вы могли также вручную протестировать для наблюдения, какая сторона прямоугольников касаются и добавляют точку в правильном порядке к объекту полигона.
Они предполагают, что закрытые полигоны будут достаточны (не может иметь дыр в нем).
Мне пришлось написать алгоритм для объединения смежных полигонов в рамках проекта эксперимента с холстом 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
Как насчет того, чтобы попробовать следующее. Я думаю, что это сработает, если правильно спроектировать.
Найдите наименьший охватывающий прямоугольник, в основном max-x, min-x, max-y и min-y. Это будет наш холст для рисования. Инициализируйте двумерный массив битов dx X dy, где dx, dy - ширина этого внешнего прямоугольника, всеми нулями.
Наша цель - найти контур, в основном некоторые углы прямоугольников, чтобы мы могли уменьшить эту проблему до уровня, на котором мы сможем справиться с ней вычислительным путем, когда у нас есть точки, которые мы можем масштабировать, чтобы получить фактические координаты.
Просмотрите вышеуказанный 2D-массив и отметьте точку 1, если она содержится в одном из заданных прямоугольников.
Теперь просканируйте 2D-массив и найдите точки, окрестности которых имеют разделение 3: 1, что означает, что с трех сторон у него есть единицы, а с одной стороны - нули, или наоборот. Эти точки и будут определять контур.
Я думаю, что сложность будет управляемой, если мы сможем уменьшить проблему с умом.