最近、複雑なポリゴンを複雑でないポリゴンに変換する方法について考えています。これはどのように行われますか？
これは私がやりたいことの一種です：
最後に JavaScript を使用しますが、どのような形式のソリューションでも問題ありません (言語、アルゴリズム、または単純な英語)。
user263078
質問する
3458 次
6 に答える
6
ポリゴンを手で描くときに使用するのと同じヒューリスティックを使用します (これはおそらく、そのポリゴンを計算するための最も数学的に効率的な方法ではありませんが、おそらく理解し/実装するのが最も簡単です)。
- ポイントから開始
- 現在のポイントと到達しようとしているポイントの間のすべての交点を見つける
- 何も存在しない場合は、次のポイントに描画します
- ある場合は、そこまで描画し、次のポイントをそこから次のポイントに設定します
- 最初に戻っていない場合は、2 に進みます。
jsfiddle での実装例を次に示します。注: 最適化されていません。
于 2012-05-20T12:45:18.127 に答える
2
これは遅い回答ですが、これはJavascript Clipper Libraryを使用して行うことができます。目的の操作は単純化 (内部的にユニオン操作を使用) であり、エッジが他のエッジと交差する自己交差を削除します。
ノート！Javascript Clipper 5 は、すべての場合において、ソリューションが真に単純なポリゴンのみで構成されていることを保証することはできません。このような特殊なケースは、エッジに接する頂点です。Clipper 6 (Javascript バージョンはまだ準備ができていません) は、これらのような特殊なケースも処理できます。
Javascript Clipper Main Demo を使用してポリゴンを単純化する
Javascript Clipper Main Demoを使用して Clipper で遊ぶことができます。Polygons-Custom をクリックすると、そこに独自のポリゴンを入力して、必要な操作を行うことができます。
あなたの例を見てみましょう:
[[7,86, 196,24, 199,177, 47,169, 51,21, 224,102, 223,146, 7,140, 7,86]]
デモでこれらの点を (サブジェクトまたはクリップとして) 入力すると、次の多角形が得られます。
次に、次のソリューションを生成する単純化操作を行います。
Polygon Explorer で Solution をクリックすると、単純化されたポリゴンの座標が表示されます: [[199,177, 47,169, 47.75,141.13, 7,140, 7,86, 49.62,72.02, 51,21, 114.51,50.73, 196,24, 197.28 ,89.49, 224,102, 223,146, 198.38,145.32]]
ポリゴンの単純化のコード例
最後に、完全に機能するコードをJSBINに入れます。これには SVG 描画関数が含まれているため、かなり長くなります。
<html>
<head>
<title>Javascript Clipper Library / Simplifying Polygons</title>
<script src="clipper.js"></script>
<script>
function draw() {
var subj_polygons = [[{"X":7,"Y":86},{"X":196,"Y":24},{"X":199,"Y":177},{"X":47,"Y":169},{"X":51,"Y":21},{"X":224,"Y":102},{"X":223,"Y":146},{"X":7,"Y":140},{"X":7,"Y":86}]];
var scale = 100;
subj_polygons = scaleup(subj_polygons, scale);
var cpr = new ClipperLib.Clipper();
cpr.AddPolygons(subj_polygons, ClipperLib.PolyType.ptSubject);
var solution_polygons = new ClipperLib.Polygons();
solution_polygons = cpr.SimplifyPolygons(subj_polygons, ClipperLib.PolyFillType.pftNonZero);
//console.log(JSON.stringify(solution_polygons));
var svg = '<svg style="margin-top:10px; margin-right:10px;margin-bottom:10px;background-color:#dddddd" width="240" height="200">';
svg += '<path stroke="black" fill="yellow" stroke-width="2" d="' + polys2path(solution_polygons, scale) + '"/>';
svg += '</svg>';
document.getElementById('svgcontainer').innerHTML = svg;
}
// helper function to scale up polygon coordinates
function scaleup(poly, scale) {
var i, j;
if (!scale) scale = 1;
for(i = 0; i < poly.length; i++) {
for(j = 0; j < poly[i].length; j++) {
poly[i][j].X *= scale;
poly[i][j].Y *= scale;
}
}
return poly;
}
// converts polygons to SVG path string
function polys2path (poly, scale) {
var path = "", i, j;
if (!scale) scale = 1;
for(i = 0; i < poly.length; i++) {
for(j = 0; j < poly[i].length; j++) {
if (!j) path += "M";
else path += "L";
path += (poly[i][j].X / scale) + ", " + (poly[i][j].Y / scale);
}
path += "Z";
}
return path;
}
</script>
</head>
<body onload="draw()">
<h2>Javascript Clipper Library / Simplifying Polygons</h2>
This page shows an example of simplifying polygon and drawing it using SVG.
<div id="svgcontainer"></div>
</body>
</html>
于 2013-10-08T09:37:09.060 に答える
1
すべての交点のインシデント エッジのリストを維持する必要があります。
次に、前の (入ってくる) エッジとの角度 (反時計回り) が最も小さいエッジ (出て行く) をポイントとして選択します。
于 2012-05-20T11:58:04.127 に答える
0
わかりました、私は実用的な解決策を作ったようです:
http://mrpyo.github.com/Polygon/
これは ActionScript なので、問題なく JavaScript に変換できます。誰かが興味を持っていれば、使用されているアルゴリズムを説明できます...
于 2012-05-22T13:16:18.033 に答える
0
Convex Hull アルゴリズムを調べたいと思われるようです。これは、いくつかの凸包アルゴリズムのアプレットです。アルゴリズムの 1 つを変更して極値を取得し、そこから移動できる場合があります。
于 2012-05-20T06:45:13.167 に答える