Каморка

Необходимо получить точки пересечения полилинии PL с невыпуклым полигоном PG «без дыр».
В PL различают начальную и конечную точки, так что можно задать совокупность веторов, представленных сегментами PL.

Точки пересечения должны представлять полилинию PL_INT, каждый сегмент которой является вектором, коллинеарным вектору сегмента исходной полилинии PL.

Разумеется хочется красивый алгоритм. Пока сделал так:

PLPG – массив искомых точек пересечения (вершины PL_INT)

Цикл “А” по всем сегментам исходной полилинии PL:
1. Получить сегмент PL(i) полилинии PL (в начале цикла, очевидно первый сегмент PL(0)).

Цикл “B” по всем сегментам полигона PG:
2. Получить сегмент PG(j)
3. Проверить пересечение PG(j) c PL(i).
4. Если пересечение сушествует, то добавить точку
массив точек пересечения текущего сегмента PLPG(i).
5. Сортировать массив PLPG(i) по значению растояния точек
oт начала сегмента PL(i)
6. Добавить все точки массива PLPG(i) в результирующий
Массив PLPG
7. Конец цикла “B”
8. Конец цикла “A”


Спасибо.