Как я могу определить, находится ли 2D точка внутри многоугольника?

Question

Я пытаюсь создать быструю 2D точку внутри алгоритма многоугольника для использования при тестировании попаданий (например, Polygon.contains(p:Point)). Буду признателен за эффективные методы.

Answer 1

Ответ Дэвида Сегонда в значительной степени является стандартным общим ответом, а Ричард Т - наиболее распространенная оптимизация, хотя есть и другие. Другие сильные оптимизации основаны на менее общих решениях. Например, если вы собираетесь проверять один и тот же многоугольник с множеством точек, триангуляция многоугольника может значительно ускорить процесс, поскольку существует ряд очень быстрых алгоритмов поиска TIN. Другой вариант: если многоугольник и точки находятся на ограниченной плоскости при низком разрешении, например, на экране, вы можете нарисовать многоугольник в отображаемом буфере памяти с заданным цветом и проверить цвет данного пикселя, чтобы увидеть, лежит ли он в многоугольниках.

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

Работая в этой области, я обнаружил, что вычислительная геометрия Джозефа О'Руркса в C 'ISBN 0-521-44034-3 очень помогает.

Answer 2

Obj-C версия ответа nirg с примером метода для тестирования точек. Ответ Нирга хорошо сработал для меня.

- (BOOL)isPointInPolygon:(NSArray *)vertices point:(CGPoint)test {
    NSUInteger nvert = [vertices count];
    NSInteger i, j, c = 0;
    CGPoint verti, vertj;

    for (i = 0, j = nvert-1; i < nvert; j = i++) {
        verti = [(NSValue *)[vertices objectAtIndex:i] CGPointValue];
        vertj = [(NSValue *)[vertices objectAtIndex:j] CGPointValue];
        if (( (verti.y > test.y) != (vertj.y > test.y) ) &&
        ( test.x < ( vertj.x - verti.x ) * ( test.y - verti.y ) / ( vertj.y - verti.y ) + verti.x) )
            c = !c;
    }

    return (c ? YES : NO);
}

- (void)testPoint {

    NSArray *polygonVertices = [NSArray arrayWithObjects:
        [NSValue valueWithCGPoint:CGPointMake(13.5, 41.5)],
        [NSValue valueWithCGPoint:CGPointMake(42.5, 56.5)],
        [NSValue valueWithCGPoint:CGPointMake(39.5, 69.5)],
        [NSValue valueWithCGPoint:CGPointMake(42.5, 84.5)],
        [NSValue valueWithCGPoint:CGPointMake(13.5, 100.0)],
        [NSValue valueWithCGPoint:CGPointMake(6.0, 70.5)],
        nil
    ];

    CGPoint tappedPoint = CGPointMake(23.0, 70.0);

    if ([self isPointInPolygon:polygonVertices point:tappedPoint]) {
        NSLog(@"YES");
    } else {
        NSLog(@"NO");
    }
}

Answer 3

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

На этом сайте есть хорошая диаграмма, показывающая именно это, и хорошее объяснение по тестированию: Гамасутра - столкновение с Новым годом: обнаружение столкновений

Answer 4

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

- (BOOL)shape:(NSBezierPath *)path containsPoint:(NSPoint)point
{
    NSBezierPath *currentPath = [path bezierPathByFlatteningPath];
    BOOL result;
    float aggregateX = 0; //I use these to calculate the centroid of the shape
    float aggregateY = 0;
    NSPoint firstPoint[1];
    [currentPath elementAtIndex:0 associatedPoints:firstPoint];
    float olderX = firstPoint[0].x;
    float olderY = firstPoint[0].y;
    NSPoint interPoint;
    int noOfIntersections = 0;

    for (int n = 0; n < [currentPath elementCount]; n++) {
        NSPoint points[1];
        [currentPath elementAtIndex:n associatedPoints:points];
        aggregateX += points[0].x;
        aggregateY += points[0].y;
    }

    for (int n = 0; n < [currentPath elementCount]; n++) {
        NSPoint points[1];

        [currentPath elementAtIndex:n associatedPoints:points];
        //line equations in Ax + By = C form
        float _A_FOO = (aggregateY/[currentPath elementCount]) - point.y;  
        float _B_FOO = point.x - (aggregateX/[currentPath elementCount]);
        float _C_FOO = (_A_FOO * point.x) + (_B_FOO * point.y);

        float _A_BAR = olderY - points[0].y;
        float _B_BAR = points[0].x - olderX;
        float _C_BAR = (_A_BAR * olderX) + (_B_BAR * olderY);

        float det = (_A_FOO * _B_BAR) - (_A_BAR * _B_FOO);
        if (det != 0) {
            //intersection points with the edges
            float xIntersectionPoint = ((_B_BAR * _C_FOO) - (_B_FOO * _C_BAR)) / det;
            float yIntersectionPoint = ((_A_FOO * _C_BAR) - (_A_BAR * _C_FOO)) / det;
            interPoint = NSMakePoint(xIntersectionPoint, yIntersectionPoint);
            if (olderX <= points[0].x) {
                //doesn't matter in which direction the ray goes, so I send it right-ward.
                if ((interPoint.x >= olderX && interPoint.x <= points[0].x) && (interPoint.x > point.x)) {  
                    noOfIntersections++;
                }
            } else {
                if ((interPoint.x >= points[0].x && interPoint.x <= olderX) && (interPoint.x > point.x)) {
                     noOfIntersections++;
                } 
            }
        }
        olderX = points[0].x;
        olderY = points[0].y;
    }
    if (noOfIntersections % 2 == 0) {
        result = FALSE;
    } else {
        result = TRUE;
    }
    return result;
}

Answer 5

Тривиальным решением было бы разделить многоугольник на треугольники и выполнить проверку треугольников, как описано здесь

Если у вас многоугольник CONVEX , возможно, есть более подходящий подход. Посмотрите на многоугольник как на коллекцию бесконечных линий. Каждая строка делит пространство на две части. для каждой точки легко сказать, находится ли она на одной стороне или другой стороне линии. Если точка находится на одной стороне всех линий, она находится внутри многоугольника.

Answer 6

C # версия ответа nirg здесь: я просто поделюсь кодом. Это может сэкономить кому-то время.

public static bool IsPointInPolygon(IList<Point> polygon, Point testPoint) {
            bool result = false;
            int j = polygon.Count() - 1;
            for (int i = 0; i < polygon.Count(); i++) {
                if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y) {
                    if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X) {
                        result = !result;
                    }
                }
                j = i;
            }
            return result;
        }

Answer 7

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

На основе алгоритма симуляции простоты в http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

Некоторые предикаты помощника:

exor(A,B):- \+A,B;A,\+B.
in_range(Coordinate,CA,CB) :- exor((CA>Coordinate),(CB>Coordinate)).

inside(false).
inside(_,[_|[]]).
inside(X:Y, [X1:Y1,X2:Y2|R]) :- in_range(Y,Y1,Y2), X > ( ((X2-X1)*(Y-Y1))/(Y2-Y1) +      X1),toggle_ray, inside(X:Y, [X2:Y2|R]); inside(X:Y, [X2:Y2|R]).

get_line(_,_,[]).
get_line([XA:YA,XB:YB],[X1:Y1,X2:Y2|R]):- [XA:YA,XB:YB]=[X1:Y1,X2:Y2]; get_line([XA:YA,XB:YB],[X2:Y2|R]).

Уравнение прямой, заданной 2 точками A и B (линия (A, B)):

                    (YB-YA)
           Y - YA = ------- * (X - XA) 
                    (XB-YB) 

Важно, чтобы направление вращения линии установлен по часовой стрелке для границ и против часовой стрелки для дырок. Мы собираемся проверить, находится ли точка (X, Y), то есть проверенная точка слева полуплоскость нашей линии (это вопрос вкуса, это также может быть правая сторона, но и направление линий границ должно быть изменено в в этом случае), это для проецирования луча из точки вправо (или влево) и подтвердите пересечение с линией. Мы выбрали проект луч в горизонтальном направлении (опять же, дело вкуса, это также может быть сделано по вертикали с аналогичными ограничениями), поэтому мы имеем:

               (XB-XA)
           X < ------- * (Y - YA) + XA
               (YB-YA) 

Теперь нам нужно знать, находится ли точка слева (или справа) от только отрезок, а не вся плоскость, поэтому нам нужно ограничить поиск только этим сегментом, но это легко, так как быть внутри сегмента, только одна точка в линии может быть выше чем Y по вертикальной оси. Поскольку это более сильное ограничение, должен быть первым, чтобы проверить, поэтому мы берем сначала только те строки выполнение этого требования, а затем проверить его возможность. У Иордана Теорема кривой любой луч, проецируемый на многоугольник, должен пересекаться на четное количество строк. Итак, мы сделали, мы бросим луч к право, а затем каждый раз, когда он пересекает линию, переключать свое состояние. Однако в нашей реализации мы собираемся проверить длину пакет решений, отвечающих заданным ограничениям, и решите участие в этом. для каждой линии в многоугольнике это должно быть сделано.

is_left_half_plane(_,[],[],_).
is_left_half_plane(X:Y,[XA:YA,XB:YB], [[X1:Y1,X2:Y2]|R], Test) :- [XA:YA, XB:YB] =  [X1:Y1, X2:Y2], call(Test, X , (((XB - XA) * (Y - YA)) / (YB - YA) + XA)); 
                                                        is_left_half_plane(X:Y, [XA:YA, XB:YB], R, Test).

in_y_range_at_poly(Y,[XA:YA,XB:YB],Polygon) :- get_line([XA:YA,XB:YB],Polygon),  in_range(Y,YA,YB).
all_in_range(Coordinate,Polygon,Lines) :- aggregate(bag(Line),    in_y_range_at_poly(Coordinate,Line,Polygon), Lines).

traverses_ray(X:Y, Lines, Count) :- aggregate(bag(Line), is_left_half_plane(X:Y, Line, Lines, <), IntersectingLines), length(IntersectingLines, Count).

% This is the entry point predicate
inside_poly(X:Y,Polygon,Answer) :- all_in_range(Y,Polygon,Lines), traverses_ray(X:Y, Lines, Count), (1 is mod(Count,2)->Answer=inside;Answer=outside).

Answer 8

Java версия:

public class Geocode {
    private float latitude;
    private float longitude;

    public Geocode() {
    }

    public Geocode(float latitude, float longitude) {
        this.latitude = latitude;
        this.longitude = longitude;
    }

    public float getLatitude() {
        return latitude;
    }

    public void setLatitude(float latitude) {
        this.latitude = latitude;
    }

    public float getLongitude() {
        return longitude;
    }

    public void setLongitude(float longitude) {
        this.longitude = longitude;
    }
}

public class GeoPolygon {
    private ArrayList<Geocode> points;

    public GeoPolygon() {
        this.points = new ArrayList<Geocode>();
    }

    public GeoPolygon(ArrayList<Geocode> points) {
        this.points = points;
    }

    public GeoPolygon add(Geocode geo) {
        points.add(geo);
        return this;
    }

    public boolean inside(Geocode geo) {
        int i, j;
        boolean c = false;
        for (i = 0, j = points.size() - 1; i < points.size(); j = i++) {
            if (((points.get(i).getLongitude() > geo.getLongitude()) != (points.get(j).getLongitude() > geo.getLongitude())) &&
                    (geo.getLatitude() < (points.get(j).getLatitude() - points.get(i).getLatitude()) * (geo.getLongitude() - points.get(i).getLongitude()) / (points.get(j).getLongitude() - points.get(i).getLongitude()) + points.get(i).getLatitude()))
                c = !c;
        }
        return c;
    }

}

Answer 9

Я сделал на Python реализацию nirg c ++ code :

Входы

• bounding_points: узлов, составляющих многоугольник.

• bounding_box_positions: точек-кандидатов для фильтрации. (В моей реализации создано из ограничительной рамки.

  (Входные данные представляют собой списки кортежей в формате: [(xcord, ycord), ...])

Возвращает

• Все точки, которые находятся внутри многоугольника.

def polygon_ray_casting(self, bounding_points, bounding_box_positions):
    # Arrays containing the x- and y-coordinates of the polygon's vertices.
    vertx = [point[0] for point in bounding_points]
    verty = [point[1] for point in bounding_points]
    # Number of vertices in the polygon
    nvert = len(bounding_points)
    # Points that are inside
    points_inside = []

    # For every candidate position within the bounding box
    for idx, pos in enumerate(bounding_box_positions):
        testx, testy = (pos[0], pos[1])
        c = 0
        for i in range(0, nvert):
            j = i - 1 if i != 0 else nvert - 1
            if( ((verty[i] > testy ) != (verty[j] > testy))   and
                    (testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]) ):
                c += 1
        # If odd, that means that we are inside the polygon
        if c % 2 == 1: 
            points_inside.append(pos)


    return points_inside

Опять же, идея взята из здесь

Answer 10

.Net порт:

    static void Main(string[] args)
    {

        Console.Write("Hola");
        List<double> vertx = new List<double>();
        List<double> verty = new List<double>();

        int i, j, c = 0;

        vertx.Add(1);
        vertx.Add(2);
        vertx.Add(1);
        vertx.Add(4);
        vertx.Add(4);
        vertx.Add(1);

        verty.Add(1);
        verty.Add(2);
        verty.Add(4);
        verty.Add(4);
        verty.Add(1);
        verty.Add(1);

        int nvert = 6;  //Vértices del poligono

        double testx = 2;
        double testy = 5;


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