Обрезка линии до произвольного 2D-многоугольника - PullRequest
7 голосов
/ 15 октября 2010

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

alt text

Если целевой областью является не многоугольник, а неявная кривая или сплайн-кривая, как это сделать?

Спасибо!

Ответы [ 2 ]

5 голосов
/ 15 октября 2010

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

Недавно я выпустил бета-обновление * для моей библиотеки обрезки полигонов 'Clipper', которая выполняет обрезку линий-полигонов и линий-линий (где линии также могут быть кривыми). Однако, хотя основная библиотека написана на Delphi, C ++ & C #, новый бета-код пока только на Delphi, который может вам не помочь. Тем не менее, если вы посмотрите на код, вы поймете, почему я утверждаю, что нет «простого» решения.

  • Изменить 15 июля 2011 г .: Это «обновление» никогда не выходило за рамки этой бета-версии и теперь является просто «проверкой концепции». Теперь она основана на старой версии моей библиотеки Clipper, и для ее поддержки и расширения потребуется серьезная перезапись. (На каком-то этапе я могу вернуться к нему, но в настоящее время я намерен продолжать улучшать базовую библиотеку.) Тем не менее, этот «проверенный концепцией» код Delphi можно загрузить здесь

Clipper demo image

3 голосов
/ 15 октября 2010
  • Шаг первый: найти все точки пересечения в любом порядке.Для многоугольника вам нужно найти пересечение красной линии и линии каждого отрезка.Просто решите систему из двух линейных уравнений.Если решение ограничено пределами сегмента полигона, у вас есть пересечение.
  • Шаг второй: сортировка найденных точек по позиции на красной линии.Вы знаете, что первая и последняя точка являются внешними.«Внешность» меняется с каждой точкой - внешняя-внутренняя-внешняя и так далее.Между двумя смежными внешними точками у вас есть внутренний отрезок (зеленый).Редактировать: не верно ... Начните с точки № 0, сегмент № 0 - № 1 - внутренний, следующий - внешний, следующий - снова внутренний и т. Д.задается неявной функцией, вам нужно найти, где эта функция равна красной линии (подход, конечно, зависит от функции).
...