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

[trir]

а если реализовать жадный алгоритм раскраски графа используя инструменты Oracle для графов?

[Alexgis]

А вот не нашёл там ничего. Да и жадный алгоритм на таблицах делается на раз два.

[ginpetr]

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

[Alexgis]

Когда: "Пересечение в точке разрешено" - "Да"
Не работает. Где-то ошибка - цвета могут пересекаться

пример

ex.png (7.3 КБ) 8165 просмотров

GR1.zip

(5.15 КБ) 327 скачиваний

[Alexgis]

Когда: "Пересечение в точке разрешено" - "Нет"
Очевидно использован приблизительный алгоритм

ex1.png (8.82 КБ) 8154 просмотра

По теореме о четырех красках можно раскрасить более оптимальным способом: 4 цвета вместо 5

ex2.png (5.82 КБ) 8150 просмотров

[ginpetr]

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

[ginpetr]

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

[Alexgis]

Действительно, топология...

[Alexgis]

Классическая жадная раскраска на MapBasic )))))
Через объединение таблиц.
Раскрашиваются все полигоны в таблице.

1) Строится таблица с rowID пересекающихся объектов.
2) Сортируем в зависимости от количества пересечений
3) Раскрашиваем объект

спасибо ginpetr, за команду для нахождения пересечений

ex3.png (26.69 КБ) 8047 просмотров

Относительно точного алгоритма
В программе, полигоны сортируются в зависимости от количества связанных полигонов в обратном порядке.
Всегда существует такой порядок, который приводит жадный алгоритм к оптимальному числу.
Однако количество перестановок равно n!
т.е. для 10 полигонов - количество перестановок = 3628800 )))

[trir]

деревья!