php - poligonos - como unir dos mapas en arcgis

Fusionar múltiples rectángulos adyacentes en un polígono

Question

Antecedentes : Estoy trabajando en un sitio para un centro comercial pequeño, que tiene múltiples "unidades" rectangulares para alquilar. Cuando llega una "tienda", puede alquilar una o varias "unidades", y me gustaría generar un mapa que conste de tiendas (sin unidades sin alquilar)

Problema

Tengo una lista de rectángulos ( unidades ), definida por pares de puntos - [[lefttop_x;lefttop_y];[rightbottom_x;rightbottom_y]] - y quiero unirlos en polígonos, para que pueda aplicarles un estilo adecuado (que luego render a través de Canvas / SVG / VML / Raphael.js).

• Las unidades son siempre rectángulos.
• Las unidades tienen diferentes tamaños.
• Las unidades son siempre adyacentes (no hay espacio entre ellas)

Como resultado de esta operación (preferiblemente PHP, pero puedo lidiar con pseudocódigo), me gustaría tener una matriz de puntos de polígonos.

Gracias.

PD: He estado investigando esto y encontré varias preguntas y respuestas "cercanas a lo que quiero", pero o bien estoy demasiado cansado o no he tenido contacto con las matemáticas durante demasiado tiempo :)

Answer 1

Aquí está mi solución:

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>

¿Como funciona?

El script identifica y elimina todos los segmentos "superpuestos". Por ejemplo:

Primero, los lados de cada rectángulo se dividen en las intersecciones con los lados del rectángulo adiacent.
Por ejemplo, considere el lado B2-B3 del rectángulo B: el método "splitSides" lo divide en los segmentos B2-D1, D1-D4 y D4-B3.
Luego, el método "removeDuplicates" elimina todos los segmentos superpuestos (duplicados).
Por ejemplo, el segmento D1-D4 es un duplicado, ya que aparece en el rectángulo B y en el rectángulo D.
Finalmente, el método "getSides" devuelve la lista de los segmentos restantes, mientras que el método "getPoints" devuelve la lista de los puntos de polígono.
Los métodos de "dibujo" son solo para la representación gráfica del resultado, y requieren que la extensión GD funcione:

Sobre el rendimiento

Aquí hay algunos tiempos de ejecución:

• 10 rectángulos: 0,003 segundos
• 100 rectángulos: 0,220 segundos
• 1000 rectángulos: 4,407 segundos
• 2000 rectángulos: 13,448 segundos

Al perfilar la ejecución con XDebug , obtuve los siguientes resultados:

Answer 2

No usaré las matemáticas para resolver este problema, sino solo el análisis.

Considera la siguiente imagen:

Aquí, tenemos 2 ejemplos a la vez, para estar seguros de que cubriremos todos los casos.

• En la primera imagen, tenemos un caso especial: los rectángulos no 3, 4, 5, 11, 12, 13 crean un área vacía, esto puede ser un espacio de humo en su caso.

• En la segunda imagen, tenemos una esquina entre los rectángulos no 16, 17, 18, 19 ... esto tendrá su importancia más adelante.

Cómo resolví el problema usa las siguientes cosas:

• Una esquina es un punto que se ha escrito de 2 a 8 veces: al menos 2 porque si imaginamos un rectángulo ABCD, la esquina B se compartirá con AB y BC (por lo que el píxel se ha colocado 2 veces). Se puede escribir 8 veces en el caso de los rectángulos 16, 17, 18, 19, donde un punto se comparte con 4 rectángulos, por lo que 8 lados.

• Un lado es un conjunto de puntos que se pueden escribir 1 o 2 veces (sin considerar esquinas): 1 vez si el lado está solo, no cerca de otro lado, y 2 veces si el lado está cerca de otro. Y un lado que no está cerca de otro está cerca del exterior: debe formar parte del polígono final.

Así que aquí está la lógica:

• Creamos un espacio virtual del mismo tamaño que toda la imagen, lleno de ceros (0).

• Escribimos todos los rectángulos, pero en lugar de escribir píxeles, incrementamos el valor del píxel virtual

                            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                             
        (...)

(Lo siento, parece que mi sangría tiene problemas con la herramienta de formato de SO)

• Eliminamos todos los puntos virtuales que tienen un valor mayor que 2, excepto las esquinas que configuramos en 1

En este punto, tenemos polígonos y solo puntos (donde hay una esquina en medio de varios otros rectángulos).

                              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                   

• Ahora debemos buscar uno o varios polígonos (es posible que tengamos varios polígonos cuando estemos en el caso de los 11 12 13 14 3 4 5 rectángulos). Esto significa, buscar un punto en nuestra imagen virtual.

• Si el punto está solo (ver arriba), no tiene ningún punto en su parte superior, izquierda, inferior o derecha, esta es una esquina (antes hemos guardado nuestra esquina) en medio de varios otros rectángulos. Esto es bastante complicado, pero funciona si todos los rectángulos tienen más de 4 píxeles.

• Cuando encontramos un punto, lo almacenamos, intentamos iterar una dirección (arriba / izquierda / derecha / abajo) y seguimos eliminando puntos en esta dirección hasta que no haya más puntos: esta es una esquina del polígono. Continuamos de esta manera hasta que no sea posible moverse en ninguna dirección: esto significa que estamos al final del polígono.

• Ahora, obtienes una matriz de 2 dimensiones: la primera dimensión es la lista de polígonos (en el caso del primer ejemplo), y la segunda dimensión es la lista de los puntos que describen tu polígono. Para cada polígono, solo tienes que iterar esos puntos y unir el actual al siguiente para obtener tu polígono.

¿Qué pasa con el resultado ahora?

Implementación:

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''s 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''s 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);
            }
        }
    }

}

Ejemplo de uso:

$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''s 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();

Answer 3

O''Rourke ha estudiado un problema relacionado con este (junto con muchos otros relacionados con la geometría computacional) y, como consecuencia, produjo un método muy hermoso para resolverlo de manera eficiente. Su método se describe en el documento Uniqueness of connect-the-dots ortogonal y también se ilustra claramente en http://www.cs.mcgill.ca/~cs644/Godfried/2005/Fall/sdroui9/p0_introduction.html . Tenga en cuenta que dice que el polígono no debería compartir vértices para aplicar este método, pero esto sucede muy a menudo en el problema que estamos discutiendo aquí. Por lo tanto, todo lo que tenemos que hacer es eliminar los vértices que se comparten. Tenga en cuenta que esto todavía produce un polígono, y es el polígono que se desea como resultado. También tenga en cuenta que la lista de rectángulos no debe contener duplicados (asumiré que ese es el caso, de lo contrario preproceselo para hacer la lista única).

He utilizado Python para codificarlo, y si tiene alguna duda sobre su significado, no dude en preguntar. Aquí hay una descripción general de la implementación. Comenzamos con una lista de rectángulos descritos de acuerdo con la notación de OP. Luego obtenemos los cuatro vértices de cada rectángulo, descartando vértices compartidos en el camino. Esto se logra de manera eficiente utilizando un set . Ahora simplemente aplicamos el algoritmo mencionado. Tenga en cuenta que utilizo dos tablas hash, edges_h (para bordes horizontales) y edges_v (para bordes verticales), para almacenar los bordes de polígono. Estas tablas hash funcionan efectivamente como un gráfico no dirigido. Por lo tanto, después de obtener todos los bordes, es fácil y rápido obtener los vértices ordenados del polígono. Seleccione cualquier (clave, valor) de la tabla hash edges_h , por ejemplo. Ahora, el siguiente vértice ordenado es el dado por edges_v[value] = next_value , y el siguiente por edges_h[next_value] y así sucesivamente. Repita este proceso hasta que lleguemos al primer vértice elegido, y listo.

Una vista rápida en el algoritmo mencionado es:

1. Ordena los puntos por la más baja x, la más baja y
2. Recorra cada columna y cree bordes entre los vértices 2i y 2i + 1 en esa columna
3. Ordena los puntos por la más baja y, la más baja x
4. Recorra cada fila y cree bordes entre los vértices 2i y 2i + 1 en esa fila.

# These rectangles resemble the OP''s 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

el resultado es una lista de vértices ordenados para el polígono:

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

También podemos experimentar con un diseño más complicado:

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]])

que se representa como el siguiente conjunto de rectángulos:

y el método produce las siguientes listas:

[(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)]

el cual, si está dibujado, representa los polígonos en azul y rojo, respectivamente, como en:

Como simples puntos de referencia van:

• 1000 rectángulos: ~ 0.04 segundos
• 10000 rectángulos: ~ 0.62 segundos
• 100000 rectángulos: ~ 8.68 segundos

Estos tiempos son simplemente el promedio de 10 ejecuciones en una máquina desactualizada y ocupada. Los rectángulos fueron generados al azar.

EDITAR:

Implementación en PHP si es necesario.

Answer 4

Solo algunos pensamientos:

1. Iterar en todas las esquinas para encontrar una que incida con solo una unidad, y por lo tanto una esquina de su unión.
2. Desde allí, elija una dirección para iterar, por ejemplo, siempre en sentido contrario a las agujas del reloj.
3. Verifique si el borde en esta dirección incide con una esquina de otra unidad, o si la siguiente esquina a lo largo de este borde incide con un borde de otra unidad. Cualquiera de estos formaría la siguiente esquina de la unión. De lo contrario, el punto final de este borde es la siguiente esquina.
4. Continúe de esta manera, moviéndose de una unidad a la siguiente, hasta que alcance su punto de partida.