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

Ответ 1

Алгоритм - луч-литье вправо. Каждая итерация цикла, контрольная точка проверяется на одном из краев многоугольника. Первая строка if-теста завершается успешно, если точка-координата точки находится в пределах области границы. Вторая строка проверяет, находится ли контрольная точка слева от строки (я думаю - у меня нет бумаги для лома, чтобы проверить ее). Если это так, линия, направленная вправо от контрольной точки, пересекает этот край.

Повторно инвертируя значение c, алгоритм подсчитывает, сколько раз линия справа пересекает многоугольник. Если он пересекает нечетное число раз, то точка внутри; если четное число, точка вне.

У меня были бы проблемы с: а) точностью арифметики с плавающей запятой и б) последствиями наличия горизонтального ребра или контрольной точки с той же y-координатой, что и вершина.

Ответ 2

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

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

Ответ 3

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

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

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

Ответ 4

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

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

Ответ 5

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

1) Определите свой полигон как направленную группу векторов. Под этим подразумевается, что каждая сторона многоугольника описывается вектором, который идет от вершины а до вершины а + 1. Векторы так направлены так, что голова одного касается хвоста следующего, пока последний вектор не коснется хвоста первого.

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

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

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

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

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

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

Ответ 6

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

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

Ответ 7

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

Ответ 8

Здесь выполняется 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);

Ответ 9

Развернуть на @chowlette answer, где вторая строка проверяет, находится ли точка слева от строки, Никакого вывода не приводится, но это то, что я разработал: Сначала это позволяет представить два основных случая:

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

Если бы наш смысл был стрелять лучами по горизонтали, где бы он ударил по сегменту линии. Направляется ли наша точка налево или на право? Внутри или снаружи? Мы знаем его координату 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, а также )

Ответ 10

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

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

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

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

Ответ 11

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

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

Ответ 12

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