Обрезка строки в двумерный многоугольник

Question

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

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

Спасибо!

Answer 1

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

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

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

Answer 2

• Шаг первый: найти все перекрестки баллов, в любом порядке. Для многоугольника вам нужно найти пересечение красного линии и линии каждого сегмента. Просто разрешите систему двух линейных уравнений. Если решение ограничено границами сегментов полигона, у вас есть пересечение.
• Шаг второй: сортировать найденные точки по позиция на красной линии. Вы знаете, что первая и последняя точка являются внешними. «Изюминка» переворачивается с каждой точкой - внешним-внутренним-внешним и так далее. Между двумя соседними внешними точками у вас есть внутренний отрезок (зеленый). Edit: not true ... Начать с точки № 0, сегмент # 0 - # 1 является внутренним, затем внешним, затем снова внутренним и так далее.

Если область не является полигоном, но задана некоторой неявной функцией, вам нужно найти, где эта функция равна красной строке (конечно, подход зависит от функции).