Есть дырявый многоугольник, который задается просто массивом линий.
Каждая линия задается двумя точками начала и конца этой линии.
Необходимо построить сетку внутри этого многоугольника с некоторым шагом ▲T
Есть ли какая-нить библиотека на C# для этой задачи? Сам нашел, только для не дырявых многоугольников((
Сейчас придумал один способ сделать это, но думаю он медленный:
Алгоритм:
1) Разбить весь дырявый многоугольник на составляющие его многоугольники ( на замкнутые ломанные линии, тут должно быть ограничение, что стены не могут быть тонкими как спицы, это означает что каждая вершина должна быть соединена линиями только с 2 другими вершинами, не больше! а также самопересечений не было бы ).
Тогда получим массив массивом из линий ( массив многоугольников )
2) Далее найти самый большой многоугольник, хочу просто найти самый большой по площади ( пока решил сделать это с помощью Формула площади Гаусса(формула землемера или формула шнурования или алгоритм шнурования) )
Тогда самый большой многоугольник задает границу нашего исходного дырявого многоугольника, а все остальные многоугольники задают дыры.
3)Теперь берем любую вершину у самого большого многоугольника и пускаем волну, которая идет по четырем направлениям ( вверх, вниз, влево, вправо ) на шаг ▲t. Причем, мы разрешает волне распространяться только внутри самого большого многоугольника и снаружи всех остальных многоугольников - дыр.
Тогда получим массив точек волны - это и есть наша сетка. 