奥罗克已经研究了与此有关之一(另外还有许多其他涉及到计算几何)问题,因此,产生了一个非常漂亮的方法,有效地解决它。 他的方法在论文中描述的正交连接最点的唯一性 ,并且也明显地示出在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]
等。 重复这个过程,直到我们碰到的第一个选择的顶点,就这么干。
快速查看所提到的算法是:
- 由最低的X排序分,最低ÿ
- 通过每一列去创建该列中的顶点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秒
- 万个矩形:〜0.62秒
- 100000个矩形:〜8.68秒
这些时间仅仅是10次忙碌的过时的机器上的平均。 矩形,随机生成的。
编辑:
在PHP执行如果需要的话。
这里是我的解决方案:
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>
它是如何工作的?
脚本识别并删除所有“重叠”链段。 例如:
首先,每个矩形的边在与adiacent矩形的边的交叉点被分割。
例如,考虑的乙矩形的B2-B3方:“splitSides”方法拆分成的B2-D1,D1-D4和D4-B3的段。
那么“removeDuplicates”方法移除所有重叠(重复)链段。
例如,D1-D4段是重复的,因为它出现无论是在乙矩形,并在d矩形。
最后,“getSides”方法返回剩余的部分名单,而“getPoints”方法返回多边形点列表。
“绘制”方法只对结果的图形表示,并要求GD扩展的工作:
关于性能
下面是一些执行时间:
- 10个矩形:0003秒
- 100个矩形:0220秒
- 1000个矩形:4407秒
- 2000和矩形:13448秒
通过绘制与执行的XDebug ,我已经得到了以下结果:
我不会用数学来解决这个问题,但只有分析。
请看下面的图片:
在这里,我们有2个例子,在一次,以确保我们将涵盖所有情况。
我怎么解决这个问题使用以下的事情:
因此,这里的逻辑:
- 我们创建一个同样大小的整个图像的虚拟空间,填补零(0)。
我们写的所有的矩形,但不是书面方式像素,我们增加了虚拟像素的值
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的格式化工具的问题)
- 我们删除具有大于2的值的所有虚拟点,除了我们设置为1角
在这一点上,我们有多边形,和单独的点(其中有在其他几个矩形的中间的拐角)。
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个像素。
当我们发现一个点,我们保存它,尝试迭代一个方向(上/左/右/底部),继续前进,同时移除指向这个方向,直到不再有一点:这是多边形的一个角落。 我们将继续这样,直到它无法移动到任何方向:这意味着我们在多边形的结束。
现在,你会得到一个2渔政船阵:第一渔政船是多边形的列表(在第一个例子的情况下),而第二渔政船是描述你的多边形点的名单。 对于每一个多边形,你只需要遍历这些点并加入当前的下面一个让你的多边形。
现在怎么样的结果呢?
执行:
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();