私の問題は「凸包」に関連していると思いますが、同じではありません。図面内のすべての形状は、幅と高さが同じ長方形です。多くは互いに隣接しています。これらの隣接する長方形をポリゴンに結合したい。「凸包」とは異なり、生成されたポリゴンは内部が「中空」になる可能性があります。
利用可能なオープンソースのアルゴリズムはありますか?
20820 次
8 に答える
12
HTML5キャンバスを使用した実験プロジェクトの一環として、隣接するポリゴンをマージするためのアルゴリズムを作成する必要がありました（素晴らしいものは何もありません、ジグソーパズルです:-)結果のポリゴンの穴は自然にサポートされます. Javascript ルーチンは、www dot raymondhill dot net / puzzle-rhill / Jigsawpuzzle-rhill-3 dot js の Polygon.prototype.merge() という名前の関数にあります。
重要なのは、重複しているが反対方向のセグメントを削除することです。大まかな説明: Point は {x:?,y:?}、Segment は {ptA:?,ptB:?}、Contour は {pts:[]} (接続された Point オブジェクトのコレクション)、Polygon は{contours:[]} (Contour オブジェクトのコレクション。)
マージ アルゴリズムは、Segment オブジェクトの大きなファット プールにすべてのセグメントを収集し、重複が排除されます。最初に、ポリゴン A を定義するすべての輪郭のすべてのセグメントがプールに追加されます。次に、Polygon B を定義するすべての輪郭のすべてのセグメントがプールに追加されますが、重複がないかテストして削除します (Point オブジェクトをハッシュキーとして使用すると簡単に実行できます)。
次に、プールからセグメントを取得し (ランダムで問題ありません)、「行き止まり」に到達するまでセグメントを「ウォーク」します。つまり、これ以上セグメントを接続できなくなります。これは 1 つの Contour オブジェクトを形成します。セグメントのコレクション全体が使用されるまで繰り返します。セグメントが使用されると、それらはプールから削除されます。セグメントを「歩く」とは、その終点を取得し、開始点が一致するセグメントを検索することを意味します。
前述のように、結果として、Polygon を定義する Contour オブジェクトのコレクションができました。一部の輪郭は塗りつぶされますが、一部は中空になる可能性があります。輪郭が塗りつぶされているか中空であるかを判断するには、輪郭が時計回りか反時計回りか、またはその面積が正か負かをテストするだけです。私の場合、時計回りの輪郭は塗りつぶされ、反時計回りは中空です。
これが私の実装で、詳細とエラー処理を差し引いたものです。うまくいけば、すぐに機能するように十分にコピー/貼り付けされます。それ以外の場合は、上記の私の JS ファイルを参照してください。
// Point object
function Point(a,b) {
// a=x,b=y
if (b) {
this.x=a;
this.y=b;
}
// a=Point or {x:?,y:?}
else if (a) {
this.x=a.x;
this.y=a.y;
}
// empty
else {
this.x=this.y=0;
}
}
Point.prototype.toHashkey = function() {
return this.x+"_"+this.y;
};
Point.prototype.clone = function() {
return new Point(this);
};
// Segment object
function Segment(a,b) {
this.ptA = new Point(a);
this.ptB = new Point(b);
}
// Contour object
function Contour(a) {
this.pts = []; // no points
if (a) {
if (a instanceof Array) { // assume array of Point objects
var nPts = a.length;
for (var iPt=0; iPt<nPts; iPt++) {
this.pts.push(a[iPt].clone());
}
}
}
}
Contour.prototype.clone = function() {
return new Contour(this);
};
Contour.prototype.addPoint = function(p) {
this.pts.push(p);
};
// Polygon object
function Polygon(a) {
this.contours = []; // no contour
if (a) {
if (a instanceof Polygon) {
var contours = a.contours;
var nContours = contours.length;
for ( var iContour=0; iContour<nContours; iContour++ ) {
this.contours.push(new Contour(contours[iContour]));
}
}
else if ( a instanceof Array ) {
this.contours.push(new Contour(a));
}
}
}
Polygon.prototype.merge = function(other) {
// A Javascript object can be used as an associative array, but
// they are not real associative array, as there is no way
// to query the number of entries in the object. For this
// reason, we maintain an element counter ourself.
var segments={};
var contours=this.contours;
var nContours=contours.length;
var pts; var nPts;
var iPtA; var iPtB;
var idA; var idB;
for (var iContour=0; iContour<nContours; iContour++) {
pts = contours[iContour].pts;
nPts = pts.length;
iPtA = nPts-1;
for ( iPtB=0; iPtB<nPts; iPtA=iPtB++ ) {
idA = pts[iPtA].toHashkey();
idB = pts[iPtB].toHashkey();
if (!segments[idA]) {
segments[idA]={n:0,pts:{}};
}
segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]);
segments[idA].n++;
}
}
// enumerate segments in other's contours, eliminate duplicate
contours = other.contours;
nContours = contours.length;
for ( iContour=0; iContour<nContours; iContour++ ) {
pts = contours[iContour].pts;
nPts = pts.length;
iPtA=nPts-1;
for (iPtB=0; iPtB<nPts; iPtA=iPtB++) {
idA = pts[iPtA].toHashkey();
idB = pts[iPtB].toHashkey();
// duplicate (we eliminate same segment in reverse direction)
if (segments[idB] && segments[idB].pts[idA]) {
delete segments[idB].pts[idA];
if (!--segments[idB].n) {
delete segments[idB];
}
}
// not a duplicate
else {
if (!segments[idA]) {
segments[idA]={n:0,pts:{}};
}
segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]);
segments[idA].n++;
}
}
}
// recreate and store new contours by jumping from one point to the next,
// using the second point of the segment as hash key for next segment
this.contours=[]; // regenerate new contours
var contour;
for (idA in segments) { // we need this to get a starting point for a new contour
contour = new Contour();
this.contours.push(contour);
for (idB in segments[idA].pts) {break;}
segment = segments[idA].pts[idB];
while (segment) {
contour.addPoint(new Point(segment.ptA));
// remove from collection since it has now been used
delete segments[idA].pts[idB];
if (!--segments[idA].n) {
delete segments[idA];
}
idA = segment.ptB.toHashkey();
if (segments[idA]) {
for (idB in segments[idA].pts) {break;} // any end point will do
segment = segments[idA].pts[idB];
}
else {
segment = null;
}
}
}
};
セグメントを「ウォーク」して輪郭を作成する場合、セグメントが複数のセグメントに接続できる場合があります。
+------+-------+
| Poly A | two segments sharing same start point Z
| |
+ +---<---Z---->---+
| | | Poly B |
| | | |
+ +-------+--------+
| |
| |
+------+-------+--------+
これにより、2 つの有効な結果が得られます (上記のアルゴリズムでは、どちらか一方がランダムに導かれます)。
結果 1、1 つの塗りつぶされた輪郭:
+------+--->---+
| Poly A |
| |
+ +---<---+---->---+
| | | |
| | | |
+ +--->---+ +
| |
| |
+------+---<---+--------+
結果 2、1 つの塗りつぶされた輪郭、1 つの中空の輪郭:
+------+--->---+
| Poly A |
| |
+ +---<---+---->---+
| | Hole A| |
| | | |
+ +--->---+ +
| |
| |
+------+---<---+--------+
ただし、コードはすでに穴を処理する準備ができているはずなので、これは問題にはなりません。
その他の重要な詳細: 上記のアルゴリズムは中間点 ('+') を取り除かない。
+------>-------+
| Poly A |
| |
| | +---->---+
| | | Poly B |
| | | |
| | +----<---+
| |
| |
+------<-------+
私の理解では、これはあなたが持っているものです。交点を事前に見つけて追加することで、このようなケースをサポートするようにアルゴリズムを拡張できると思います（私の場合は不要でした）。
+------>-------+
| Poly A |
| |
| + +---->---+
| | | Poly B |
| | | |
| + +----<---+
| |
| |
+------<-------+
この助けを願っています。
PS: ジグソー パズルでアルゴリズムを「テスト」することができます。ピースをスナップして穴を生成するなどしてください。 =http://www.public-domain-photos.com/free-stock-photos-4/travel/los-angeles/los-angeles-skyline.jpg&puzzleRotate=0&puzzleVersion=3
于 2009-06-11T14:28:49.327 に答える
4
General Polygon Clipperのようなものを調べます。基本的に、ユニオン (OR) ポリゴン操作を行っています。それらがすべて長方形であるという事実は、数学を少し簡単にするだけですが、GPC のようなもので簡単に行うことができます.
多くの言語の言語ラッパーもあります。
于 2009-03-13T18:32:32.863 に答える
1
空間処理ライブラリ (JTS [java]、NTS [.net]、GEOS [c++] など、これらはすべてオープン ソースであり、GPC とは異なり、商用アプリで使用できます) を使用している場合は、長方形を結合するだけです。
これを行う一般的な方法は、入力のエッジ (四角形) のグラフを作成し、交差を実行し、結果の内側または外側のエッジにラベルを付け、外側のエッジのみを保持することです。長方形を処理するための特定のアルゴリズムについては知りませんが、前述のように、数学がより簡単になることを除いて、似ている可能性があります。
于 2009-03-13T18:56:25.520 に答える
0
私はもっと簡単な方法を見つけました：
- 黒のイメージを作成します。
- 画像上に白で塗りつぶされた長方形を描きます。これにより、重なったすべての長方形が接続されます。
- ブロブの輪郭を見つけます。
それでおしまい！
于 2013-05-06T07:40:47.727 に答える
0
以下を試してみてはいかがでしょうか。きちんと設計されていれば、これはうまくいくと思います。
基本的に max-x、min-x、max-y、および min-y である最小の外接長方形を見つけます。これが描画用のキャンバスになります。ビット dx X dy の 2D 配列を初期化し、dx、dy はこの外側の長方形の幅で、すべて 0 にします。
私たちの目的は、輪郭、基本的には長方形のいくつかの角を見つけることです。これにより、実際の座標を取得するために拡大できるポイントが得られたら、計算で処理できるレベルまでこの問題を縮小できます。
上記の 2D 配列をスキャンし、指定された長方形のいずれかに含まれている場合は点 1 をマークします。
次に、2D 配列をスキャンして、近傍が 3:1 に分割されているポイントを探します。つまり、3 辺が 1 で 1 辺が 0、またはその逆です。これらのポイントは、輪郭を定義するポイントです。
問題を賢く縮小できれば、複雑さは扱いやすいと思います。
于 2010-06-06T08:21:58.223 に答える
0
境界が妥当な場合は、エッジ カウントの 2D 配列を使用します。そうでない場合は、ネストされた辞書を使用する必要があります。
すべての幅と高さが同じであるため、x、y、および方向 (垂直または水平) の組み合わせによってエッジを一意に識別できます。
サンプル擬似コード: list_of_edges = 新しいリスト arr_count = 新しい int[][][]
fill_with_zeroes(arr_count )
foreach rect
foreach edge
arr_count [edge.x][edge.y][edge.orientation] += 1
foreach edge in arr_count
if count[edge] = 1
list_of_edges.add(edge]
もちろん、エッジを並べ替えたい場合は、もう一度配列を通過する必要があります
foreach edge in arr_count
if count[edge] = 1
add_recursive(edge)
add_recursive(x,y):
for both horizontal and vertical orientations of edge starting at x, y:
count[edge] = 0
if (edge.orientation is horizontal)
return add_recursive( x+1, y)
else
return add_recursive( x, y+1 )
申し訳ありませんが、この疑似コードはかなり雑ですが、一般的なアイデアを理解する必要があります
于 2009-03-14T02:11:55.597 に答える
-1
長方形が接触しているかどうかをテストし、それらの点の和集合で凸包を実行します。
または、長方形のどちら側が接触しているかを手動でテストし、正しい順序でポイントをポリゴン オブジェクトに追加することもできます。
これらは、閉じたポリゴンで十分であることを前提としています (穴をあけることはできません)。
于 2009-03-13T18:37:15.113 に答える