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

Ответ 1

О'Рурк изучил проблему, связанную с этой (по многим другим вопросам, относящейся к вычислительной геометрии) и, как следствие, создал очень красивый метод для ее эффективного решения. Его метод описан в статье Уникальность ортогональных точек со связью и также четко проиллюстрирован на http://www.cs.mcgill.ca/~cs644/Godfried/2005/Fall/sdroui9/p0_introduction.html. Обратите внимание, что в нем говорится, что для применения этого метода многоугольник не должен делиться вершинами, но это часто происходит в обсуждаемой здесь проблеме. Таким образом, все, что нам нужно сделать, - это исключить разделяемые вершины. Обратите внимание, что это все равно создает многоугольник, и в качестве результата требуется многоугольник. Также обратите внимание, что список прямоугольников не должен содержать дубликатов (я предполагаю, что это так, в противном случае препроцессор, чтобы сделать список уникальным).

Я использовал Python для его кодирования, и если есть какие-либо сомнения в его значении, не стесняйтесь спрашивать. Вот краткий обзор реализации. Начнем со списка прямоугольников, описанных в соответствии с обозначением OP. Затем мы получаем четыре вершины каждого прямоугольника, отбрасывая общие вершины вдоль пути. Это достигается с помощью set. Теперь мы просто применим упомянутый алгоритм. Обратите внимание, что для хранения краев многоугольника я использую две хэш-таблицы, edges_h (для горизонтальных ребер) и edges_v (для вертикальных краев). Эти хеш-таблицы эффективно работают как неориентированный граф. Таким образом, после того как все ребра получены, легко и быстро получить упорядоченные вершины многоугольника. Выберите любой (ключ, значение) из хеш-таблицы edges_h, например. Теперь следующей упорядоченной вершиной является та, которая задана edges_v[value] = next_value, а следующая - edges_h[next_value] и т.д. Повторите этот процесс, пока мы не нажмем первую выбранную вершину, и все будет сделано.

Быстрый просмотр указанного алгоритма:

•  
• Сортировка точек по наименьшему x, самому низкому y  
• Пройдите через каждый столбец и создайте ребра между вершинами 2i и 2i + 1 в этом столбце  
• Сортировка точек по наименьшему y, наименьшее x  
• Пройдите по каждой строке и создайте ребра между вершинами 2i и 2i + 1 в этой строке.

# These rectangles resemble the OP illustration.
rect = ([[0,  10], [10, 0]],
        [[10, 13], [19, 0]],
        [[19, 10], [23, 0]])

points = set()
for (x1, y1), (x2, y2) in rect:
    for pt in ((x1, y1), (x2, y1), (x2, y2), (x1, y2)):
        if pt in points: # Shared vertice, remove it.
            points.remove(pt)
        else:
            points.add(pt)
points = list(points)

def y_then_x(a, b):
    if a[1] < b[1] or (a[1] == b[1] and a[0] < b[0]):
        return -1
    elif a == b:
        return 0
    else:
        return 1

sort_x = sorted(points)
sort_y = sorted(points, cmp=y_then_x)

edges_h = {}
edges_v = {}

i = 0
while i < len(points):
    curr_y = sort_y[i][1]
    while i < len(points) and sort_y[i][1] == curr_y: //6chars comments, remove it
        edges_h[sort_y[i]] = sort_y[i + 1]
        edges_h[sort_y[i + 1]] = sort_y[i]
        i += 2
i = 0
while i < len(points):
    curr_x = sort_x[i][0]
    while i < len(points) and sort_x[i][0] == curr_x:
        edges_v[sort_x[i]] = sort_x[i + 1]
        edges_v[sort_x[i + 1]] = sort_x[i]
        i += 2

# Get all the polygons.
p = []
while edges_h:
    # We can start with any point.
    polygon = [(edges_h.popitem()[0], 0)]
    while True:
        curr, e = polygon[-1]
        if e == 0:
            next_vertex = edges_v.pop(curr)
            polygon.append((next_vertex, 1))
        else:
            next_vertex = edges_h.pop(curr)
            polygon.append((next_vertex, 0))
        if polygon[-1] == polygon[0]:
            # Closed polygon
            polygon.pop()
            break
    # Remove implementation-markers from the polygon.
    poly = [point for point, _ in polygon]
    for vertex in poly:
        if vertex in edges_h: edges_h.pop(vertex)
        if vertex in edges_v: edges_v.pop(vertex)

    p.append(poly)


for poly in p:
    print poly

результатом является список упорядоченных вершин для многоугольника:

[(0, 0), (0, 10), (10, 10), (10, 13), (19, 13), (19, 10), (23, 10), (23, 0)]

Мы также можем поэкспериментировать с более сложной компоновкой:

rect = ([[1, 2], [3, 1]], [[1, 4], [2, 2]], [[1, 6], [2, 4]], [[2, 6], [3, 5]],
        [[3, 8], [4, 4]], [[2, 8], [3, 7]], [[3, 10], [5, 8]], [[3, 4], [9, 3]],
        [[4, 5], [7, 4]], [[6, 8], [7, 5]], [[6, 9], [8, 8]], [[8, 9], [10, 6]],
        [[9, 6], [10, 3]])

который представлен как следующий набор прямоугольников:

и метод создает следующие списки:

[(6, 9), (6, 5), (4, 5), (4, 8), (5, 8), (5, 10), (3, 10), (3, 8),
 (2, 8), (2, 7), (3, 7), (3, 6), (1, 6), (1, 1), (3, 1), (3, 2),
 (2, 2), (2, 5), (3, 5), (3, 3), (10, 3), (10, 9)]

[(9, 4), (9, 6), (8, 6), (8, 8), (7, 8), (7, 4)]

который, если нарисован, представляет собой многоугольники в синем и красном соответственно, как в:

По мере прохождения простых тестов:

• 1000 прямоугольников: ~ 0,04 секунды
• 10000 прямоугольников: ~ 0,62 секунды
• 100000 прямоугольников: ~ 8,68 секунд

Эти тайминги - это просто среднее значение 10 запусков на занятой устаревшей машине. Прямоугольники были случайным образом сгенерированы.

EDIT:

Внедрение в PHP, если необходимо.

Ответ 2

Вот мое решение:

RectUnion.php

<?php 

class RectUnion {
    private $x, $y;
    private $sides;
    private $points;

    function __construct() {
        $this->x = array();
        $this->y = array();
        $this->sides = array();
        $this->points = array();
    }

    function addRect($r) {
        extract($r);
        $this->x[] = $x1;
        $this->x[] = $x2;
        $this->y[] = $y1;
        $this->y[] = $y2;
        if ($x1 > $x2) { $tmp = $x1; $x1 = $x2; $x2 = $tmp; }
        if ($y1 > $y2) { $tmp = $y1; $y1 = $y2; $y2 = $tmp; }
        $this->sides[] = array($x1, $y1, $x2, $y1);
        $this->sides[] = array($x2, $y1, $x2, $y2);
        $this->sides[] = array($x1, $y2, $x2, $y2);
        $this->sides[] = array($x1, $y1, $x1, $y2);
    }

    function splitSides() {
       $result = array();
       $this->x = array_unique($this->x);
       $this->y = array_unique($this->y);
       sort($this->x);
       sort($this->y);
       foreach ($this->sides as $i => $s) {
           if ($s[0] - $s[2]) {     // Horizontal
               foreach ($this->x as $xx) {
                   if (($xx > $s[0]) && ($xx < $s[2])) {
                       $result[] = array($s[0], $s[1], $xx, $s[3]);
                       $s[0] = $xx;
                   }
               }
           } else {                 // Vertical
               foreach ($this->y as $yy) {
                   if (($yy > $s[1]) && ($yy < $s[3])) {
                       $result[] = array($s[0], $s[1], $s[2], $yy);
                       $s[1] = $yy;
                   }
               }
           }
           $result[] = $s;
       }
       return($result);
    }

    function removeDuplicates($sides) {
        $x = array();
        foreach ($sides as $i => $s) {
            @$x[$s[0].','.$s[1].','.$s[2].','.$s[3]]++;
        }
        foreach ($x as $s => $n) {
            if ($n > 1) {
              unset($x[$s]);
            } else {
              $this->points[] = explode(",", $s);
            }
        }
        return($x);
    }

    function drawPoints($points, $outfile = null) {
        $xs = $this->x[count($this->x) - 1] + $this->x[0];
        $ys = $this->y[count($this->y) - 1] + $this->y[0];
        $img = imagecreate($xs, $ys);
        if ($img !== FALSE) {
            $wht = imagecolorallocate($img, 255, 255, 255);
            $blk = imagecolorallocate($img, 0, 0, 0);
            $red = imagecolorallocate($img, 255, 0, 0);
            imagerectangle($img, 0, 0, $xs - 1, $ys - 1, $red);
            $oldp = $points[0];
            for ($i = 1; $i < count($points); $i++) {
                $p = $points[$i];
                imageline($img, $oldp['x'], $oldp['y'], $p['x'], $p['y'], $blk);
                $oldp = $p;
            }
            imageline($img, $oldp['x'], $oldp['y'], $points[0]['x'], $points[0]['y'], $blk);
            if ($outfile == null) header("content-type: image/png");
            imagepng($img, $outfile);
            imagedestroy($img);
        }
    }

    function drawSides($sides, $outfile = null) {
        $xs = $this->x[count($this->x) - 1] + $this->x[0];
        $ys = $this->y[count($this->y) - 1] + $this->y[0];
        $img = imagecreate($xs, $ys);
        if ($img !== FALSE) {
            $wht = imagecolorallocate($img, 255, 255, 255);
            $blk = imagecolorallocate($img, 0, 0, 0);
            $red = imagecolorallocate($img, 255, 0, 0);
            imagerectangle($img, 0, 0, $xs - 1, $ys - 1, $red);
            foreach ($sides as $s => $n) {
                if (is_array($n)) {
                    $r = $n;
                } else {
                    $r = explode(",", $s);
                }
                imageline($img, $r['x1'], $r['y1'], $r['x2'], $r['y2'], $blk);
            }
            if ($outfile == null) header("content-type: image/png");
            imagepng($img, $outfile);
            imagedestroy($img);
        }
    }

    function getSides($sides = FALSE) {
        if ($sides === FALSE) {
            foreach ($this->sides as $r) {
                $result[] = array('x1' => $r[0], 'y1' => $r[1], 'x2' => $r[2], 'y2' => $r[3]);
            }
        } else {
            $result = array();
            foreach ($sides as $s => $n) {
                $r = explode(",", $s);
                $result[] = array('x1' => $r[0], 'y1' => $r[1], 'x2' => $r[2], 'y2' => $r[3]);
            }
        }
        return($result);
    }

    private function _nextPoint(&$points, $lastpt) {
        @extract($lastpt);
        foreach ($points as $i => $p) {
            if (($p[0] == $x) && ($p[1] == $y)) {
                unset($points[$i]);
                return(array('x' => $p[2], 'y' => $p[3]));
            } else if (($p[2] == $x) && ($p[3] == $y)) {
                unset($points[$i]);
                return(array('x' => $p[0], 'y' => $p[1]));
            }
        }
        return false;
    }

    function getPoints($points = FALSE) {
        if ($points === FALSE) $points = $this->points;
        $result = array(
            array('x' => $points[0][0], 'y' => $points[0][1])
        );
        $lastpt = array('x' => $points[0][2], 'y' => $points[0][3]);
        unset($points[0]);
        do {
            $result[] = $lastpt;
        } while ($lastpt = $this->_nextPoint($points, $lastpt));
        return($result);
    }
}

?>

merge.php

<?php

require_once("RectUnion.php");

function generateRect($prev, $step) {
    $rect = array(
        'x1' => $prev['x2'],
        'x2' => $prev['x2'] + rand($step, $step * 10),
        'y1' => rand($prev['y1'] + 2, $prev['y2'] - 2),
        'y2' => rand($step * 2, $step * 10)
    );
    return($rect);
}

$x0 = 50;       // Pixels
$y0 = 50;       // Pixels
$step = 20;     // Pixels
$nrect = 10;    // Number of rectangles
$rects = array(
    array("x1" => 50, "y1" => 50, "x2" => 100, "y2" => 100)
);
for ($i = 1; $i < $nrect - 1; $i++) {
    $rects[$i] = generateRect($rects[$i - 1], $step);
}

$start_tm = microtime(true);

$ru = new RectUnion();
foreach ($rects as $r) {
    $ru->addRect($r);
}
$union = $ru->removeDuplicates($ru->splitSides());

$stop_tm = microtime(true);

$ru->drawSides($ru->getSides(), "before.png");

if (FALSE) {    // Lines
    $sides = $ru->getSides($union);
    $ru->drawSides($sides, "after.png");
} else {        // Points
    $points = $ru->getPoints();
    $ru->drawPoints($points, "after.png");
}

?>
<!DOCTYPE html>
<html>
    <body>
        <fieldset>
            <legend>Before Union</legend>
            <img src='before.png'>
        </fieldset>
        <fieldset>
            <legend>After Union</legend>
            <img src='after.png'>
        </fieldset>
        <h4>Elapsed Time: <?= round($stop_tm - $start_tm, 4) ?> seconds</h4>
        <?php if (isset($sides)): ?>
        <h4>Sides:</h4>
        <pre><?= print_r($sides, true) ?></pre>
        <?php elseif (isset($points)): ?>
        <h4>Points:</h4>
        <pre><?= print_r($points, true) ?></pre>
        <?php endif ?>
    </body>
</html>

Как это работает?

script идентифицирует и удаляет все "перекрывающиеся" сегменты. Например:

Сначала стороны каждого прямоугольника расщепляются на пересечениях со сторонами адиагентного прямоугольника.
Например, рассмотрим сторону B2-B3 прямоугольника B: метод "splitSides" разбивает его на сегменты B2-D1, D1-D4 и D4-B3.
Затем метод removeDuplicates удаляет все перекрывающиеся (дублированные) сегменты.
Например, сегмент D1-D4 является дубликатом, так как он отображается либо в прямоугольнике B, либо в прямоугольнике D.
Наконец, метод getSides возвращает список оставшихся сегментов, в то время как метод getPoints возвращает список точек полигона.
Методы "рисования" предназначены только для графического представления результата и требуют расширения GD для работы:

О производительности

Вот несколько примеров выполнения:

• 10 прямоугольников: 0,003 секунды
• 100 прямоугольников: 0,220 секунд
• 1000 прямоугольников: 4 407 секунд
• 2000 прямоугольников: 13 448 секунд

Профилируя выполнение XDebug, я получил следующие результаты:

Ответ 3

Я не буду использовать математику для решения этой проблемы, но только анализ.

Рассмотрим следующее изображение:

Здесь мы имеем сразу два примера, чтобы убедиться, что мы рассмотрим все случаи.

• на первом изображении у нас есть специальный случай: прямоугольники № 3, 4, 5, 11, 12, 13 создают пустую область, это может быть дым в вашем случае.

• во втором изображении мы имеем угол между прямоугольниками 16, 17, 18, 19... это будет иметь свою важность позже.

Как я решил проблему, использует следующие вещи:

• Угол - это точка, которая была написана от 2 до 8 раз: по крайней мере 2, потому что, если мы представляем прямоугольник ABCD, угол B будет разделяться с AB и BC (так что пиксель был помещен 2 раз). Его можно записать 8 раз в случае прямоугольников 16, 17, 18, 19, где одна точка разделяется четырьмя прямоугольниками, поэтому 8 сторон.

• Сторона представляет собой набор точек, которые могут быть записаны 1 или 2 раза (без учета углов): 1 раз, если сторона одна, а не близко к другой стороне, и 2 раза, если сторона, близкая к другой один. А сторона, которая не близка к другой, близка к внешнему: она должна принимать участие в конечном полигоне.

Итак, вот логика:

• Мы создаем виртуальное пространство того же размера, что и все изображение, заполненное нулями (0).

• Мы пишем все прямоугольники, но вместо того, чтобы писать пиксели, мы увеличиваем значение виртуального пикселя

                            21111111112                   
                            1         1                   
                            1         1                   
                            1         1                   
                            1         1                   
                            1         1                   
                            1         1                   
                            1         1                   
                            1         1                   
                            1         1                   
                  2111111111622222222261111111112         
                  1         2         2         1         
                  1         2         2         1         
                  1         2         2         1         
                  1         2         2         1         
                  1         2         2         1         
                  1         2         2         1         
                  1         2         2         1         
                  1         2         2         1         
                  1         2         2         1         
        21111111116222222222611111111141111111112         
        1         2         1                             
        1         2         1                             
        1         2         1                             
        1         2         1                             
        1         2         1                             
        1         2         1                             
        1         2         1                             
        1         2         1                             
        1         2         1                             
        (...)
  

(Извините, похоже, что мой отступ имеет проблемы с инструментом форматирования SO)

• Мы удаляем все виртуальные точки, которые имеют значение больше 2, за исключением углов, которые мы установили в 1

В этот момент мы имеем многоугольники и точки в одиночку (где есть угол в середине нескольких других прямоугольников).

                              11111111111                   
                              1         1                   
                              1         1                   
                              1         1                   
                              1         1                   
                              1         1                   
                              1         1                   
                              1         1                   
                              1         1                   
                              1         1                   
                    11111111111         11111111111         
                    1                             1         
                    1                             1         
                    1                             1         
                    1                             1         
                    1                             1         
                    1                             1         
                    1                             1         
                    1                             1         
                    1                             1         
          11111111111         111111111111111111111         
          1                   1                             
          1                   1                             
          1                   1                             
          1                   1                             
          1                   1                             
          1                   1                             
          1                   1                             
          1                   1                             
          1                   1                             
11111111111         1         11111111111                   
1                                       1                   
1                                       1                   
1                                       1                   
1                                       1                   
1                                       1                   
1                                       1                   
1                                       1                   
1                                       1                   
1                                       1                   
11111111111111111111111111111111111111111                   

• Теперь нам нужно искать один или несколько полигонов (у нас может быть несколько полигонов, когда мы находимся в корпусе прямоугольников 11 12 13 14 3 4 5). Это означает, что поиск точки в нашем виртуальном изображении.

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

• Когда мы найдем точку, мы ее сохраним, попробуйте выполнить итерацию в одном направлении (вверх/влево/вправо/снизу) и продолжить, удаляя точки в этом направлении, пока не будет больше точки: это один угол многоугольника. Мы продолжаем этот путь, пока не удастся перейти в какое-либо направление: это означает, что мы находимся в конце многоугольника.

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

Как насчет результата?

Реализация:

class PolygonMaker
{

    private $image;
    private $width;
    private $height;
    private $vImage;

    public function __construct($width, $height)
    {
        // create a GD image to display results and debug
        $this->width = $width;
        $this->height = $height;
        $this->image = imagecreatetruecolor($width, $height);
        $white = imagecolorallocate($this->image, 0xFF, 0xFF, 0xFF);
        imagefill($this->image, 0, 0, $white);
        imagesetthickness($this->image, 3);
    }

    public function __destruct()
    {
        imagedestroy($this->image);
    }

    public function display()
    {
        // Display gd image as png
        header("Content-type: image/png");
        imagepng($this->image);
    }

    public function drawRectangles(array $rectangles, $r, $g, $b)
    {
        // Draw rectangles as they are inside the gd image
        foreach ($rectangles as $rectangle)
        {
            list($tx, $ty) = $rectangle[0];
            list($bx, $by) = $rectangle[1];
            $color = imagecolorallocate($this->image, $r, $g, $b);
            imagerectangle($this->image, $tx, $ty, $bx, $by, $color);
        }
    }

    public function findPolygonsPoints(array $rectangles)
    {
        // Create a virtual image where rectangles will be "drawn"
        $this->_createVirtualImage($rectangles);

        $polygons = array ();

        // Searches for all polygons inside the virtual image
        while (!is_null($beginPoint = $this->_findPolygon()))
        {
            $polygon = array ();

            // Push the first point
            $polygon[] = $this->_cleanAndReturnPolygonPoint($beginPoint);
            $point = $beginPoint;

            // Try to go up, down, left, right until there is no more point
            while ($point = $this->_getNextPolygonPoint($point))
            {
                // Push the found point
                $polygon[] = $this->_cleanAndReturnPolygonPoint($point);
            }

            // Push the first point at the end to close polygon
            $polygon[] = $beginPoint;

            // Add the polygon to the list, in case of several polygons in the image
            $polygons[] = $polygon;
        }

        $this->vImage = null;
        return $polygons;
    }

    private function _createVirtualImage(array $rectangles)
    {
        // Create a 0-filled grid where will be stored rectangles
        $this->vImage = array_fill(0, $this->height, array_fill(0, $this->width, 0));

        // Draw each rectangle to that grid (each pixel increments the corresponding value of the grid of 1)
        foreach ($rectangles as $rectangle)
        {
            list($x1, $y1, $x2, $y2) = array ($rectangle[0][0], $rectangle[0][1], $rectangle[1][0], $rectangle[1][1]);
            $this->_drawVirtualLine($x1, $y1, $x1, $y2); // top-left, bottom-left
            $this->_drawVirtualLine($x2, $y1, $x2, $y2); // top-right, bottom-right
            $this->_drawVirtualLine($x1, $y1, $x2, $y1); // top-left, top-right
            $this->_drawVirtualLine($x1, $y2, $x2, $y2); // bottom-left, bottom-right
        }

        // Remove all pixels that are scored > 1 (that our logic!)
        for ($y = 0; ($y < $this->height); $y++)
        {
            for ($x = 0; ($x < $this->width); $x++)
            {
                $value = &$this->vImage[$y][$x];
                $value = $value > 1 ? 0 : $value;
            }
        }
    }

    private function _drawVirtualLine($x1, $y1, $x2, $y2)
    {
        // Draw a vertial line in the virtual image
        if ($x1 == $x2)
        {
            if ($y1 > $y2)
            {
                list($x1, $y1, $x2, $y2) = array ($x2, $y2, $x1, $y1);
            }
            for ($y = $y1; ($y <= $y2); $y++)
            {
                $this->vImage[$y][$x1]++;
            }
        }

        // Draw an horizontal line in the virtual image
        if ($y1 == $y2)
        {
            if ($x1 > $x2)
            {
                list($x1, $y1, $x2, $y2) = array ($x2, $y2, $x1, $y1);
            }
            for ($x = $x1; ($x <= $x2); $x++)
            {
                $this->vImage[$y1][$x]++;
            }
        }

        // Force corners to be 1 (because one corner is at least used 2 times but we don't want to remove them)
        $this->vImage[$y1][$x1] = 1;
        $this->vImage[$y1][$x2] = 1;
        $this->vImage[$y2][$x1] = 1;
        $this->vImage[$y2][$x2] = 1;
    }

    private function _findPolygon()
    {
        // We're looking for the first point in the virtual image
        foreach ($this->vImage as $y => $row)
        {
            foreach ($row as $x => $value)
            {
                if ($value == 1)
                {
                    // Removes alone points ( every corner have been set to 1, but some corners are alone (eg: middle  of 4 rectangles)
                    if ((!$this->_hasPixelAtBottom($x, $y)) && (!$this->_hasPixelAtTop($x, $y))
                       && (!$this->_hasPixelAtRight($x, $y)) && (!$this->_hasPixelAtLeft($x, $y)))
                    {
                        $this->vImage[$y][$x] = 0;
                        continue;
                    }
                    return array ($x, $y);
                }
            }
        }
        return null;
    }

    private function _hasPixelAtBottom($x, $y)
    {
        // The closest bottom point is a point positionned at (x, y + 1)
        return $this->_hasPixelAt($x, $y + 1);
    }

    private function _hasPixelAtTop($x, $y)
    {
        // The closest top point is a point positionned at (x, y - 1)
        return $this->_hasPixelAt($x, $y - 1);
    }

    private function _hasPixelAtLeft($x, $y)
    {
        // The closest left point is a point positionned at (x - 1, y)
        return $this->_hasPixelAt($x - 1, $y);
    }

    private function _hasPixelAtRight($x, $y)
    {
        // The closest right point is a point positionned at (x + 1, y)
        return $this->_hasPixelAt($x + 1, $y);
    }

    private function _hasPixelAt($x, $y)
    {
        // Check if the pixel (x, y) exists
        return ((isset($this->vImage[$y])) && (isset($this->vImage[$y][$x])) && ($this->vImage[$y][$x] > 0));
    }

    private function _cleanAndReturnPolygonPoint(array $point)
    {
        // Remove a point from the virtual image
        list($x, $y) = $point;
        $this->vImage[$y][$x] = 0;
        return $point;
    }

    private function _getNextPolygonPoint(array $point)
    {
        list($x, $y) = $point;

        // Initialize modifiers, to move to the right, bottom, left or top.
        $directions = array(
                array(1, 0), // right
                array(0, 1), // bottom
                array(-1, 0), // left
                array(0, -1), // top
        );

        // Try to get to one direction, if we can go ahead, there is a following corner
        $return = null;
        foreach ($directions as $direction)
        {
            list($xModifier, $yModifier) = $direction;
            if (($return = $this->_iterateDirection($x, $y, $xModifier, $yModifier)) !== null)
            {
                return $return;
            }
        }

        // the point is alone : we are at the end of the polygon
        return $return;
    }

    private function _iterateDirection($x, $y, $xModifier, $yModifier)
    {
        // This method follows points in a direction until the last point
        $return = null;
        while ($this->_hasPixelAt($x + $xModifier, $y + $yModifier))
        {
            $x = $x + $xModifier;
            $y = $y + $yModifier;

            // Important : we remove the point so we'll not get back when moving
            $return = $this->_cleanAndReturnPolygonPoint(array ($x, $y));
        }

        // The last point is a corner of the polygon because if it has no following point, we change direction
        return $return;
    }

    /**
     * This method draws a polygon with the given points. That to check if
     * our calculations are valid.
     *
     * @param array $points An array of points that define the polygon
     */
    public function drawPolygon(array $points, $r, $g, $b)
    {
        $count = count($points);
        for ($i = 0; ($i < $count); $i++)
        {
            // Draws a line between the current and the next point until the last point is reached
            if (array_key_exists($i + 1, $points))
            {
                list($x1, $y1) = $points[$i];
                list($x2, $y2) = $points[$i + 1];
                $black = imagecolorallocate($this->image, $r, $g, $b);
                imageline($this->image, $x1, $y1, $x2, $y2, $black);
            }
        }
    }

}

Пример использования:

$rectanglesA = array (
        array ( // 1
                array (50, 50), // tx, ty
                array (75, 75), // bx, by
        ),
        array ( // 2
                array (75, 50), // tx, ty
                array (125, 75), // bx, by
        ),
        array ( // 3
                array (125, 50), // tx, ty
                array (175, 75), // bx, by
        ),
        array ( // 4
                array (175, 50), // tx, ty
                array (225, 75), // bx, by
        ),
        array ( // 5
                array (225, 50), // tx, ty
                array (275, 75), // bx, by
        ),
        array ( // 6
                array (275, 50), // tx, ty
                array (325, 75), // bx, by
        ),
        array ( // 7
                array (325, 50), // tx, ty
                array (375, 75), // bx, by
        ),
        array ( // 8
                array (375, 50), // tx, ty
                array (425, 75), // bx, by
        ),
        array ( // 9
                array (320, 42), // tx, ty
                array (330, 50), // bx, by
        ),
        array ( // 10
                array (425, 60), // tx, ty
                array (430, 65), // bx, by
        ),
        array ( // 11
                array (100, 75), // tx, ty
                array (150, 250), // bx, by
        ),
        array ( // 12
                array (150, 125), // tx, ty
                array (250, 150), // bx, by
        ),
        array ( // 13
                array (225, 75), // tx, ty
                array (250, 125), // bx, by
        ),
        array ( // 14
                array (150, 92), // tx, ty
                array (180, 107), // bx, by
        ),
);

$rectanglesB = array (
        array ( // 15
                array (200, 300), // tx, ty
                array (250, 350), // bx, by
        ),
        array ( // 16
                array (250, 250), // tx, ty
                array (300, 300), // bx, by
        ),
        array ( // 17
                array (250, 300), // tx, ty
                array (300, 350), // bx, by
        ),
        array ( // 18
                array (300, 250), // tx, ty
                array (350, 300), // bx, by
        ),
        array ( // 19
                array (300, 300), // tx, ty
                array (350, 350), // bx, by
        ),
        array ( // 20
                array (300, 200), // tx, ty
                array (350, 250), // bx, by
        ),
        array ( // 21
                array (350, 300), // tx, ty
                array (400, 350), // bx, by
        ),
        array ( // 22
                array (350, 200), // tx, ty
                array (400, 250), // bx, by
        ),
        array ( // 23
                array (350, 150), // tx, ty
                array (400, 200), // bx, by
        ),
        array ( // 24
                array (400, 200), // tx, ty
                array (450, 250), // bx, by
        ),
);

$polygonMaker = new PolygonMaker(500, 400);

// Just to get started and see what happens
//$polygonMaker->drawRectangles($rectanglesA, 0xFF, 0x00, 0x00);
//$polygonMaker->drawRectangles($rectanglesB, 0xFF, 0x00, 0x00);

$polygonsA = $polygonMaker->findPolygonsPoints($rectanglesA);
foreach ($polygonsA as $polygon)
{
    $polygonMaker->drawPolygon($polygon, 0x00, 0x00, 0x00);
}

$polygonsB = $polygonMaker->findPolygonsPoints($rectanglesB);
foreach ($polygonsB as $polygon)
{
    $polygonMaker->drawPolygon($polygon, 0x00, 0x00, 0x00);
}

// Display image to see if everything is correct
$polygonMaker->display();

Ответ 4

Только некоторые мысли:

• Итерации по всем углам, чтобы найти тот, который инциден с одним блоком, и, следовательно, угол вашего объединения.
• Оттуда выберите одно направление для итерации, например. всегда против часовой стрелки.
• Проверьте, падает ли край в этом направлении с углу другого устройства, или же следующий угол вдоль этого края падает с краем другого устройства. Любой из них станет следующим углом союза. В противном случае конечная точка этого края будет следующим углом.
• Продолжайте таким образом, перейдя от одного устройства к другому, пока не достигнете начальной точки.