以下のアルゴリズムが、このリンクから特定のポリゴン内にポイントがあるかどうかを確認するために機能することを確認しました。
int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
int i, j, c = 0;
for (i = 0, j = nvert-1; i < nvert; j = i++) {
if ( ((verty[i]>testy) != (verty[j]>testy)) &&
(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
c = !c;
}
return c;
}
私はこのアルゴリズムを試しましたが、実際には完璧に機能します。でも残念ながら、少し時間をかけて考えてみたらよくわかりません。
ですから、誰かがこのアルゴリズムを理解できるなら、少し説明してください。
ありがとうございました。
アルゴリズムは右側にレイキャスティングしています。ループが繰り返されるたびに、テストポイントがポリゴンのエッジの1つに対してチェックされます。ポイントのy座標がエッジのスコープ内にある場合、ifテストの最初の行は成功します。2行目は、テストポイントが行の左側にあるかどうかを確認します（確認するための紙くずがないのではないかと思います）。それが本当なら、テストポイントから右に引かれた線はその端を横切ります。
の値を繰り返し反転することによりc、アルゴリズムは右方向の線がポリゴンと交差する回数をカウントします。奇数回交差する場合、ポイントは内側にあります。偶数の場合、ポイントは外側にあります。
ただし、a）浮動小数点演算の精度、およびb）水平エッジ、または頂点と同じy座標を持つテストポイントを持つことの影響について懸念があります。
編集1/30/2022：私は大学時代に9年前にこの答えを書きました。チャットの会話の人々は、それが正確ではないことを示しています。あなたはおそらく他の場所を見る必要があります。♂️</ p>
Chowlettは、あらゆる点で、形、形が正しいです。アルゴリズムは、ポイントがポリゴンの線上にある場合、それは外側にあると想定します。場合によっては、これは誤りです。2つの'>'演算子を'>='に変更し、'<'を'<='に変更すると、これが修正されます。
bool PointInPolygon(Point point, Polygon polygon) {
vector<Point> points = polygon.getPoints();
int i, j, nvert = points.size();
bool c = false;
for(i = 0, j = nvert - 1; i < nvert; j = i++) {
if( ( (points[i].y >= point.y ) != (points[j].y >= point.y) ) &&
(point.x <= (points[j].x - points[i].x) * (point.y - points[i].y) / (points[j].y - points[i].y) + points[i].x)
)
c = !c;
}
return c;
}
これは、実際のコードでレイトレーシングアルゴリズムを説明するために得られるのと同じくらい詳細である可能性があります。最適化されていない可能性がありますが、それは常にシステムを完全に把握した後で行う必要があります。
//method to check if a Coordinate is located in a polygon
public boolean checkIsInPolygon(ArrayList<Coordinate> poly){
//this method uses the ray tracing algorithm to determine if the point is in the polygon
int nPoints=poly.size();
int j=-999;
int i=-999;
boolean locatedInPolygon=false;
for(i=0;i<(nPoints);i++){
//repeat loop for all sets of points
if(i==(nPoints-1)){
//if i is the last vertex, let j be the first vertex
j= 0;
}else{
//for all-else, let j=(i+1)th vertex
j=i+1;
}
float vertY_i= (float)poly.get(i).getY();
float vertX_i= (float)poly.get(i).getX();
float vertY_j= (float)poly.get(j).getY();
float vertX_j= (float)poly.get(j).getX();
float testX = (float)this.getX();
float testY = (float)this.getY();
// following statement checks if testPoint.Y is below Y-coord of i-th vertex
boolean belowLowY=vertY_i>testY;
// following statement checks if testPoint.Y is below Y-coord of i+1-th vertex
boolean belowHighY=vertY_j>testY;
/* following statement is true if testPoint.Y satisfies either (only one is possible)
-->(i).Y < testPoint.Y < (i+1).Y OR
-->(i).Y > testPoint.Y > (i+1).Y
(Note)
Both of the conditions indicate that a point is located within the edges of the Y-th coordinate
of the (i)-th and the (i+1)- th vertices of the polygon. If neither of the above
conditions is satisfied, then it is assured that a semi-infinite horizontal line draw
to the right from the testpoint will NOT cross the line that connects vertices i and i+1
of the polygon
*/
boolean withinYsEdges= belowLowY != belowHighY;
if( withinYsEdges){
// this is the slope of the line that connects vertices i and i+1 of the polygon
float slopeOfLine = ( vertX_j-vertX_i )/ (vertY_j-vertY_i) ;
// this looks up the x-coord of a point lying on the above line, given its y-coord
float pointOnLine = ( slopeOfLine* (testY - vertY_i) )+vertX_i;
//checks to see if x-coord of testPoint is smaller than the point on the line with the same y-coord
boolean isLeftToLine= testX < pointOnLine;
if(isLeftToLine){
//this statement changes true to false (and vice-versa)
locatedInPolygon= !locatedInPolygon;
}//end if (isLeftToLine)
}//end if (withinYsEdges
}
return locatedInPolygon;
}
最適化について一言：最短（および/または最短）のコードが最速で実装されるというのは真実ではありません。配列から要素を読み取って格納し、必要になるたびに配列にアクセスするよりも、コードブロックの実行中に何度もそれを使用する方がはるかに高速なプロセスです。これは、アレイが非常に大きい場合に特に重要です。私の意見では、配列の各項を適切な名前の変数に格納することで、その目的を評価しやすくなり、はるかに読みやすいコードを形成することもできます。ちょうど私の2セント...
元のコードを少し読みやすくするために変更しました（これもEigenを使用しています）。アルゴリズムは同じです。
// This uses the ray-casting algorithm to decide whether the point is inside
// the given polygon. See https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm
bool pnpoly(const Eigen::MatrixX2d &poly, float x, float y)
{
// If we never cross any lines we're inside.
bool inside = false;
// Loop through all the edges.
for (int i = 0; i < poly.rows(); ++i)
{
// i is the index of the first vertex, j is the next one.
// The original code uses a too-clever trick for this.
int j = (i + 1) % poly.rows();
// The vertices of the edge we are checking.
double xp0 = poly(i, 0);
double yp0 = poly(i, 1);
double xp1 = poly(j, 0);
double yp1 = poly(j, 1);
// Check whether the edge intersects a line from (-inf,y) to (x,y).
// First check if the line crosses the horizontal line at y in either direction.
if ((yp0 <= y) && (yp1 > y) || (yp1 <= y) && (yp0 > y))
{
// If so, get the point where it crosses that line. This is a simple solution
// to a linear equation. Note that we can't get a division by zero here -
// if yp1 == yp0 then the above if be false.
double cross = (xp1 - xp0) * (y - yp0) / (yp1 - yp0) + xp0;
// Finally check if it crosses to the left of our test point. You could equally
// do right and it should give the same result.
if (cross < x)
inside = !inside;
}
}
return inside;
}
アルゴリズムは、最も必要な要素に分解されます。それが開発され、テストされた後、すべての不要なものが削除されました。結果として、あなたはそれを簡単に理解することはできませんが、それは仕事をし、そしてまた非常に良いパフォーマンスをします。
// not optimized yet (nvert could be left out)
public static function pnpoly(nvert: int, vertx: Array, verty: Array, x: Number, y: Number): Boolean
{
var i: int, j: int;
var c: Boolean = false;
for (i = 0, j = nvert - 1; i < nvert; j = i++)
{
if (((verty[i] > y) != (verty[j] > y)) && (x < (vertx[j] - vertx[i]) * (y - verty[i]) / (verty[j] - verty[i]) + vertx[i]))
c = !c;
}
return c;
}
このアルゴリズムは、ポリゴンの側面が交差しない限り、閉じたポリゴンで機能します。三角形、五角形、正方形、それ自体と交差しない非常に曲がりくねった区分的に線形の輪ゴムですら。
1）ポリゴンをベクトルの有向グループとして定義します。これは、ポリゴンのすべての辺が頂点anから頂点an+1に向かうベクトルによって記述されることを意味します。ベクトルは、最後のベクトルが最初のベクトルの尾に接触するまで、1つの頭が次の尾に接触するように方向付けられます。
2）ポリゴンの内側または外側でテストするポイントを選択します。
3）ポリゴンの周囲に沿った各ベクトルVnについて、テストポイントで開始し、Vnのテールで終了するベクトルDnを見つけます。DnXVn / DN * VNとして定義されたベクトルCnを計算します（Xは外積を示し、*は内積を示します）。Cnの大きさをMnという名前で呼びます。
4）すべてのMnを加算し、この量をKと呼びます。
5）Kがゼロの場合、ポイントはポリゴンの外側にあります。
6）Kがゼロでない場合、ポイントはポリゴンの内側にあります。
理論的には、ポリゴンのエッジ上にあるポイントは未定義の結果を生成します。
Kの幾何学的な意味は、テストポイントに座っているノミが、ポリゴンの端を歩いているアリが左に歩いている角度から右に歩いている角度を引いたものを「見た」合計角度です。閉回路では、アリはそれが始まった場所で終わります。ポリゴンの外側では、場所に関係なく、答えはゼロです。
ポリゴンの内側では、場所に関係なく、答えは「ポイントの周りに1回」です。
このメソッドは、ポイント（testx、testy）からO（0,0）への光線がポリゴンの側面をカットするかどうかをチェックします。
ここにはよく知られている結論があります。1つのポイントからの光線がポリゴンの側面を奇数時間カットした場合、そのポイントはポリゴンに属します。そうでない場合、そのポイントはポリゴンの外側になります。
2番目の行がポイントが行の左側にあるかどうかをチェックする@chowletteの答えを拡張するために、派生は与えられていませんが、これは私が解決したものです：最初に2つの基本的なケースを想像するのに役立ちます：
. /または/ .私たちのポイントが光線を水平方向に発射する場合、それは線分に当たるでしょう。私たちのポイントはそれの左にありますか、それとも右にありますか？内側か外側か？定義上、点と同じであるため、y座標がわかります。x座標は何になりますか？
あなたの伝統的な線の公式を取りなさいy = mx + b。mは実行中の上昇です。ここでは、代わりに、ポイントと同じ高さ（y）を持つラインセグメント上のポイントのx座標を見つけようとしています。
したがって、xについて解きますx = (y - b)/m。mはランオーバーランになるので、これはランオーバーライズになるか、(yj - yi)/(xj - xi)になり(xj - xi)/(yj - yi)ます。bは原点からのオフセットです。yi座標系のベースとして仮定すると、bはyiになります。私たちのポイントtestyは入力です。減算yiすると、数式全体がからのオフセットになりyiます。
現在、(xj - xi)/(yj - yi)または1/m回yまたは(testy - yi)：(xj - xi)(testy - yi)/(yj - yi)がありますが、testxはに基づいていないyiため、2つ（またはゼロtestxも）を比較するために追加し直します。
基本的な考え方は、ポリゴンのエッジごとに1つずつ、ポイントからベクトルを計算することだと思います。ベクトルが1つのエッジと交差する場合、ポイントはポリゴン内にあります。凹多角形によって、奇数のエッジと交差する場合は、内側にもあります（免責事項：すべての凹多角形で機能するかどうかはわかりませんが）。
これは私が使用しているアルゴリズムですが、速度を上げるために少し前処理のトリックを追加しました。私のポリゴンには最大1000のエッジがあり、それらは変更されませんが、マウスを動かすたびにカーソルがポリゴンの内側にあるかどうかを調べる必要があります。
基本的に、外接する長方形の高さを等しい長さの間隔に分割し、これらの間隔ごとに、その中にある/交差するエッジのリストをコンパイルします。
ポイントを検索する必要がある場合、O（1）時間で、どのインターバルにあるかを計算できます。その後、インターバルのリストにあるエッジのみをテストする必要があります。
256の間隔を使用しましたが、これにより、テストする必要のあるエッジの数が1000ではなく2〜10に減りました。
これのphp実装は次のとおりです。
<?php
class Point2D {
public $x;
public $y;
function __construct($x, $y) {
$this->x = $x;
$this->y = $y;
}
function x() {
return $this->x;
}
function y() {
return $this->y;
}
}
class Point {
protected $vertices;
function __construct($vertices) {
$this->vertices = $vertices;
}
//Determines if the specified point is within the polygon.
function pointInPolygon($point) {
/* @var $point Point2D */
$poly_vertices = $this->vertices;
$num_of_vertices = count($poly_vertices);
$edge_error = 1.192092896e-07;
$r = false;
for ($i = 0, $j = $num_of_vertices - 1; $i < $num_of_vertices; $j = $i++) {
/* @var $current_vertex_i Point2D */
/* @var $current_vertex_j Point2D */
$current_vertex_i = $poly_vertices[$i];
$current_vertex_j = $poly_vertices[$j];
if (abs($current_vertex_i->y - $current_vertex_j->y) <= $edge_error && abs($current_vertex_j->y - $point->y) <= $edge_error && ($current_vertex_i->x >= $point->x) != ($current_vertex_j->x >= $point->x)) {
return true;
}
if ($current_vertex_i->y > $point->y != $current_vertex_j->y > $point->y) {
$c = ($current_vertex_j->x - $current_vertex_i->x) * ($point->y - $current_vertex_i->y) / ($current_vertex_j->y - $current_vertex_i->y) + $current_vertex_i->x;
if (abs($point->x - $c) <= $edge_error) {
return true;
}
if ($point->x < $c) {
$r = !$r;
}
}
}
return $r;
}
テスト走行：
<?php
$vertices = array();
array_push($vertices, new Point2D(120, 40));
array_push($vertices, new Point2D(260, 40));
array_push($vertices, new Point2D(45, 170));
array_push($vertices, new Point2D(335, 170));
array_push($vertices, new Point2D(120, 300));
array_push($vertices, new Point2D(260, 300));
$Point = new Point($vertices);
$point_to_find = new Point2D(190, 170);
$isPointInPolygon = $Point->pointInPolygon($point_to_find);
echo $isPointInPolygon;
var_dump($isPointInPolygon);
コードを変更して、ポイントがエッジ上にあることを含め、ポイントがポリゴン内にあるかどうかを確認しました。
bool point_in_polygon_check_edge(const vec<double, 2>& v, vec<double, 2> polygon[], int point_count, double edge_error = 1.192092896e-07f)
{
const static int x = 0;
const static int y = 1;
int i, j;
bool r = false;
for (i = 0, j = point_count - 1; i < point_count; j = i++)
{
const vec<double, 2>& pi = polygon[i);
const vec<double, 2>& pj = polygon[j];
if (fabs(pi[y] - pj[y]) <= edge_error && fabs(pj[y] - v[y]) <= edge_error && (pi[x] >= v[x]) != (pj[x] >= v[x]))
{
return true;
}
if ((pi[y] > v[y]) != (pj[y] > v[y]))
{
double c = (pj[x] - pi[x]) * (v[y] - pi[y]) / (pj[y] - pi[y]) + pi[x];
if (fabs(v[x] - c) <= edge_error)
{
return true;
}
if (v[x] < c)
{
r = !r;
}
}
}
return r;
}