Страницы

Поиск по вопросам

вторник, 26 ноября 2019 г.

Как равномерно распределить N точек на M зон?


Дано двумерное пространство. Даны N точек с заданными координатами. Нужно распределит
точки в M зон. В каждую зону нужно поместить количество точек равное целому частном
M/N или M/N+1. Способ определения кому достанется M/N, а кому M/N+1 значения не имеет. Внешний контур зон должен быть выпуклым. Зоны не должны пересекаться, а если это невозможно, то в пересечении зон, не должно быть внутренних точек.

Например,



Следующий вариант плохой


Я затрудняюсь перенести это условие на формальный язык. В реальной задаче (N>5000
M~50) вариант с красными стрелками не подходит, потому что для "коммивояжеров" получится слишком неудобный участок



Похожие вопросы


Поиск геометрического центра группы объектов в 3D пространстве с предварительно
фильтрацией
Какой существует алгоритм для объединения точек в области?
Структура данных для упорядочения двумерных точек


Ссылки по теме


Хабрахабр. Андрей Часовских @andreycha. Обзор алгоритмов кластеризации данных.

    


Ответы

Ответ 1



Точное решение с доказательством я привести не могу, но могу дать несколько направлений. Первый вариант Можно построить частный случай Kd-дерева, когда каждой области принадлежит по 1 точке а после начать объединять области снизу, используя данное условие. Если точки находятся "близко", то они будут соседями на соседних уровнях, и поэтому объединятся в первую очередь. Второй вариант Второй вариант предполагает построение диаграммы Вороного. Для каждой точки находи ближайшие границы. Области можно объединять только с областями, которые смежные с данными границами. В данном случае будет усеченный перебор, так как в среднем у каждой точки будет мало таких границ. Худший случай - точки расположены строго по гексагональной сетке. Рекомендую посмотреть "Mark de Berg - Computational Geometry Algorithms and Applications". Там будет описание построения данных структур. Я бы начал с первого варианта, так как Kd деревья реализуются достаточно просто информации по ним больше, возможно, даже можно найти пример с объединением по условию, так как эти деревья имеют много применений. Диаграммы Вороного проще "дебажить" графически и есть много реализаций на разных языках, поэтому базу можно быстрее сделать. Если отталкиваться от "в приоритете близость точек друг к другу и равное количеств для каждой зоны", то диаграммы Вороного могут быть лучше, так как у них при построени похожая задача стоит. Возможно, можно доказать транзитивность этого условия между областями. Тогда достаточно будет построить диаграмму второго порядка, их в книге вроде нет, но можно найти несколько статей на эту тему. К сожалению, готовых реализаций для диаграмм высших порядков я не встречал, поэтому придется писать самостоятельно.

Ответ 2



Во-первых, замечу, что выпуклость контуров сама по себе не имеет смысла. Потому ка контур любого кластера будет выпуклым. Требование выпуклости нужно для определения пересечений. Вам для кластеризации подойдет алгоритм нечеткой кластеризации c-means, который являетс модификацией алгоритма k-means. Им обоим для работы требуется заранее знать количество кластеров для поиска, а это как раз ваш случай. Но у c-means есть то преимущество, перед k-means, что он для каждой точки дает нечеткую оценку принадлежности к кластерам. Оценку пересечений нужно так же сделать нечеткой. То есть нужно знать насколько сильно пересекаются кластеры. Далее, можно попробовать несколько эвристик: Модифицировать c-means так, что в случае когда точка "близка" одновременно нескольки кластерам учитывать пересечение контуров, то есть "приближать" точку к тому кластеру который "уменьшает" пересечение. Попробовать уменьшить пересечения за счет обмена "близкими" точками между пересекающимс кластерами. Если кластеры пересекаются, то велика вероятность что и другие их точки также "близки", чем точки из других кластеров. Чтобы уменьшить пересечение нужно найти "виновников" пересечения и опробовать и забрать\отдать. При этом если в одном кластере будет нехватать точек, то в другом буде из избыток. Чтобы этого избежать можно забирать или отдавать точки любым кластерам к которым эти точки близки. В результате возникнет волна обменов, ее нужно остановливать если оценки пересечений начинают ухудшаться. Так же как и в предыдущем варианте, но попробовать направлять волны обменов дру на друга чтобы они погасились. То есть волну "изъятия" нужно направлять на волну "отдающуюю". Для алгоритма k-means очень важен выбор первоначальных центров кластеров. В случа если в какой-то области получилось много пересечений, то можно перестартовать k-means приблизив первоначальные центы к пересечениям чтобы они поглотились новыми кластерами. При этом рестарт необязательно выполнять для всех точек, если другие кластеры далено от проблемного места их можно не трогать.

Комментариев нет:

Отправить комментарий