Раскраска полигонов

[Alexgis]

Есть около 2000 перекрывающихся полигонов.
Необходимо их раскрасить так, чтобы в местах перекрытия были только полигоны разных цветов:

• пересекающиеся полигоны должны быть разного цвета
• непересекающиеся полигоны могут быть одного цвета
• количество используемых цветов должно быть минимально.

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

Подскажите пожалуйста эффективных алгоритм. Ну или в какую сторону копать...

[Boris]

Задача "5 красок" имеет единственно верное решение - прямой перебор с возвратом. Не уверен, что в поставленном варианте, возможно решение именно с 5 красками. Может больше, может меньше. Зависит от данных.
Алгоритм "5 красок" - классический, решение описано во многих учебниках по программированию.
Теперь по постановке задачи - хз что описано. По описанию требуется либо 2 цвета, либо 2000*20. ЧТо значит пересечения разного цвета? Разного на сколько и пересечения чего с чем? Есть наложения в пересечениях? А как раскрашиваются они? А сколько всего пересечений сейчас, до раскрашивания? А в чем проблема их получить и покрасить? А в какой гис?

[Ariki]

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

Хотя если перекрываются 20 полигонов, всё равно получится каша, какого бы цвета они ни были.

И да, если количество цветов не ограничено, можно смело назначать их случайно: вероятность повтора очень мала

[Alexgis]

Алгоритм "5 красок" - классический, решение описано во многих учебниках по программированию.

Носом не ткнёте - сходу не нашёл...

ЧТо значит пересечения разного цвета? Разного на сколько и пересечения чего с чем?

Пересекающиеся полигоны (друг с другом) должны быть разного цвета.
Цвета из палитры по номеру (1,2,3...)

А в чем проблема их получить и покрасить? А в какой гис?

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

Хотя если перекрываются 20 полигонов, всё равно получится каша, какого бы цвета они ни были.
И да, если количество цветов не ограничено, можно смело назначать их случайно: вероятность повтора очень мала

Важно использовать минимальное количество цветов. Каша из 20 полигонов устраивает )). Полигоны это Convex hull + буфер вокруг точек, объединенных по некоторому признаку. Вот они и должны быть разного цвета

[trir]

1. Найти области пересечения
2. Для каждой области пересечения получить список полигонов
3. Для каждого полигона в списке назначить свой цвет из предварительно созданного списка цветов

Вариант №2
1. Найти области пересечения
2. Для каждой области пересечения получить список полигонов (list1)
3. Получить список полигонов, имеющих >1 области пересечения (list2)
4. Отсортировать list2 по убыванию
5. Обрабатываем list2
5.1. Получаем список доступных цветов для (list1)
5.2. Назначаем полигону первый доступный цвет
6. Обрабатываем list1
6.1. Получаем список доступных цветов для (list1)
6.2. Назначаем полигону доступный цвет

[Alexgis]

Вариант 1:
Такой подход не будет обеспечивать минимальное количество цветов.
Так получается около 90 цветов. Хотя каждый полигон не пересекается более чем с 20 другими
Вариант 2:
Я тоже пробовал - около 40 цветов получается

Визуально видно - что минимум цветов может быть в районе 20 - 25

[trir]

Так получается около 90 цветов

почему?

[Alexgis]

почему?

Цепочка (область пересечения) получается из 90 полигонов

[trir]

скрин бы приложил

можно построить диаграмму Вороного по областе пересечения - получить граф соседей и на основе него...

[Alexgis]

Вероятно действительно требуется делать перебор с возвратом - вот только алгоритм не придумывается.
Да ещё желательно чтобы прямо в Oracle обрабатывался.

[Alexgis]

Скрин не могу сейчас сделать.
Граф я могу получить на основе запроса.
Вот оказывается:Раскраска графов

Вариант 2: => жадная раскраска ))

[trir]

желательно чтобы прямо в Oracle обрабатывался

а в чём проблема?

[Alexgis]

Проблема теперь в поиске алгоритма Раскраски графов.
В wikipedia общие слова ...

[trir]

Ещё маленький момент - два близких, но не пересекающихся полигона, могут быть закрашенны одни цветом.
Поэтому стоит построить небольшие буферы по всем полигонам и аналезировать их.

[Alexgis]

Да! Буфера строю!