23

Background: I am working on a site for small shopping center, which has multiple rectangular "units" to rent. When a "shop" comes, it can rent one or multiple "units", and I'd like to generate a map consisting of shops (sans unrented units)

Problem:

I have a list of rectangles (units), defined by pairs of points – [[lefttop_x;lefttop_y];[rightbottom_x;rightbottom_y]] – and I want to merge them into polygons, so I can properly style them (which I will then render via Canvas/SVG/VML/Raphael.js).

  • Units are always rectangles
  • Units have different sizes
  • Units are always adjacent (there is no space between them)

As a result of this (preferably PHP, but I can deal with pseudocode) operation, I'd like to have an array of polygons points.

Rectangle merging – visual cue

Thank you.

P.S.: I've been looking into this, and I found multiple 'close to what I want' questions+answers, but I am either too tired or I've been out of touch with maths for too long :)

7
  • 1
    out of touch with maths for too long I know that feeling...
    – Shikiryu
    Dec 6, 2012 at 15:03
  • Are your coordinates exact integers, or do you have to worry about rounding effects?
    – MvG
    Dec 7, 2012 at 9:17
  • @MvG: Exact integers (pixel position from [0;0] to be exact)
    – Adam Kiss
    Dec 8, 2012 at 0:53
  • Fortunately the optimal solution doesn't involve any kind of math that a child couldn't understand :)
    – mmgp
    Dec 16, 2012 at 18:08
  • The problem itself isn't in understanding the solution, it's coming up with optimal algorithm :)
    – Adam Kiss
    Dec 16, 2012 at 18:52

5 Answers 5

32

O'Rourke has studied a problem that is related to this one (along many others that relate to Computational Geometry) and as a consequence, produced a very beautiful method to efficiently solve it. His method is described in the paper Uniqueness of orthogonal connect-the-dots and is also clearly illustrated at http://www.cs.mcgill.ca/~cs644/Godfried/2005/Fall/sdroui9/p0_introduction.html. Note that it says that the polygon shouldn't share vertices in order to apply this method, but this happens very often in the problem we are discussing here. Thus, all we need to do is to eliminate vertices that are shared. Note that this still produces a polygon, and it is the polygon that is wanted as result. Also observe that the list of rectangles must not contain duplicates (I will assume that is the case, otherwise preprocess it to make the list unique).

I've used Python to code it, and if there is any doubt about its meaning, feel free to ask. Here is an overview of the implementation. We start with a list of rectangles described according to OP's notation. Then we obtain the four vertices of each rectangle, discarding shared vertices along the way. This is efficiently achieved using a set. Now we simply apply the algorithm mentioned. Note that I use two hash tables, edges_h (for horizontal edges) and edges_v (for vertical edges), to store the polygon edges. These hash tables effectively work as an undirected graph. Thus, after all the edges are obtained it is easy and fast to obtain the ordered vertices of the polygon. Pick any (key, value) from the hash table edges_h, for example. Now, the next ordered vertex is the one given by edges_v[value] = next_value, and the next one by edges_h[next_value] and so on. Repeat this process till we hit the first chosen vertex, and it is done.

A quick view into the mentioned algorithm is:

  1. Sort points by lowest x, lowest y
  2. Go through each column and create edges between the vertices 2i and 2i + 1 in that column
  3. Sort points by lowest y, lowest x
  4. Go through each row and create edges between the vertices 2i and 2i + 1 in that row.
# 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

the result is a list of ordered vertices for the polygon:

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

We can also experiment with a more complicated layout:

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

which is represented as the following set of rectangles:

enter image description here

and the method produces the following lists:

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

which, if drawn, represents the polygons in blue and red, respectively, as in:

enter image description here

As simple benchmarks go:

  • 1000 rectangles: ~ 0.04 seconds
  • 10000 rectangles: ~ 0.62 seconds
  • 100000 rectangles: ~ 8.68 seconds

These timings are simply the average of 10 runs on a busy outdated machine. Rectangles were randomly generated.

EDIT:

Implementation in PHP if needed.

16
  • This implementation has the behavior of keeping shared vertices if they are shared by an odd number of rectangles. As a consequence, it maintains an even number of vertices per column and per row and the algorithm works.
    – mmgp
    Dec 13, 2012 at 15:29
  • A lot of reading, and thanks for the implementation, I'll look into this over weekend.
    – Adam Kiss
    Dec 14, 2012 at 10:47
  • Thank you for your great contribution, I went with the other solution. Great links, and I at least upboted. Thank you.
    – Adam Kiss
    Dec 17, 2012 at 0:43
  • Very weird decision, by the way. You picked a more complicated implementation with a higher execution time. I guess it is time for me to leave SO anyway, but thanks for reading the post. Plus the solution accepted doesn't give the vertices as it stands, well.. what a loss of time.
    – mmgp
    Dec 17, 2012 at 0:54
  • 1
    Never mind, I found another solution. I didn't understand the explanation, but it mentioned that looking at the edges is interesting, and that's what I did. From there I found an algorithm that cancels touching edges (simple for regular squares like in QR codes) and combines the remaining edges. It works very well, here's the code: github.com/ygoe/qrcode-generator/blob/5bb2d93e10/js/…
    – ygoe
    Jun 3, 2021 at 9:57
15
+250

Here is my solution:

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>

How does it work?

The script identifies and removes all "overlapping" segments. For example:
example

First, the sides of each rectangle are split at the intersections with the sides of the adiacent rectangle.
For example, consider the B2-B3 side of the B rectangle: the "splitSides" method splits it into the B2-D1, D1-D4 and D4-B3 segments.
Then the "removeDuplicates" method removes all the overlapping (duplicate) segments.
For example, the D1-D4 segment is a duplicate, since it appears either in the B rectangle and in the D rectangle.
Finally the "getSides" method returns the list of the remaining segments, while the "getPoints" method returns the list of the polygon points.
The "draw" methods are only for the graphical representation of the result, and require the GD extension to work:
result

About performance

Here are some execution times:

  • 10 rectangles: 0,003 seconds
  • 100 rectangles: 0,220 seconds
  • 1000 rectangles: 4,407 seconds
  • 2000 rectangles: 13,448 seconds

By profiling the execution with XDebug, I've got the following results:

cachegrind

9
  • Isn't splitSides quadratic in time ?
    – mmgp
    Dec 12, 2012 at 13:55
  • @mmgp To be honest, when I wrote the code I didn't consider the performance as an issue, since Adam didn't specify the maximum number of rentable units he has to deal with; my only concern was to find a simple solution. Hence, any suggestion to improve/optimize the code is welcome.
    – user1419445
    Dec 12, 2012 at 20:58
  • I didn't look into the code at all, but isn't it strange that removeDuplicates is taking longer than splitSides on your last added figure ? It should take linear time, but the PHP functions involved are making it worse than the quadratic function. I like how this solution goes, by the way, it is just that splitSides needs a smarter sweeping technique if someone wants to use it on many rectangles (for some value of many).
    – mmgp
    Dec 12, 2012 at 21:13
  • @mmgp I agree with you: either the removeDuplicates and the splitSides functions should be improved to provide a better performance with many rectangles.
    – user1419445
    Dec 12, 2012 at 21:32
  • Anyway, your functions should be faster than mine. You're a hard bounty hunter :-) But one more thing: OP wants a list of points that describe the polygon so that he can use some plugins to draw it. But you give a list of lines, and that will "not be easy" to transform those lines to points (in fact, points should logically be sorted so that by associating each one, one by one, we can get the polygon). Any way to solve that ? (this shouldn't be difficult, by finding common points on each line, but here you'll have a complete answer)
    – Alain
    Dec 12, 2012 at 23:11
2

Just some thoughts:

  1. Iterate over all corners to find one which is incident with only one unit, and therefore a corner of your union.
  2. From there choose one direction to iterate, e.g. always counter-clockwise.
  3. Check whether the edge in this direction is incident with a corner of another unit, or whether the next corner along this edge is incident with an edge of another unit. Either of these would form the next corner of the union. Otherwise the endpoint of this edge is the next corner.
  4. Continue in this fashion, moving from one unit to the next, until you reach your starting point.
1
  • Thanks! I've just started a bounty, because even though you've given great suggestions, I don't really see myself algorithmizing this. ^^
    – Adam Kiss
    Dec 9, 2012 at 12:08
2

I will not use mathematics to solve this problem, but only analysis.

Consider the following image :

enter image description here

Here, we have 2 examples at once, to be sure we will cover every cases.

  • in the first image, we have a special case : the rectangles no 3, 4, 5, 11, 12, 13 creates an empty area, this may be a smoke space in your case.

  • in the second image, we have a corner between rectangles no 16, 17, 18, 19... this will have its importance later.

How I solved the problem uses the following things :

  • A corner is a point that have been written from 2 to 8 times : at least 2 because if we imagine a rectangle ABCD, the corner B will be shared with AB and BC (so the pixel has been put 2 times). It can be written 8 times in the case of the rectangles 16, 17, 18, 19, where one point is shared with 4 rectangles, so 8 sides.

  • A side is a set of points that can be written 1 or 2 times (without considering corners) : 1 time if the side is alone, not close to another side, and 2 times if the side close to another one. And a side who is not close to another one is close to the outside : it should take part of the final polygon.

So here is the logic :

  • We create a virtual space of the same size as the whole image, filled of zeros ( 0 ).
  • We write all rectangles, but instead of writting pixels, we increment the value of the virtual pixel

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

(Sorry, it looks like my indentation has problems with the SO's formatting tool)

  • We remove all virtual points that have a value greater than 2, except corners that we set to 1

At this point, we have polygons, and points alone (where there is a corner at the middle of several other rectangles).

                              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                   
  • Now we need to look for one or several polygons (we may have several polygons when we're in the 11 12 13 14 3 4 5 rectangles's case). This mean, search a point into our virtual image.

  • If the point is alone (see above), it has no point at its top, left, bottom or right side, this is a corner (we saved our corner earlier) in the middle of several other rectangles. This is quite tricky, but works if all your rectangles are greater than 4 pixels.

  • When we find a point, we store it, try to iterate one direction (top/left/right/bottom) and go ahead while removing points to this direction until there is no more point : this is one corner of the polygon. We continue this way until it is not possible to move to any direction : this means we are at the end of the polygon.

  • Now, you get a 2-dimention array : the first dimention is the list of polygons (in the case of the first example), and the second dimention is the list of the points that describe your polygon. For each polygons, you just have to iterate those points and join the current one to the following one to get your polygon.

What about the result now ?

enter image description here

Implementation :

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

}

Usage example :

$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();
4
  • Thanks, it's an intersting approach! Even if cached, won't this calculation be in range, say, seconds? (say three maps, 50 rectangles, 20-30 intersections)
    – Adam Kiss
    Dec 10, 2012 at 23:02
  • It depends on the size of your map. If you have a 10000x10000 map, this of course will be slow. Here, I work on a 500x500 map but it is possible to work on a smaller map and multiply each coordiate by N when rendering polygons. Large numbers are useful for a gd sample, but reduce your scale in a real usecase.
    – Alain
    Dec 11, 2012 at 7:04
  • Interesting, thanks! I'll go through this over the weekend :)
    – Adam Kiss
    Dec 14, 2012 at 10:47
  • Nice, different solution. Thank you — went with the other one though.
    – Adam Kiss
    Dec 17, 2012 at 0:44
2

If any one else comes by this, I've also implemented this algorithm based off of the answer from mmgp in JavaScript. If anyone else is trying to do this in JS, you're probably better off using mine than having to figure out the little issues with porting this yourself from the other examples.

I have it open sourced as part of a larger project here - https://github.com/Crabcyborg/crabcyborg/blob/e282aff3a033fba76bba1a7c924f04e6df7b3dc4/shapeup/svg-helper.js#L199

Since it's JavaScript, I can demo it live. It's used in the "polygon per color" example on https://crabcyb.org/experiment/shapeup-svg/

const pointsToPolygons = (points, size) => {
    let edges_v = {}, edges_h = {};
    const setEdges = (edges, cmp, e) => {
        points.sort(cmp);
        let edge_index = 0;
        const length = points.length;
        while(edge_index < length) {
            const curr = points[edge_index][e];
            do {
                edges[points[edge_index]] = points[edge_index+1];
                edges[points[edge_index+1]] = points[edge_index];
                edge_index += 2
            } while(edge_index < length && points[edge_index][e] == curr);
        }
    };
    setEdges(edges_v, xThenY, 0);
    setEdges(edges_h, yThenX, 1);
    
    let polygon = [], keys;
    while((keys = Object.keys(edges_h)).length) {
        const [ key ] = keys;
        delete edges_h[key];
        
        const first_vertex = new V2(key);
        let previous = [first_vertex.toArray(), 0];
        let vertices = [first_vertex];

        while(1) {
            const [edge_index, edge] = previous;
            const edges = [edges_v, edges_h][edge];
            const next_vertex = new V2(edges[edge_index]);
            const next = [next_vertex.toArray(), 1-edge];
            delete edges[edge_index];

            if(first_vertex.compare(next_vertex)) {
                break;
            }

            vertices.push(next_vertex);
            previous = next;
        }

        let scaled_vertices = [];
        for(let vertex of vertices) {
            scaled_vertices.push(vertex.scale(size).toArray());

            const edge_index = vertex.toArray();
            delete edges_v[edge_index];
            delete edges_h[edge_index];
        }

        polygon.push(scaled_vertices);
    }

    return polygon;
};

function V2(x,y) {
    if(Array.isArray(x)) {
        y = x[1];
        x = x[0];
    } else {
        switch(typeof x) {
            case 'object': 
                y = x.y;
                x = x.x;
            break;

            case 'string':
                const split = x.split(',');
                x = parseInt(split[0]);
                y = parseInt(split[1]);
            break;
        }
    }

    this.x = x;
    this.y = y;
}

V2.prototype = {
    scale: function(scale) {
        return new V2(this.x * scale, this.y * scale);
    },
    compare: function(v) {
        return this.x == v.x && this.y == v.y;
    },
    toArray: function() {
        return [this.x, this.y];
    }
};

const xThenY = (a,b) => a[0]<b[0] || (a[0]==b[0] && a[1]<b[1]) ? -1 : 1;
const yThenX = (a,b) => a[1]<b[1] || (a[1]==b[1] && a[0]<b[0]) ? -1 : 1;
1
  • Hi Mike, thank you for this code. Could you provide a simple usage example?
    – SERG
    Feb 20, 2022 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.