Есть массив граничных точек (заданных декартовыми координатами), ограничивающих некоторую область. Задача - подсчитать её площадь.

Задача осложняется тем, что внутри области могут иметься "дырки" - участки не принадлежащие области, но находящиеся внутри её внешних границ, и часть граничных точек принадлежит границе в такими "дырками", так что подсчёт методом треугольников не подходит.

Может кто-то решал уже такую задачу и есть готовое решение? Я был бы очень благодарен. 

Если кому надо - код на Delphi для решения этой задачи для выпуклых множеств методом треугольников:

Точно так же решается методом треугольников. С одной разницей - перед расчётом площади начального (первого) треугольника следует убедиться, что он лежит внутри фигуры, а после расчёта его площади - вырезаешь его из фигуры, и оставшуюся фигуру обсчитываешь с самого начала.

Akina, тогда не попадут области, принадлежащие множеству, но попадающие в те треугольники, на которые попадают "дырки" (за дырками).

В такой постановке Ваша задача не имеет однозначного решения. Необходима какая-то дополнительная информация. Например,  данные о том, какие подмножества точек формируют границы каких "дырок" (в предположении, что каждая дырка является выпуклой) или ограничение снизу на величину угла области или еще что-нибудь. В общем, надо брать "источник" задачи и формулировать дополнительные критерии, позволяющие сузить множество возможных решений.

Этой гениальной фразы я не понял... поясни с рисунком.

Akina, 

Присоединённый файл ( Кол-во скачиваний: 21 )
 дырка.JPG 14,61 Kb

Ааа... тогда у тебя не один массив граничных точек, а несколько. Кажды из них описывает свою область, один - внешний контур, остальные - внутренние.

Однако это вовсе не является проблемой. И есть даже два разных решения.

Первое. Если в случае без дырок каждый раз выбирался для обработки треугольник из трёх последовательных по контуру точек, то в случае с дырами допустимы как такой треугольник, так и треугольник с двумя соседними точками на одном контуре и одной точкой на другом контуре. При этом одиночная точка дублируется (их станет две), а контуры объединяются.

Второе. По вышеописанному алгоритму считается площадь дырки. С минусом. Дырка выбрасывается. Далее минусуется площадь второй дырки... третьей... когда все дырки посчитаны. полученная (отрицательная) площадь используется в качестве начального значения при расчёте площади внешнего контура. Дырки при этом уже не учитываются.

Само собой предполагается, что дырки не пересекаются ни друг с другом, ни с внешним контуром.

Добавлено через 6 минут и 55 секунд
Да. Дополнение к первому алгоритму.
Если было определено, что очередной построенный треугольник - внешний, то можно либо искать другой треугольник, который будет внутренним (как минимум два таких всегда есть), либо просто считать его плошадь отрицательной. Думаю, второе проще.

Akina, 
Фантом, 



Исходная задача такая:

1. Есть карта Москвы (или любого другого города) и массив граничных точек города.
2. Есть набор конусов вращения, заданных радиусами и высотами, а также центрами оснований (несколько десятков).
3. Эти конусы как-то пересекаются друг с другом и с границами города, причём высоты и радиусы каждый час меняются. 

Образуются области, ограниченные линиями пересечения конусов друг с другом и с границами города. Площади этих областей мне и требуется подсчитать. Точнее, задача несколько сложнее - надо так подбирать радиусы конусов, чтобы площади областей были равны заданным значениям.

При этом две области в разные моменты времени могут как быть вложенными одна в другую, так и просто граничить или вовсе не пересекаться.  Нужно еще определить, граница с какой областью является "дыркой", а с какой просто внешней границей.

Добавлено через 6 минут и 1 секунду


Увы, могут.

В таком случае сначала необходимо провести подготовку, и объединить все пересекающиеся контуры. Две дырки - в одну неправильно формы. Дырку и основной контур - в новый основной контур, с вырезом.

Да, а какая нужна точность подсчёта? а то может просто взять квадрат (прямоугольник) приличного размера (скажем 10к пикселей по каждой координате), покрасить белым, потом на него нанести в масштабе контуры города (чёрным), поверх него все твои конусы (белым), и, наконец, тупо посчитать количество оставшихся чёрных пикселей...

Akina, 

Подсчёт разноцветных пикселов, конечно, интересный метод, но мне не подойдёт, хотелось бы не закрашивать области.

Добавлено через 12 минут и 39 секунд
Впрочем, вы меня натолкнули на интересную мысль, может просто разбить область на квадраты и, определив принадлежность каждого квадрата к области, суммировать их площади?

Так не на экране же... берёшь скрытый контрол или прямо полотно - и на нём рисуешь. тебе ж не отображать, верно? ты все свои массивы, коллекции да рекордсеты ж на экране не рисуешь.

C "дырками" я научился бороться: 
1. При формировании массива граничных точек запоминаю к какой именно соседней областью данная  точка граничит
2. Прохожу по всем точкам, граничащим с одной и той же областью, нахожу центральную точку (полусумма минимальных и максимальных координат), упорядочиваю все эти точки по углу к центральной, и считаю максимальное расстояние между соседними точками упорядоченными таким образом. После последней точки идет первая.
3. Если максимальное расстояние между соседями меньше "эпсилон" (погрешности), то контур замкнут и мы имеем "дырку". В этом случае считаем её площадь методом треугольников, а при расчёте площади всей области этот контур не учитываем, а из общей площади вычитаем площадь дырки.

Всё хорошо работает, пока контур замкнут. Но если он хотя бы немного не замкнут, то это уже не срабатывает, а сильная невыпуклость области вызывает сильную ошибку в методе треугольников. 

Придётся, наверное, всё-таки считать пикселы.

Нельзя быть немножко беременной.


Площадь бывает только у замкнутой фигуры. И неважно, с дырками или без.


Это центр масс. И в твоём случае он не имееет ровным счётом никакого смысла, ни физического, ни математического.


А в чём смысл? Порядок точек в контуре не имеет ничего общего с полученным после сортировки порядком.

Akina, 



Разумеется, речь идёт о контуре "дырки". Внутри замкнутого контура может быть "дырка" незамкнутого контура. Общий контур при этом будет замкнутым и будет иметь площадь.

Вот, сделал подсчёт пикселей, как вы предлагали:



Тонкий момент - поиск внутренней точки. Предполагает, что область связная.

Проходим по "экватору" и считаем внутренней точкой следующий пиксель за первым прохождением границы.

Это сообщение отредактировал(а) Governor - 16.5.2013, 14:05

Ты думай, что говоришь-то... или хотя бы попробуй нарисовать... если это дырка - она замкнута, а если незамкнута - это просто полилиния, площадь которой нулевая.