Определение того, существует ли координата внутри многоугольника

Question

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

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

Мои исследования показывают, что самый простой способ — взять мою точку (которую я назову x) и точку вне многоугольника (назову ее y) и определить, пересекается ли линия ((xx, xy), (yx, yy)) с границы полигона.Если он пересекает нечетное количество раз, точка x должна находиться внутри многоугольника.

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

Очень признателен.

Answer 1

Видеть здесь

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

ХТХ

РЕДАКТИРОВАТЬЕсть еще один вопрос SO, который относится к этому вопросу, который можно найти здесь

Answer 2

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

Если ваша точка — P = (x,y), а конечные точки сегмента — P1 = (x1,y1) и P2 = (x2,y2), координата y сегмента, в котором он пересекает x, определяется выражением sy = (x- x1)*(y2-y1)/(x2-x1) + y1

Проверьте, соответствует ли sy < y (только если x1 < x < x2 или x2 < x < x1).Если их нечетное количество, то P находится внутри.

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

Answer 3

Джастин,

Вам также может потребоваться лучше определить «вне многоугольника», чтобы построить сегмент.

Возьмите минимальное и максимальное значения всех координат x и y и постройте прямоугольник (xmin,ymin),(xmax,ymin),(xmax,ymax),(xmin,ymax).Любая точка за пределами прямоугольника определенно будет за пределами многоугольника — тогда продолжайте, как показано выше.Каждый сегмент многоугольника и построенная линия определяются уравнением y = ax + b и для каждого сегмента диапазоном xlo и xhi.Построенная вами линия либо пересекает сегмент диапазона, либо нет.То есть решение двух одновременных уравнений в сегментном диапазоне либо существует, либо нет.Просто посчитайте количество существующих решений, чтобы получить количество пересечений.

Answer 4

Я предполагаю, что вы находитесь в самолете (2D).

• Вычислите наклоны каждой стороны (в некоторой системе координат) и наклон линии от точки X до точки Y (линия XY).
• Для всех сторон, уклон которых не равен наклону XY, вычислите точку пересечения.
• Для каждой точки определите, находится ли точка пересечения на отрезке XY и отрезке линии, определяющем сторону.Если да, то вы перешли эту сторону.(Проверьте координаты пересечения и посмотрите, включены ли компоненты x и y в диапазон значений для каждого сегмента линии.)
• Подсчитайте количество пересечений и получите ответ.

Answer 5

Вычислите номер обмотки многоугольника и точки.

Answer 6

Попробуй это,

public static bool PointinPolygon( Point[] points, Point p )
    {
        bool result = false;

        for( int i = 0; i < points.Length - 1; i++ )
        {
            if( ( ( ( points[ i + 1 ].Y <= p.Y ) && ( p.Y < points[ i ].Y ) ) || ( ( points[ i ].Y <= p.Y ) && ( p.Y < points[ i + 1 ].Y ) ) ) && ( p.X < ( points[ i ].X - points[ i + 1 ].X ) * ( p.Y - points[ i + 1 ].Y ) / ( points[ i ].Y - points[ i + 1 ].Y ) + points[ i + 1 ].X ) )
            {
                result = !result;
            }
        }
        return result;
    }