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

Question

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

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

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

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

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

Answer 1

См. здесь

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

НТН

EDIT Есть еще один вопрос, связанный с этим вопросом, который можно найти здесь

Answer 2

Джастин,

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

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

Answer 3

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

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

Проверьте, если sy

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

Answer 4

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

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

Answer 5

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

Answer 6

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

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