Точка в полигональном алгоритме

Chowlett является правильным во всех отношениях, форме и форме. Алгоритм предполагает, что если ваша точка находится на линии полигона, то она находится снаружи - в некоторых случаях это ложь. Изменение двух операторов ' > ' на '> = 'и изменение'

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

только одно слово об оптимизации: неверно, что самый короткий (и/или самый короткий) код является самым быстрым реализованным. Это гораздо более быстрый процесс для чтения и хранения элемента из массива и использовать его (возможно) много раз в рамках выполнения блока кода, чем для доступа к массиву каждый раз требуется. Это особенно важно, если массив очень большой. На мой взгляд, сохраняя каждый член массива в хорошо названной переменной, также легче оценить его назначение и, таким образом, сформировать гораздо более читаемый код. Только мои два цента...

алгоритм разделен до самых необходимых элементов. После того, как он был разработан и протестирован все ненужное было удалено. В результате вы не можете undertand его легко, но он делает свою работу, а также в очень хорошей производительности.

---

Я взял на себя смелость перевести его на ActionScript-3:

// 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. Векторы направлены так, что голова одного соприкасается с хвостом другого до последнего вектор касается хвоста первого.

2) Выберите точку для тестирования внутри или снаружи полигона.

3) для каждого вектора Vn по периметру полигона находим вектор Dn, который начинается в контрольной точке и заканчивается в хвосте Vn. Вычислите вектор Cn, определенный как DnXVn / DN*VN (X обозначает перекрестное произведение; * обозначает точечное произведение). Назовем величину Cn именем Mn.

4) Добавьте все Mn и назовите это количество K.

5) Если K ноль, точка находится вне полигона.

6) Если K не равно нулю, то точка находится внутри многоугольника.

теоретически точка, лежащая на краю многоугольника, даст неопределенный результат.

геометрическое значение K-это общий угол, который блоха, сидящая на нашей тестовой точке, "увидела" муравья, идущего по краю многоугольника, идущего влево минус угол, идущий вправо. В замкнутом контуре муравей заканчивается там, где он начался. За пределами полигон, независимо от местоположения, ответ равен нулю.
Внутри полигона, независимо от местоположения, ответ "один раз вокруг точки".

---

этот метод проверяет, отрезает ли луч от точки (testx, testy) до O (0,0) стороны многоугольника или нет .

есть известный вывод здесь: если луч от 1 точки и вырезать стороны полигона в течение нечетного времени, эта точка будет принадлежать полигону, в противном случае эта точка будет вне полигона.

Я думаю, что основная идея заключается в вычислении векторов из точки, по одному на ребро многоугольника. Если вектор пересекает одно ребро, то точка находится внутри полигона. По вогнутым полигонам, если он пересекает нечетное число ребер, он также находится внутри (отказ от ответственности: хотя и не уверен, что он работает для всех вогнутых полигонов).

чтобы расширить на @chowlete's ответ где вторая строка проверяет, находится ли точка слева от линии, Никакого вывода не дается, но это то, что я разработал: Во-первых это помогает представить 2 основных случаях:

• точка находится слева от линии . / или
• точка находится справа от линии / .

если бы наша точка должна была стрелять лучом горизонтально, где бы он ударил отрезок линии. Это наша точка слева или справа от него? Внутри или снаружи? Мы знаем его координату y, потому что она по определению совпадает с точкой. Какой будет координата x?

возьмите свою традиционную формулу линии y = mx + b. m-это подъем над пробегом. Здесь вместо этого мы пытаемся найти X координата точки На этом отрезке линии, которая имеет ту же высоту (y), что и наша точка.

поэтому мы решаем для 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 поэтому мы добавляем его обратно, чтобы сравнить два (или нулевой testx)

вот 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);

Это алгоритм, который я использую, но я добавил немного предварительной обработки обмана, чтобы ускорить его. Мои полигоны имеют ~1000 ребер, и они не меняются, но мне нужно посмотреть, находится ли курсор внутри одного при каждом движении мыши.

Я в основном разделяю высоту ограничивающего прямоугольника на равные интервалы длины, и для каждого из этих интервалов я составляю список ребер, которые лежат внутри/пересекаются с ним.

когда мне нужно найти точку, я могу вычислить-в O(1) время - какой интервал он находится, а затем мне нужно только проверить те ребра, которые находятся в списке интервала.

Я использовал 256 интервалов, и это уменьшило количество ребер, которые мне нужно проверить, до 2-10 вместо ~1000.

Я изменил код, чтобы проверить, находится ли точка в полигоне, включая точку на краю.

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

Я изменил исходный код чтобы сделать его немного более читаемым (также это использует 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;
}