背景：我正在一个小型购物中心的网站上工作，该网站有多个矩形“单元”可供出租。当一个“商店”来时，它可以租一个或多个“单元”，我想生成一个由商店组成的地图（没有未租的单元）
问题：
我有一个由点对定义的矩形列表（单位）[[lefttop_x;lefttop_y];[rightbottom_x;rightbottom_y]]——我想将它们合并为多边形，这样我就可以正确地设置它们的样式（然后我将通过 Canvas/SVG/VML/Raphael.js 进行渲染）。
由于这个（最好是 PHP，但我可以处理伪代码）操作，我想要一个多边形点数组。
谢谢你。
PS：我一直在研究这个，我发现了多个“接近我想要的”的问题+答案，但是我要么太累了，要么我已经与数学脱节太久了:)
O'Rourke 研究了一个与这个问题相关的问题（以及与计算几何相关的许多其他问题），因此，产生了一种非常漂亮的方法来有效地解决它。他的方法在“正交连接点的唯一性”一文中进行了描述，并且在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]，依此类推。重复这个过程，直到我们碰到第一个选择的顶点，就完成了。
快速查看上述算法是：
# 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)]
如果绘制，则分别以蓝色和红色表示多边形，如下所示：
作为简单的基准测试：
这些时间只是在一台繁忙的过时机器上运行 10 次的平均值。矩形是随机生成的。
编辑：
如果需要，在 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);
}
}
?>
<?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 扩展才能工作：
关于性能
以下是一些执行时间：
通过使用XDebug分析执行，我得到了以下结果：
如果有其他人这样做，我还根据 JavaScript 中 mmgp 的答案实现了这个算法。如果其他人试图在 JS 中执行此操作，那么您最好使用我的，而不是自己从其他示例中找出移植的小问题。
我在这里将它作为一个更大项目的一部分开源 - https://github.com/Crabcyborg/crabcyborg/blob/e282aff3a033fba76bba1a7c924f04e6df7b3dc4/shapeup/svg-helper.js#L199
因为它是 JavaScript，我可以现场演示。它用于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;
我不会用数学来解决这个问题，而只会分析。
考虑下图：
在这里，我们一次有 2 个示例，以确保我们将涵盖所有案例。
在第一张图片中，我们有一个特殊情况：第 3、4、5、11、12、13 号矩形创建了一个空白区域，在您的情况下这可能是一个烟雾空间。
在第二张图片中，我们在 16、17、18、19 号矩形之间有一个角......这将在稍后具有它的重要性。
我如何解决问题使用以下内容：
一个角点是一个被写入 2 到 8 次的点：至少 2 次，因为如果我们想象一个矩形 ABCD，角 B 将与 AB 和 BC 共享（因此像素已被放置 2 次）。在矩形 16、17、18、19 的情况下，可以写 8 次，其中一个点与 4 个矩形共享，因此有 8 个边。
边是一组可以写 1 或 2 次（不考虑角）的点：如果边单独，不靠近另一边，则写 1 次，如果靠近另一边，则写 2 次。不靠近另一边的一侧靠近外侧：它应该成为最终多边形的一部分。
所以这是逻辑：
我们写所有的矩形，但不是写像素，而是增加虚拟像素的值
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 的格式化工具有问题）
在这一点上，我们只有多边形和点（在其他几个矩形的中间有一个角）。
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'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);
}
}
}
}
用法示例：
$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();
只是一些想法：