背景：私は、複数の長方形の「ユニット」を借りることができる小さなショッピングセンターのサイトで作業しています。「お店」が来ると、1つまたは複数の「ユニット」を借りることができます。お店で構成されるマップを作成したいと思います（未レンタルのユニットはありません）。
問題：
ポイントのペアで定義された長方形（ユニット[[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の表記法に従って記述された長方形のリストから始めます。次に、各長方形の4つの頂点を取得し、途中で共有頂点を破棄します。これは、を使用して効率的に実現されsetます。ここで、前述のアルゴリズムを適用するだけです。ポリゴンエッジを格納するために、 edges_h（水平エッジ用）と（垂直エッジ用）の2つのハッシュテーブルを使用していることに注意してください。edges_vこれらのハッシュテーブルは、無向グラフとして効果的に機能します。したがって、すべてのエッジが取得された後、ポリゴンの順序付けられた頂点を取得するのは簡単かつ迅速です。edges_hたとえば、ハッシュテーブルから任意の（キー、値）を選択します。さて、次の順序付けられた頂点はによって与えられたものですedges_v[value] = next_value、次の1つなど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
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」メソッドはポリゴンポイントのリストを返します。
「描画」メソッドは、結果をグラフィカルに表現するためだけのものであり、GD拡張機能が機能する必要があります。
パフォーマンスについて
実行時間は次のとおりです。
XDebugを使用して実行をプロファイリングすると、次の結果が得られます。
他の誰かがこれをやってくるなら、私はJavaScriptのmmgpからの答えに基づいてこのアルゴリズムも実装しました。他の誰かがJSでこれを行おうとしている場合は、他の例からこれを自分で移植する際の小さな問題を理解するよりも、私のものを使用する方がおそらく良いでしょう。
私はここでより大きなプロジェクトの一部としてオープンソースを持っています-https ://github.com/Crabcyborg/crabcyborg/blob/e282aff3a033fba76bba1a7c924f04e6df7b3dc4/shapeup/svg-helper.js#L199
JavaScriptなので、ライブでデモできます。https://crabcyb.org/experiment/shapeup-svg/の「polygonpercolor」の例で使用されています
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の長方形は空の領域を作成します。これは、あなたの場合は煙のスペースである可能性があります。
2番目の画像では、16、17、18、19番の長方形の間に角があります...これは後で重要になります。
私が問題を解決した方法は、次のものを使用します：
コーナーは、2〜8回書き込まれたポイントです。長方形ABCDを想像すると、コーナーBはABおよびBCと共有されるため（ピクセルは2回配置されます）、少なくとも2回です。長方形16、17、18、19の場合、1つのポイントが4つの長方形、つまり8つの辺で共有される場合に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
次に、1つまたは複数のポリゴンを探す必要があります（11 12 13 14 3 4 5の長方形の場合、複数のポリゴンがある可能性があります）。つまり、仮想画像内のポイントを検索します。
ポイントが単独の場合（上記を参照）、その上、左、下、または右側にポイントはありません。これは、他のいくつかの長方形の中央にあるコーナーです（前にコーナーを保存しました）。これは非常に注意が必要ですが、すべての長方形が4ピクセルより大きい場合に機能します。
ポイントを見つけたら、それを保存し、1つの方向（上/左/右/下）を繰り返して、ポイントがなくなるまでこの方向へのポイントを削除します。これはポリゴンの1つのコーナーです。どの方向にも移動できなくなるまでこの方法を続けます。これは、ポリゴンの終わりにいることを意味します。
これで、2次元配列が得られます。最初の次元はポリゴンのリスト（最初の例の場合）であり、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();
いくつかの考え：