Алгоритм объединения смежных прямоугольников в многоугольник

Я предполагаю, что моя проблема связана с «выпуклой оболочкой», но не то же самое. Все фигуры на рисунке представляют собой прямоугольники одинаковой ширины и высоты. Многие соседствуют друг с другом. Я хочу объединить эти смежные прямоугольники в многоугольники. В отличие от «выпуклой оболочки» полученные многоугольники могли быть «полыми» внутри.

Доступен ли какой-либо алгоритм с открытым исходным кодом?


person Glitch    schedule 13.03.2009    source источник
comment
Периметр любой капли из смежных прямоугольников образует многоугольник. У вас есть вопрос. Как мне составить список отрезков линии, определяющих периметр набора соединенных прямоугольников? или что-то другое?   -  person mbeckish    schedule 13.03.2009
comment
Когда вы говорите, что многие находятся рядом друг с другом, что это значит? Они просто соприкасаются по краям, или прямоугольники могут перекрываться? Находятся ли прямоугольники на какой-то сетке или их вершины могут быть где угодно?   -  person David Grayson    schedule 14.03.2009


Ответы (8)


Мне пришлось написать алгоритм для объединения смежных полигонов в рамках проекта эксперимента с холстом 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
comment
Спасибо за этот ответ, я смог использовать алгоритм в картографическом контексте с библиотекой OpenLayers. - person Laurent Jégou; 06.07.2011

Я бы посмотрел на что-то вроде General Polygon Clipper. Вы в основном выполняете операции объединения (ИЛИ) многоугольников. Тот факт, что все они прямоугольники, немного упрощает математику, но это легко можно сделать с помощью чего-то вроде GPC.

Там же есть языковые оболочки для многих языков.

person Reed Copsey    schedule 13.03.2009

Если вы используете библиотеку пространственной обработки (например, JTS [java], NTS [.net] или GEOS [c ++], которые имеют открытый исходный код и могут использоваться для коммерческих приложений, в отличие от GPC), вы можете просто объединить прямоугольники.

Общий способ сделать это - построить график краев входных данных (прямоугольников), выполнить пересечения, пометить края как внутри или снаружи результата и просто сохранить внешние края. Я не знаю конкретного алгоритма для обработки прямоугольников, но он, вероятно, будет аналогичным, за исключением того, что, как уже отмечалось, математика будет проще.

person codekaizen    schedule 13.03.2009

если ваши границы разумны, используйте двумерный массив счетчиков краев, иначе вам придется использовать вложенные словари.

поскольку все значения ширины и высоты одинаковы, вы можете однозначно идентифицировать край по комбинации x, y и ориентации (вертикальной или горизонтальной)

пример псевдокода: list_of_edges = новый список arr_count = new int [] [] []

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 )

извините, этот псевдокод довольно неаккуратный, но вы должны уловить общее представление

person Jimmy    schedule 14.03.2009

Как насчет того, чтобы попробовать следующее. Думаю, это сработает, если правильно спроектировать.

  1. Найдите наименьший закрывающий прямоугольник, в основном max-x, min-x, max-y и min-y. Это будет наш холст для рисования. Инициализируйте двумерный массив битов dx X dy, где dx, dy - ширина этого внешнего прямоугольника, всеми нулями.

  2. Наша цель состоит в том, чтобы найти контур, в основном некоторые углы прямоугольников, чтобы мы могли уменьшить масштаб этой проблемы до уровня, на котором мы можем справиться с ней вычислительным путем, когда у нас есть точки, которые мы можем масштабировать, чтобы получить фактические координаты.

  3. Просмотрите вышеуказанный 2D-массив и отметьте точку 1, если она содержится в одном из заданных прямоугольников.

  4. Теперь просканируйте 2D-массив и найдите точки, окрестности которых имеют разделение 3: 1, что означает, что с трех сторон у него есть единицы, а с одной стороны - нули, или наоборот. Эти точки и будут определять контур.

Я думаю, что сложность станет управляемой, если мы сможем уменьшить проблему с умом.

person Anil    schedule 06.06.2010

Я нашел более простой способ:

  1. Создайте черное изображение.
  2. Нарисуйте на изображении закрашенные прямоугольники белым цветом. При этом будут соединены все перекрывающиеся прямоугольники.
  3. Найдите контуры капли.

Вот и все!

person TeckWee    schedule 06.05.2013

У меня раньше была похожая проблема. Я не знаю точно, как вы выравниваете точки, но мои всегда находились на расстоянии 5 метров друг от друга.

Мое решение заключалось в том, чтобы получить точку, упорядоченную по координате x.

Имел два списка, один назывался предыдущим, а другой - текущим.

Если текущий был пустым, добавьте точку к текущему. Если текущая не пуста, проверьте, находится ли точка рядом с одной из точек в текущем (пропустите список в обратном направлении, так как вероятность того, что недавняя точка находится рядом, выше)

Если точка не смежна ни с одной точкой в ​​текущем, то проверьте, не примыкает ли какая-либо из точек в текущем к какой-либо точке в предыдущем списке. Если да, то объедините (объедините) их, если нет, то переместите точки из предыдущего в другой список, содержащий полные многоугольники, затем установите предыдущий = текущий, пустой текущий и добавьте обрабатываемую точку в текущий.

В зависимости от того, как обрабатываются ваши точки (порядок), вам может потребоваться снова пропустить все последние полигоны, чтобы проверить, не примыкают ли они к какому-либо из других полигонов.

Извините за длинную стену текста, дайте мне знать, если вы хотите кодировать, он на C # и не очень чистый.

person Kennedine    schedule 15.05.2014

Просто проверьте, соприкасаются ли прямоугольники, а затем выполните выпуклую оболочку на объединении их точек.

Или вы также можете вручную проверить, какая сторона прямоугольников соприкасается, и добавить точку в правильном порядке к многоугольному объекту.

Они предполагают, что замкнутых многоугольников будет достаточно (в них не должно быть дыр).

person Ben S    schedule 13.03.2009
comment
Это не сработает, если он хочет сохранить дыры. Представьте, что у вас есть блок прямоугольников 3x3, но отсутствует центральный прямоугольник - выпуклая оболочка заполнит его. - person Reed Copsey; 13.03.2009