Критерии большой пустой области

← →
Strech (2006-05-24 02:59) [0]

Доброго времени суток! Помогите определиться с критериями. Есть карта, большинство клеток которой занято. Как найти наибольшую по площади пустую область. Зрительно я вижу какая пустая область самая большая, но формализовать правила ее определения не могу :(

← →
Mortem © (2006-05-24 03:10) [1]

Зачем тебе это?
Алголист не помог?

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

Суть в следующем:
У тебя есть карта, например, 1024*2048.
Размещаешь на ней площадку с 8*8 узлами равномерно.
(Т.е. если карта 17*17, то во все четные позиции по X и Y).

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

Критерии большой пустой области Найти похожие ветки