<?php

$rect = array( array(array(0, 10), array(10, 0)),
           array(array(19, 10), array(23, 0)),
           array(array(10, 13), array(19, 0))
       );


$pset = array();
foreach ($rect as $r) {
    list($x1, $y1) = $r[0];
    list($x2, $y2) = $r[1];
    foreach (array($x1.":".$y1, $x2.":".$y1, $x2.":".$y2, $x1.":".$y2) as $pt) {
        if (array_key_exists($pt, $pset)) {
            unset($pset[$pt]);
        } else {
            $pset[$pt] = 1;
        }
    }
}
$pt_len = sizeof($pset);
$points = array();
foreach (array_keys($pset) as $pt) {
    list($x, $y) = explode(":", $pt);
    array_push($points, array(intval($x), intval($y)));
}

$edges_h = array();
$edges_v = array();

/* Sort by x coordinates. In case of equal x, sort by lowest y. */
sort($points);
$i = 0;
while ($i < $pt_len) {
    $curr_x = $points[$i][0];
    while ($i < $pt_len && $points[$i][0] == $curr_x) {
        list($a, $b) = $points[$i];
        list($c, $d) = $points[$i + 1];
        $edges_v[$a.":".$b] = $c.":".$d;
        $edges_v[$c.":".$d] = $a.":".$b;
        $i += 2;
    }
}

/* Sort by y coordinates. In case of equal y, sort by lowest x. */
function y_then_x($a, $b)
{
    if ($a[1] < $b[1] || ($a[1] == $b[1] && $a[0] < $b[0]))
        return -1;
    return 1;
}
usort($points, "y_then_x");
$i = 0;
while ($i < $pt_len) {
    $curr_y = $points[$i][1];
    while ($i < $pt_len && $points[$i][1] == $curr_y) {
        list($a, $b) = $points[$i];
        list($c, $d) = $points[$i + 1];
        $edges_h[$a.":".$b] = $c.":".$d;
        $edges_h[$c.":".$d] = $a.":".$b;
        $i += 2;
    }
}

/* Get all polygons. */
$p = array();
reset($edges_h);
while (!empty($edges_h)) {
    $k = key($edges_h);
    $polygon = array(array($k, 0));
    unset($edges_h[$k]);
    while (1) {
        list($curr, $e) = end($polygon);
        if ($e == 0) {
            $next_vertex = $edges_v[$curr];
            unset($edges_v[$curr]);
            array_push($polygon, array($next_vertex, 1));
        } else {
            $next_vertex = $edges_h[$curr];
            unset($edges_h[$curr]);
            array_push($polygon, array($next_vertex, 0));
        }
        if (end($polygon) == $polygon[0]) {
            /* Closed polygon. */
            array_pop($polygon);
            break;
        }
    }
    /* Remove implementation-markers from polygon. */
    $poly = array();
    foreach($polygon as $v) {
        list($pt, $marker) = $v;
        list($x, $y) = explode(":", $pt);
        array_push($poly, array($x, $y));
        unset($edges_h[$pt]);
        unset($edges_v[$pt]);
    }

    array_push($p, $poly);
}

foreach($p as $pi) {
    foreach($pi as $v) {
        list($x, $y) = $v;
        echo "($x, $y)  ";
    }
    echo "\n";
}

?>