web-gelistirme-sc.com

Poligon Algoritmasında Nokta

Aşağıdaki algoritmanın bir noktanın belirli bir poligonda olup olmadığını kontrol etmek için işe yaradığını gördüm link :

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;
}

Bu algoritmayı denedim ve aslında mükemmel çalışıyor. Ama ne yazık ki, bir fikir edinmek için biraz zaman harcadıktan sonra iyi anlayamıyorum. 

Eğer birisi bu algoritmayı anlayabiliyorsa, lütfen bana biraz açıkla. 

Teşekkür ederim.

54
Allan Jiang

Algoritma sağa ışın dökümü yapıyor. Her döngünün tekrarı, test noktası poligonun kenarlarından birine karşı kontrol edilir. İf testinin ilk satırı, noktanın y koordinatı Edge'in kapsamı içindeyse başarılı olur. İkinci satır, test noktasının satırın solunda olup olmadığını kontrol eder (sanırım - kontrol etmek için elimde hurda kağıdım yok). Bu doğruysa, test noktasından doğru çizilen çizgi o Kenardan geçiyor.

c'nin değerini art arda tersine çevirerek algoritma, sağ çizginin poligonu kaç kez geçtiğini sayar. Tek sayıda geçerse, nokta içeridedir; eğer bir çift sayı varsa, nokta dışarıdadır.

A) kayan nokta aritmetiğinin doğruluğu ve b) yatay bir kenara sahip olmanın ya da tepe noktasıyla aynı y koordinatına sahip bir test noktasının olmasının etkileri ile ilgili endişelerim olurdu.

45
Chowlett

Chowlett her yönden, biçimde ve formda doğrudur .. • Algoritma, noktanızın çokgen çizgisinde olması durumunda dışarıda olduğunu varsayar - bazı durumlarda, bunun yanlış olduğunu varsayar. İki '>' işlecini '> =' olarak değiştirmek ve '<' '' <= 'olarak değiştirmek bunu düzeltecektir.

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;
}
19
Josh

Bu, ışın izleme algoritmasını gerçek kodda açıklamak için alabileceği kadar ayrıntılı olabilir. En iyi duruma getirilmemiş olabilir, ancak bu her zaman sistemi tam olarak kavradıktan sonra gelmelidir.

    //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;
}

Optimizasyon hakkında sadece bir kelime: En kısa (ve/veya en kısa) kodun en hızlı uygulanan kod olduğu doğru değildir. Dizideki bir öğeyi okumak ve depolamak ve onu (muhtemelen) kod bloğunun yürütülmesi sırasında birçok kez kullanmak, diziye her gerektiğinde erişmek yerine kullanmaktan daha hızlı bir işlemdir. Dizi özellikle çok büyükse bu özellikle önemlidir. Bence, bir dizinin her bir terimini iyi adlandırılmış bir değişkende saklayarak, amacını değerlendirmek ve böylece daha okunaklı bir kod oluşturmak daha kolaydır. Sadece iki sentim...

6
apil.tamang

Algoritma en gerekli elemana kadar çıkarılmıştır. Geliştirilip test edildikten sonra, tüm gereksiz şeyler çıkarıldı. Sonuç olarak kolayca anlayamazsınız ama işi yapıyor ve aynı zamanda çok iyi bir performans sergiliyor.


ActionScript-3 : 'a çevirme özgürlüğünü kullandım.

// 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;
}
3
Bitterblue

Bu algoritma, poligonun kenarları geçmediği sürece herhangi bir kapalı poligonda çalışır. Üçgen, beşgen, kare, hatta kendi kendini geçmeyen çok kıvrımlı parçalara doğrusal lastik bant. 

1) Çokgeninizi, yönlendirilmiş bir vektörler grubu olarak tanımlayın. Bununla, poligonun her bir tarafının, tepe noktasından an köşesine ve + 1'e giden bir vektör ile tanımlanması kastedilmektedir. Vektörler öyle yönlendirilir ki, birinin kafası son vektör birincinin kuyruğuna değene kadar bir sonraki kuyruğa dokunur. 

2) Çokgenin içinde veya dışında test edilecek noktayı seçin. 

3) Çokgenin çevresi boyunca her bir Vn vektörü için, test noktasında başlayan ve Vn'nin kuyruğunda biten Dn vektörünü bulun. DnXVn/DN * VN olarak tanımlanan Cn vektörünü hesaplayın (X, çapraz ürünü gösterir; * nokta ürününü gösterir). Cn'nin büyüklüğünü Mn ismi ile çağırın. 

4) Tüm Mn'yi ekleyin ve bu miktarı K olarak adlandırın. 

5) K sıfırsa, nokta çokgenin dışındadır. 

6) K sıfır değilse, nokta çokgenin içindedir.

Teorik olarak, çokgenin kenarında yatan bir nokta tanımsız bir sonuç verecektir.

K'nin geometrik anlamı, test noktamızda oturan pire, poligonun Kenarında yürüyen karıncayı sola doğru eksi açı sağa doğru yürüdükçe "görmüş" toplam açıdır. Kapalı bir devrede, karınca başladığı yerde biter .. Poligonun dışında, konumundan bağımsız olarak cevap sıfırdır.
Poligonun içinde, bulunduğu yere bakmaksızın, cevabı "nokta etrafında bir kez" dir.


3
Mario

Bu yöntem, ışının noktadan (testx, testy) ila O (0,0) arasında çokgenin kenarlarını kesip kesmediğini kontrol eder.

Bilinen bir sonuç var burada : 1 noktadan bir ışın ve bir çokgenin kenarlarını tuhaf bir süre boyunca keserse, o nokta çokgene ait olacak, aksi halde o nokta çokgenin dışında olacak. 

2
Thinhbk

Bence temel fikir, vektörleri noktadan, poligonun Kenar başına birinden hesaplamak. Vektör bir Kenardan geçerse, nokta çokgenin içindedir. İçbükey çokgenler çok sayıda kenarı geçerse de içlerindedir (feragatname: tüm içbükey çokgenler için çalışıp çalışmadığından emin olmasa da).

1
Anders

Orijinal kodu biraz daha okunabilir hale getirmek için değiştirdim (bu Eigen'i de kullanıyor). Algoritma aynıdır.

// 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;
}
1
Timmmm

İşte bunun bir php uygulaması:

<?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;
}

Test sü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);
1
Daniel

@ Chowlette's answer 'da genişletmek için, ikinci satır, noktanın satırın solunda olup olmadığını kontrol eder, Türetme verilmez, ancak çalıştığım şudur: İlk önce 2 temel durumu hayal etmeye yardımcı olur:

  • nokta, satırın solunda . / veya
  • nokta, satırın sağında / .

Amacımız yatay olarak bir ışın çekmek olsaydı, çizgi parçasını nereye vuracaktı. Bizim amacımız bunun soluna mı yoksa sağına mı? İçeride mi yoksa dışarıda mı? Onun y koordinatını biliyoruz, çünkü tanım gereği nokta ile aynı. X koordinatı ne olurdu?

Geleneksel çizgi formülünüzü alın y = mx + b. m koşuya yükselmedir. Burada, o noktadaki (y) ile aynı yüksekliğe (y) sahip olan noktanın x koordinatını bulmaya çalışıyoruz .

Bu yüzden x: x = (y - b)/m için çözüyoruz. m, koşu boyunca yükseliyor, bu yüzden bu artış yükseliyor veya (yj - yi)/(xj - xi), (xj - xi)/(yj - yi) olur. b Menşe'den uzaklıktır. Koordinat sistemimizin temelini yi olarak kabul edersek, b yi olur. Bizim noktamız testy bizim girişimizdir, yi 'in çıkarılması tüm formülü yi den bir ofset haline getirir.

Şimdi (xj - xi)/(yj - yi) ya da 1/m çarpı y ya da (testy - yi): (xj - xi)(testy - yi)/(yj - yi) var ama testx yi 'a dayanmıyor, bu yüzden karşılaştırmak için geri ekledik iki (veya sıfır testx)

1
derduher

Kullandığım algoritma bu, ancak hızlandırmak için biraz ön işleme kandırması ekledim. Çokgenlerimin ~ 1000 kenarları var ve değişmiyorlar, ancak imlecin her fare hareketinde bir tane içinde olup olmadığına bakmalıyım. 

Temelde sınırlayıcı dikdörtgenin yüksekliğini eşit uzunluk aralıklarına bölerim ve bu aralıkların her biri için onunla kesişen/kesişen kenarların listesini derlerim. 

Bir noktaya ihtiyaç duyduğumda, içinde O(1) zaman - içinde hangi aralığı olduğunu hesaplayabilirim ve sonra yalnızca aralık listesinde olan bu kenarları test etmem gerekir.

256 aralık kullandım ve test etmek için gereken kenar sayısını ~ 1000 yerine 2-10'a düşürdüm.

0
Sly1024

Noktayı bir Kenarda da dahil olmak üzere noktanın çokgenin içinde olup olmadığını kontrol etmek için kodu değiştirdim. 

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;
}
0
rawdev