Всем доброго дня. Есть задача, думаю над оптимальным алгоритмом ее решения.
Есть плоскость, на плоскости полигон (красный). Также, на этой плоскости есть ломанные линии. Необходимо найти процент заполнения площади полигона другими линиями.
На входе дано:
— Координаты узловых точек красного полигона. Массив
— Массив ломанных линий. Внутри которого пара точек прямой.
— Координаты узловых точек малых полигонов. Внутри которого массив точек малого полигона.
Условно разделим красный полигон на квадраты. Необходимо найти процент заполнених квадратов, которые входят внутрь данного красного полигона, что будет равносильно поставленной задаче, но с бОльшей погрешностью.
Вот мой алгоритм, но понимаю, что он в лоб, хотелось бы получить более оптимальный.
0) Строю массив квадратов внутри полигона. Элемент массива — пара объектов "точка" (2 координаты) и флаг пересечения. Массив одномерный.
1) Получаю вершины красного полигона. P1, P2, P3... Pn
2) Иду по элементам массива объектов — линий, получая пару координат вершин. p'1 и p'2
3) Выбираю подмассив из массива квадратов, ограниченный максимальными и минимальными координатами линии
4) Иду по подмассиву, получая объекты "квардат"
5) Проверяю на пересечение линии P1-P2 и p'1-p'2; P2-P3 и p'1-p'2; P3-Pn и p'1-p'2. Т.е. проверяю каждую сторону квадрата на пересечение с полученной линией. Если хоть линии пересекаются, ставлю флаг пересечения к текущему квадрату. Увеличиваю счетчик заполненных квадратов
6) Следующий объект — "квадрат"
7) Следующий элемент — "линия"
8) Подсчитываю общее количество квадратов внутри красного полигона. Получаю процент заполненной площади.
Прошу помощи в нахождении более быстрого, а может и простого решения.
Благодарю
