|
LittelBigFace, значтся так:
1. Вычисляешь точки пересечения.
2. Добавляешь 4 точки так, чтобы прямоугольник по ним содержал все остальные точки и искомые точки не должны лежать на сторонах этого прямоугольник (это нужно чтобы избезать бесконечностей - все области должны быть замкнуты).
3. Дальше будем считать плоскости. Алгоритм сканирующий. Суть в том, чтобы идти по искомым точкам сверху вниз, следить за тем, какие полигоны замыкаются.
Считаем количество отрезков, примыкающих к верхней кромке прямоугольника. Получаем несколько полигонов "в разработке". По каждому из них мы знаем два отрезка, идущих от последней точки пересечения (в данном случае пересечения с прямоугольником). Берем точку минимальным y. В этой точке сходятся как минимум два отрезка из тех, что мы помним как граничные к полигонам "в разработке". Значит как минимум один полигон замкнулся (т.е. пересеклись его граничные отрезки), его выкидываем из "в разработке" в "готово". Из этой точки выходит несколько отрезков (те, что помечены как граничные или пройденные не считаем), т.е. еще как минимум один полигон переходит "в разработку". Если в точке полигон не замыкается, назначаем граничным отрезок из необработанных, примыкающих к этой точке, у когорого координата x ближе всего к координате х нижней точки второго граничного отрезка данного полигона.
Доходим до нижней линии прямоугольника, имеем список всех полигонов.
Брррррр, ну я и загнался. Придумал за 15 минут, могут быть подводные камни. Будут вопросы - пиши.
|