Является ли моя адаптация точки-в-полигоне (теорема кривой ordan) в python правильной?

проблема

Недавно я нашел необходимость определить, находятся ли мои точки внутри многоугольника. Поэтому я узнал об этом подходе на C ++ и адаптировал его к python. Тем не менее, код C ++, который я изучал, не совсем прав, я думаю? Я считаю, что исправил это, но я не совсем уверен, поэтому я надеялся, что люди ярче, чем я, может помочь мне немного осветить это?

Теорема супер проста, и идея такова, что при использовании n-го замкнутого многоугольника вы рисуете произвольную строку, если ваша точка внутри, линия будет пересекаться с ребрами нечетным числом раз. В противном случае вы будете ровны и находитесь вне полигона. Довольно шумно круто.

У меня были следующие тестовые примеры:

polygon_x = [5, 5, 11, 10] polygon_y = [5, 10, 5, 10] test1_x = 6 test1_y = 6 result1 = point_in_polygon(test1_x, test1_y, polygon_x, polygon_y) print(result1) test2_x = 13 test2_y = 5 result2 = point_in_polygon(test2_x, test2_y, polygon_x, polygon_y) print(result2) 

Вышеуказанное дало бы мне оба ложных, если бы я определил их следующим образом:

  if polygon_x[i] < polygon_x[(i+1) % length]: temp_x = polygon_x[i] temp_y = polygon_x[(i+1) % length] else: temp_x = polygon_x[(i+1) % length] temp_y = polygon_x[i] 

Это не верно! Я должен получить true для result1 а затем false для result2 . Так ясно, что-то фанки.

Код, который я читал на C ++, имеет смысл, за исключением вышеизложенного. Кроме того, мне не удалось выполнить тестовый temp_y которого мне temp_y что temp_y следует определять с помощью polygon_y а не с polygon_x . Конечно, когда я это сделал, мой тестовый пример для (6,6) проходит. Он все еще терпит неудачу, когда мои точки находятся на линии, но пока я нахожусь внутри полигона, он пройдет. Ожидаемое поведение.

Код Polygon, принятый для python

  def point_in_polygon(self, target_x, target_y, polygon_x, polygon_y): print(polygon_x) print(polygon_y) #Variable to track how many times ray crosses a line segment crossings = 0 temp_x = 0 temp_y = 0 length = len(polygon_x) for i in range(0,length): if polygon_x[i] < polygon_x[(i+1) % length]: temp_x = polygon_x[i] temp_y = polygon_y[(i+1) % length] else: temp_x = polygon_x[(i+1) % length] temp_y = polygon_y[i] print(str(temp_x) + ", " + str(temp_y)) #check if target_x > temp_x and target_x <= temp_y and (target_y < polygon_y[i] or target_y <= polygon_y[(i+1)%length]): eps = 0.000001 dx = polygon_x[(i+1) % length] - polygon_x[i] dy = polygon_y[(i+1) % length] - polygon_y[i] k = 0 if abs(dx) < eps: k = 999999999999999999999999999 else: k = dy/dx m = polygon_y[i] - k * polygon_x[i] y2 = k*target_x + m if target_y <= y2: crossings += 1 print(crossings) if crossings % 2 == 1: return True else: return False 

Резюме

Может кто-нибудь, пожалуйста, объясните мне, что temp_x и temp_y ? Кроме того, если мое исправление для переопределения temp_x для polygon_x и temp_y для polygon_y является правильным подходом? Я сомневаюсь в этом. Вот почему.

То, что происходит для temp_x и temp_y , не имеет для меня никакого смысла. Для i = 0 явно polygon_x[0] < polygon_x[1] false , поэтому мы получаем temp_x[1] = 5 и temp_y[0] = 5 . То есть (5,5) . Это просто одна из моих пар. Однако предположим, что я кормлю алгоритм моими пунктами не по порядку (по оси, попарная целостность всегда обязательна), что-то вроде:

 x = [5, 10, 10, 5] y = [10,10, 5, 5] 

В этом случае, когда i = 0 , получаем temp_x[1] = 10 и temp_y[0] = 10 . Хорошо, по совпадению (10,10) . Я также тестировал очки против «исправленного» алгоритма (9,9) и он все еще внутри. Короче говоря, я пытаюсь найти контрпример, потому что мое исправление не будет работать, но я не могу. Если это работает, мне нужно понять, что делает этот метод, и надеяться, что кто-то сможет мне это объяснить?

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

Большое вам спасибо за то, что выслушали мои мысли выше. Любые предложения очень приветствуются.

    Вы неправильно поняли значения x1 и x2 в связанном C ++-коде, и это недоразумение привело к тому, что вы выбрали неправильные имена переменных в Python. Обе переменные содержат значения x , поэтому temp_y является очень вводящим в заблуждение именем. min_x именами могут быть min_x и max_x , так как они являются минимумом и максимумом значений x вершин, составляющих край многоугольника. Более ясная версия кода может быть написана как:

     for i in range(length): min_x = min(polygon_x[i], polygon_x[(i+1)%length]) max_x = max(polygon_x[i], polygon_x[(i+1)%length]) if x_min < target_x <= x_max: # ... 

    Это, возможно, немного менее эффективно, чем стиль кода C ++, так как вызов min и max будет сравнивать значения дважды.

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

    Пример координат, который вы polygon_x = [5, 5, 11, 10] в коде ( polygon_x = [5, 5, 11, 10] и polygon_y = [5, 10, 5, 10] ), не описывает нормальный вид многоугольника. Скорее, вы получаете (слегка однобокую) форму лука-бабочки, с двумя диагональными краями, пересекающими друг друга, как X в середине. Однако это не проблема для этого алгоритма.

    Тем не менее, первая точка, которую вы тестируете, лежит именно на одном из этих диагональных ребер (тот, который обтекает список, начиная с последней вершины (10, 10) заканчивая первым (5, 5) ). Будет ли код определять, что он внутри или вне полигона, вероятно, сводится к округлению с плавающей запятой и выбору оператора между < или <= . В этой ситуации любой ответ можно считать «правильным».

    Когда вы переупорядочиваете координаты позже в вопросе (и, кстати, меняете 11 на 10 ), вы превратили лук-галстук в квадрат. Теперь тест (6, 6) полностью находится внутри формы, поэтому код будет работать, если вы не назначите координату y второй переменной temp .