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

[Boris]

Нет, давайте все же вернемся к описанию задачи. Что именно должно быть разного цвета - пересечения, или пересекающиеся полигоны? Есть ли наложения в месте пересечения трех и более полигонов?
Потому как если нет наложений и каждый полигон имеет много пересечений, но каждое пересечение образовано только наложением двух полигонов, то задача сводится к задаче о раскраске карты. Что примыкание, что пересечение в этом случае задачи равноценные. И эта задача требует 5 разных красок. Наука говорит, что сейчас все сошлись на том, что их минимум 4. Поиск в гугле чего об этой проблеме на графах дал кучу результатов, один из 8 первых с кодом.

[Alexgis]

Boris,
1) Что именно должно быть разного цвета - пересечения, или пересекающиеся полигоны?
Разного цвета должны быть полигоны.
2) Есть ли наложения в месте пересечения трех и более полигонов?
Есть. Существуют области (места), в которых накладываются около 20 полигонгов.
теорема о четырёх красках здесь не применима - цветов будет больше.

[Boris]

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

[Alexgis]

Пример полигонов и их раскраски

[KolesovDmitry]

Просто, чтобы лучше понять задачу -- а зачем вам их раскрашивать? Что вы потом собираетесь с этим делать?

[Alexgis]

На всякий случай. Каждый полигон - одного цвета. При раскраске они не режутся.
Эффект разных цветов в примере - за счёт полупрозрачности.

[Alexgis]

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

Что вы потом собираетесь с этим делать?

Показать на карте...

[KolesovDmitry]

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

Что вы потом собираетесь с этим делать?

Показать на карте...

Тогда почему их просто не показать на карте так, как вы показали в примере (полупрозрачными)?

[Alexgis]

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

На рисунке, цвета проставлены вручную. А хотелось бы, чтобы это делал автомат.

[Ariki]

А в чём проблема? Вы правильно разобрались, что задача сводится к раскраске графа. По запросу "graph coloring algorithm" гуглится куча реализаций приближённого решения задачи:

С++
Python (исходный код библиотеки networkx)
Java

[Alexgis]

Ariki, спасибо - буду смотреть!
Сейчас и используется приближённый - беда в том, что он нестабильный.
Пробовали два варианта. И тот и другой дают не оптимальный результат в зависимости от данных.

Придётся делать точный, 2000 узлов - не так много.
Алгоритм ищется, желательно на pl/sql, чтобы яву не деплоить, но не принципиально...

[Ariki]

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

Точный алгоритм на таком количестве вершин использовать невозможно:
Википедия о сложности точного алгоритма

[Alexgis]

Википедия о сложности точного алгоритма

Жесть - я как-то на цифры не посмотрел сразу (((
Спасибо - похоже вопрос исчерпан...

[Boris]

Ну, судя по картинке, если показан типичный результат, то задача сильно легче полного перебора вариантов, т.к. объекты сгруппированы и нет единого непрерывного наложения. Вот если бы все 2000 полигонов создавали непрерывный объект, то дело было бы труба.

[Alexgis]

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