Как найти общую площадь комплекса плоских фигур, накиданных произвольно, возможно с пересечениями.
Заранее спасибо.
Здравствуйте, Desperatov, Вы писали:
D>Как найти общую площадь комплекса плоских фигур, накиданных произвольно, возможно с пересечениями.
Сначала надо все их объединить. Для объединения/пересечения и т.д. в векторной форме можно использовать, например вот это:
http://www.cs.man.ac.uk/aig/staff/alan/software/
Эта операция может быть весьма дорогой, особенно если многоугольников много. Алгоритм Алана (Bala R.Vatti, если быть точным) может объединить два многосвязных мнгогоугольника (как при вызове функции WinAPI PolyPolygon). Но в данной задече нам придется объединять строго по одному. То есть берем два, объединяем. Далее берем следующий и объединяем с результатом и т.д. Казалось бы, можно интерпретировать все полигоны как один многосвязный и объединить его с пустым множеством, но этот номер не пройдет, поскольку в местах пересечений возникнут дыры. Данный алгоритм умеет работать только по правилу even-odd.
После того, как результирующий мульти-полигон найден, считаем площадь. Для этого суммируем площади всех односвязых полигонов:
http://astronomy.swin.edu.au/~pbourke/geometry/polyarea/
http://astronomy.swin.edu.au/~pbourke/geometry/polyarea/source1.c
Площадь получается со знаком, определяющим направление обхода, поэтому берем модуль.
Но здесь тоже есть засада с самопересекающимися полигонами, например для четырехугольника:
(0,0) (10,0) (0,10) (10,10) вычисленая площадь будет 0.
Но похоже (не уверен на 100%), что алгоритм Алана справляется с такими перевертышами — на выходе вместо самопересекающегося четырехугольника у нас будет шестиугольник без самопересечений.
MS>Сначала надо все их объединить. [. . .]
Кстати, если не нужна очень-очень большая точность, то все полигоны можно растеризовать в битовую матрицу, после чего посчитать единичные пикселы. На экранных разрешениях это может быть раз в 10 быстрее. Для растеризации можно использовать любой доступный способ, например, такой:
http://www.rsdn.ru/Forum/Message.aspx?mid=461727&only=1Автор: McSeem2
Дата: 30.11.03
Даже можно средствами WinAPI — создаем монохромный MemDC, рисуем в нем фигуры стандартными функциями, после чего считаем площадь.
Ваши советы пришлись кстати. Спасибо.
