将多个相邻矩形合并为一个多边形
Ada*_*iss 16 php geometry rectangles polygons
背景:我正在一个小型购物中心的网站上工作,该购物中心有多个矩形"单位"可供出租.当一个"商店"出现时,它可以租用一个或多个"单位",我想生成一个由商店组成的地图(无单位)
问题:
我有一个由点对定义的矩形(单位)列表[[lefttop_x;lefttop_y];[rightbottom_x;rightbottom_y]]- 我希望将它们合并为多边形,所以我可以正确地设置它们(我将通过Canvas/SVG/VML/Raphael.js渲染).
- 单位总是矩形
- 单位有不同的大小
- 单位总是相邻的(它们之间没有空格)
由于这个(最好是PHP,但我可以处理伪代码)操作,我想有一个多边形点数组.
谢谢.
PS:我一直在研究这个,我发现了多个'接近我想要的'问题+答案,但我要么太累了,要么我已经与数学脱节了太长时间:)
mmg*_*mgp 19
O'Rourke研究了一个与此问题相关的问题(以及与计算几何相关的许多其他问题),因此,产生了一种非常有效的方法来有效地解决它.他的方法在正交连接点的唯一性中描述,并在http://www.cs.mcgill.ca/~cs644/Godfried/2005/Fall/sdroui9/p0_introduction.html中清楚地说明.请注意,它表示多边形不应共享顶点以便应用此方法,但这种情况经常发生在我们在此讨论的问题中.因此,我们需要做的就是消除共享的顶点.请注意,这仍然会生成一个多边形,并且它是结果需要的多边形.还要注意矩形列表不能包含重复项(我将假设是这种情况,否则预处理它以使列表唯一).
我用Python编写代码,如果对其含义有任何疑问,请随意提问.以下是实施的概述.我们从根据OP的符号描述的矩形列表开始.然后我们获得每个矩形的四个顶点,沿途丢弃共享顶点.使用a可以有效地实现这一点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'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
结果是多边形的有序顶点列表:
[(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次运行的平均值.随机生成矩形.
编辑:
如果需要,在PHP中实现.
小智 14
这是我的解决方案:
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>
它是如何工作的？
该脚本标识并删除所有"重叠"段.例如:
首先,每个矩形的边在与该矩形边的边交叉处分开.
例如,考虑B矩形的B2-B3侧:"splitSides"方法将其分为B2-D1,D1-D4和D4-B3段.
然后"removeDuplicates"方法删除所有重叠(重复)段.
例如,D1-D4段是重复的,因为它出现在B矩形和D矩形中.
最后,"getSides"方法返回剩余段的列表,而"getPoints"方法返回多边形点列表.
"draw"方法仅用于结果的图形表示,并且需要GD扩展才能工作:
关于表现
以下是一些执行时间:
- 10个矩形:0,003秒
- 100个矩形:0,220秒
- 1000个矩形:4,407秒
- 2000个矩形:13,448秒
通过使用XDebug分析执行情况,我得到了以下结果:
