ポリゴンを決定し、ポイントがポリゴンの内側にあるか外側にあるかをチェックするアルゴリズムを実装したいと思います。
同様のアルゴリズムで利用可能な例があるかどうかは誰にもわかりませんか?
72500 次
16 に答える
41
C# コード
bool IsPointInPolygon(List<Loc> poly, Loc point)
{
int i, j;
bool c = false;
for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
{
if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt))
|| ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt)))
&& (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt)
/ (poly[j].Lt - poly[i].Lt) + poly[i].Lg))
{
c = !c;
}
}
return c;
}
ロケーションクラス
public class Loc
{
private double lt;
private double lg;
public double Lg
{
get { return lg; }
set { lg = value; }
}
public double Lt
{
get { return lt; }
set { lt = value; }
}
public Loc(double lt, double lg)
{
this.lt = lt;
this.lg = lg;
}
}
于 2011-10-12T11:24:34.973 に答える
15
Web を検索してさまざまな実装を試し、それらを C++ から C# に移植した後、最終的にコードをまっすぐにしました。
public static bool PointInPolygon(LatLong p, List<LatLong> poly)
{
int n = poly.Count();
poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon });
LatLong[] v = poly.ToArray();
int wn = 0; // the winding number counter
// loop through all edges of the polygon
for (int i = 0; i < n; i++)
{ // edge from V[i] to V[i+1]
if (v[i].Lat <= p.Lat)
{ // start y <= P.y
if (v[i + 1].Lat > p.Lat) // an upward crossing
if (isLeft(v[i], v[i + 1], p) > 0) // P left of edge
++wn; // have a valid up intersect
}
else
{ // start y > P.y (no test needed)
if (v[i + 1].Lat <= p.Lat) // a downward crossing
if (isLeft(v[i], v[i + 1], p) < 0) // P right of edge
--wn; // have a valid down intersect
}
}
if (wn != 0)
return true;
else
return false;
}
private static int isLeft(LatLong P0, LatLong P1, LatLong P2)
{
double calc = ((P1.Lon - P0.Lon) * (P2.Lat - P0.Lat)
- (P2.Lon - P0.Lon) * (P1.Lat - P0.Lat));
if (calc > 0)
return 1;
else if (calc < 0)
return -1;
else
return 0;
}
isLeft 関数で丸めの問題が発生し、間違った変換を行っていることに気付かずに何時間も費やしたので、その関数の最後の if ブロックの不備を許してください。
ところで、これは元のコードと記事です: http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
于 2010-09-03T15:42:45.083 に答える
5
最高の説明と実装は、 Point In Polygon Winding Number Inclusionで見つけることができます。
よく説明された記事の最後には、C++ の実装もあります。このサイトには、他のジオメトリ ベースの問題に対するいくつかの優れたアルゴリズム/ソリューションも含まれています。
C++ 実装を変更して使用し、C# 実装も作成しました。Winding Number アルゴリズムはエッジ クロッシング アルゴリズムよりも正確であり、非常に高速であるため、絶対に使用する必要があります。
于 2009-05-29T03:39:02.767 に答える
5
もっとシンプルで効率的な解決策があると思います。
C++ のコードは次のとおりです。それをC#に変換するのは簡単なはずです。
int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++) {
if ((((yp[i] <= y) && (y < yp[j])) ||
((yp[j] <= y) && (y < yp[i]))) &&
(x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
c = !c;
}
return c;
}
于 2011-07-22T06:12:25.437 に答える
2
asp.Net C＃の完全なソリューション、ここで完全な詳細を確認できます。緯度と経度を使用して、ポリゴンの内側または外側にあるポイント（lat、lon）を見つける方法を確認できますか？ 記事参照リンク
private static bool checkPointExistsInGeofencePolygon（string latlnglist、string lat、string lng）{
List<Loc> objList = new List<Loc>();
// sample string should be like this strlatlng = "39.11495,-76.873259|39.114588,-76.872808|39.112921,-76.870373|";
string[] arr = latlnglist.Split('|');
for (int i = 0; i <= arr.Length - 1; i++)
{
string latlng = arr[i];
string[] arrlatlng = latlng.Split(',');
Loc er = new Loc(Convert.ToDouble(arrlatlng[0]), Convert.ToDouble(arrlatlng[1]));
objList.Add(er);
}
Loc pt = new Loc(Convert.ToDouble(lat), Convert.ToDouble(lng));
if (IsPointInPolygon(objList, pt) == true)
{
return true;
}
else
{
return false;
}
}
private static bool IsPointInPolygon(List<Loc> poly, Loc point)
{
int i, j;
bool c = false;
for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
{
if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) |
((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) &&
(point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) / (poly[j].Lt - poly[i].Lt) + poly[i].Lg))
c = !c;
}
return c;
}
于 2012-12-21T07:31:24.647 に答える
1
私は地球の南に住んでいる人々を助けるために1つの詳細を追加します!! ブラジルにいる場合 (私の場合)、GPS 座標はすべてマイナスです。そして、これらすべてのアルゴリズムは間違った結果をもたらします。
すべてのポイントの緯度と経度の絶対値を使用するのが最も簡単な方法です。その場合、ヤン・コベルスキーのアルゴリズムは完璧です。
于 2017-06-08T02:46:54.713 に答える
0
単純な多角形 (線が交差していない) があり、穴がない場合は、多角形を三角形分割することもできます。これはおそらく GIS アプリで TIN を描画するために行い、それぞれの点をテストします。三角形。ポリゴンのエッジ数が少なく、ポイント数が多い場合、これは高速です。
三角形の興味深い点については、リンク テキストを参照してください
それ以外の場合は、間違いなくエッジ クロッシングではなくワインディング ルールを使用します。エッジ クロッシングには、エッジ上のポイントに関する実際の問題があります。これは、精度が制限された GPS からデータが生成される場合に発生する可能性が非常に高いものです。
于 2009-05-29T04:01:47.527 に答える
0
ポイントがポリゴンの内側にあるかどうかを確認します -
頂点 a1、a2、a3、a4、a5 を持つ多角形を考えます。次の一連の手順は、点 P がポリゴンの内側にあるか外側にあるかを確認するのに役立ちます。
エッジ a1->a2 によって形成される三角形のベクトル面積と、a2 を P に、P を a1 に接続するベクトルを計算します。同様に、多角形の辺として 1 つの辺を持ち、P をその辺に接続する他の 2 つの辺を持つ可能性のある三角形のそれぞれのベクトル領域を計算します。
ポイントがポリゴンの内側にあるためには、各三角形に正の面積が必要です。三角形の 1 つが負の面積を持っていても、点 P は多角形から際立っています。
3 つのエッジを表すベクトルを指定して三角形の面積を計算するには、http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm を参照してください。
于 2009-05-29T02:51:50.643 に答える
0
多角形が凸状の場合、問題はより簡単になります。その場合、各線に対して簡単なテストを実行して、点がその線の内側にあるか外側にあるかを確認できます (両方向に無限に伸びています)。それ以外の場合、凹面多角形の場合は、点から無限遠 (任意の方向) に想像上の光線を描画します。境界線を越えた回数を数えます。奇数はポイントが内側にあることを意味し、偶数はポイントが外側にあることを意味します。
この最後のアルゴリズムは、見た目よりもトリッキーです。架空の光線がポリゴンの頂点の 1 つに正確に当たったときに何が起こるかについて、非常に注意する必要があります。
仮想光線が -x 方向に進む場合、y 座標が厳密に点の y 座標よりも小さい点を少なくとも 1 つ含む行のみをカウントするように選択できます。これは、ほとんどの奇妙なエッジ ケースを正しく機能させる方法です。
于 2009-05-29T02:53:20.220 に答える
0
C# メソッドを Php に翻訳し、コードを理解するために多くのコメントを追加しました。
PolygonHelps の説明:
ポイントがポリゴンの内側にあるか外側にあるかを確認します。この手順は GPS 座標を使用し、ポリゴンの地理的領域が小さい場合に機能します。
入力:
$poly: Point の配列: ポリゴン頂点リスト; [{点}, {点}, ...];
$point: チェックするポイント。ポイント: {"lat" => "x.xxx", "lng" => "y.yyy"}
$c が false の場合、ポリゴンとの交点の数は偶数であるため、ポイントはポリゴンの外側にあります。
$c が true の場合、ポリゴンとの交点の数が奇数であるため、ポイントはポリゴンの内側にあります。
$n はポリゴンの頂点の数です。
メソッドは、ポリゴンの各頂点に対して、現在の頂点と前の頂点を通る線を計算し、2 つの線に交点があるかどうかを確認します。
$c は交点が存在する場合に変化します。
したがって、ポイントがポリゴンの内側にある場合、メソッドは true を返すことができ、そうでない場合は false を返します。
class PolygonHelps {
public static function isPointInPolygon(&$poly, $point){
$c = false;
$n = $j = count($poly);
for ($i = 0, $j = $n - 1; $i < $n; $j = $i++){
if ( ( ( ( $poly[$i]->lat <= $point->lat ) && ( $point->lat < $poly[$j]->lat ) )
|| ( ( $poly[$j]->lat <= $point->lat ) && ( $point->lat < $poly[$i]->lat ) ) )
&& ( $point->lng < ( $poly[$j]->lng - $poly[$i]->lng )
* ( $point->lat - $poly[$i]->lat )
/ ( $poly[$j]->lat - $poly[$i]->lat )
+ $poly[$i]->lng ) ){
$c = !$c;
}
}
return $c;
}
}
于 2017-01-09T17:03:17.427 に答える
0
多角形は、点のペア A、B、C .... の連続したリストとして定義されます。
決定ボックス Xmin、Xmax、Ymin、Ymax
ケース 1 テスト ポイント P がボックスの外側にある
ケース 2 テスト ポイント P はボックス内にあります。
ボックス {[Xmin,Ymin] - [Xmax, Ymax]} の「直径」D を決定します (D が側面にあるとの混乱を避けるために少し余分に追加します)。
すべての辺の勾配 M を決定する
すべての勾配 M と最も異なる勾配 Mt を見つける
テスト ラインは、勾配 Mt の P から距離 D 離れています。
交差点の数をゼロに設定する
サイド AB、BC のそれぞれについて、PD とサイドの開始点から終了点までの交点をテストします。必要に応じて、交差点の数を増やします。P から交点までの距離が 0 であることは、P が片側にあることを示していることに注意してください。
奇数カウントは、P が多角形の内側にあることを示します
于 2013-10-07T16:35:02.043 に答える