Comments 13
проверяют, что y координата точки находится в диапазоне y координат ребра,
Тут все чуть более хитро. Там есть один крайний случай: если луч проходит через вершину многоугольника. Тут есть две разных ситуации: луч касается многоугольника в вершине, или пересекает границу в вершине. В первом случае надо подсчитать 2 или 0 пересечения, а во втором - 1.
Поэтому нельзя просто смотреть, что y координата точки лежит в интервале координат отрезка. Ведь, если концы считать за пересечение, то во всех случаях будет насчитано 2. А если не считать - то 0. А надо как-то 1 получить при пересечении в вершине. Надо как-то по особому учитывать концы. Решение в лоб было бы отдельно смотреть на концы и соседние вершины, что бы понять, что они по разные стороны от луча. Более хитрый варинат - всегда считать только нижние концы каждого отрезка, что тут и происходит.
Условие((yi > y) != (yj > y)) . При y=yi даст истину, только когда скобки дадут false != true, а значит yj > yi. Таким образом, пересечение подсчитается, только если y = yi < yj, т.е y - это нижняя граница отрезка.
Если что, на Rosetta Code есть реализации для чего угодно: https://rosettacode.org/wiki/Sutherland-Hodgman_polygon_clipping
Алгоритм Сазерленда-Ходжмана.
Статья понравилась, спасибо.
Я как раз тоже последние лет 5 увлекаюсь вычислительной геометрией.
И за последний год написал библиотеку для вычисления результатов пересечения многоугольников: xor, union, intersection and difference. Первое время пытаешься решать задачу (как и автор статьи) во float числах. Через какое-то время приходит осознание, что из-за потери точности задача в принципе не разрешима в общем случаи. С переходом на int появляется детерминизм и становится сильно проще. Например, параллельность отрезков можно проверять через векторное произведение и тд. С float такие фокусы не проходят. Введение epsilon не спасает, а только маскирует проблему.
С вашего позволения оставлю ссылку на свою имплементацию на
https://github.com/iShape-Rust/iOverlay
и
https://github.com/iShape-Swift/iOverlay
При использование f64 вероятность вырожденных случаев снижается, но не исключает их. Проблема в том, что вырожденные случаи если их правильно не обработать приводят к неправильной логике алгоритма, а это может повлечь за собой не только не правильный результат, но и зацикливание или краш.
Для работы с невыпуклыми полигонами мне помогало пронумеровать рёбра, и добавить номер ребра к параметру u в формуле для ребра p1 + u * (p2 - p1), т.е. задать в параметрическом виде весь полигон, а не одно ребро. Тогда u от 0 до 1 -- пересечение на первом ребре, от 1 до 2 -- на втором ребре и т.д., и можно собирать все точки (и исходные вершины, и пересечения) в один список (точнее, два списка -- для первого полигона и для второго), сортировать по u и, собирать в правильном порядке. Причём, при разном "правильном порядке" получался и OR, и AND, а если постараться -- то и A-B и B-A.
Но вот на ошибках вычисления с плавающей точкой я заломался, там даже f64 не хватало.
Спасибо за материал.
PS: слишком мало this в коде ))) это что за язык где такая потребность?
А можно ли составить пересечение двух выпуклых полигонов за O(N+M), где N и M - количества вершин в оных?
Навскидку, если они оба представлены массивами вершин в порядке обхода по часовой стрелке, то напрашивается метод двух указателей: берем любую вершину одного, ближайшую к ней вершину второго, и далее обходим первый по часовой стрелке, двигая второй указатель вперед, только если для него следующая вершина ближе к текущей вершине первого. Так мы рано или поздно сможем поймать точку пересечение ребер (примыкающих к вершинам, на которых стоят указатели), а от неё примерно тем же способом собрать искомый контур.
Навскидку вроде кажется что число вершин пересечения не превышает N+M, так что такой алгоритм может и существует. Но ваш не работает потому что если ребро первого полигона пересекается двумя ребрами второго то вы проскочите точку (2 точки) пересечения.
Можно. Ваша идея должна работать, только там всякие частные случаи надо обрабатывать.
Есть подход чуть проще - разбейте каждый полигон на 2 ломаные - верхнюю и нижнюю. Потом проходим сканирующей прямой слева-направо. В каждом промежутке между любыми x координатами вершин эти 4 ломаные - это прямые. Пересечем две нижние границы, две верхние, и верхнюю от одного с нижней от другого многоугольника. Получим максимум 4 точки пересечения, отсортируем по оси OX, потом на каждом маленьком интервале никаких пересечений уже нет и быть не может. Все границы - непересекающиеся отрезки. Осталось только взять максимум из нижних границ и минимум из верхних. Можно по средней точке их сравнить.
Потом надо будет удалить вершины на сторонах, ибо мы так можем добавить несколько коллинеарных отрезков подряд.
Вот тут, вроде как, утверждается, что алгоритм линейный и при том весьма простой. Но сам я пока статью не читал и не разбирался, ничего прокомментировать не могу.
Алгоритм сортировки вершин можно оптимизировать если сортировать не по углу а по тангенсу, который в пределах каждого квадранта монотонная функция. Сначала по знакам находим квадрант, и если оба угла в одном квадранте, сортирует по тангенсу (не надо вычислять atan)
Алгоритм пересечения полигонов