Группировка объектов на карте

[zerkms]

Группировка объектов на карте

Здравствуйте, господа.

дабы избежать непоняток - напишу в первых строках и жирным: данный вопрос СОВЕРШЕННО не касается клиент-сайда

Так вот, ситуация. Допустим, у нас есть группа объектов, которые нужно отрисовать на карте. Область карты представлена двумя координатами (topleft, bottomright)

Проблема: в текущей области может быть очень много объектов. соответственно - их нужно сгруппировать (для простоты представим - что объекты изначально одинакового типа).

Моё решение (очевидное, простое, мне не очень нравится): разбиваем область на квадраты. в каждом квадрате считаем число объектов. если в квадрате объектов > 1 - вычисляем для них центр масс (среднее арифметическое по каждой из координат).
решение не очень хорошее, потому что:
1. если в квадрате 2 объекта на противоположных углах - тогда после взвешивания получим один групповой маркер, в середине квадрата (хотя можно было бы показать оба, ибо они отставлены "далеко")
2. если в двух рядом стоящих квадратах в верхнем все точки были сосредоточены в нижней части (соответственно среднее значение - будет на нижней грани), а в нижнем - в верхней части, тогда получим два групповых маркера, очень близко расположенных (хотя - можно было бы, например, всю огромную пачку объектов в одной группе оставить).

Ваши варианты?

Я уверен, что существуют алгоритмы, но нагуглить не получается.

 

[tz-lom]

группировать надо не сеткой а на основе расстояний между объектами

далее зависит от задачи и её сложности
возможно тебе поможет map-reduce или же просто перебор
кстати перебор можно будет ускорить если ты оставишь сеточное деление и будешь его использовать в роли критерия близости ( рассматриваем только объекты в этой и соседней клетках) , таким образом можно сократить количество переборов

 

[dr-sm]

я группирую на клиенте, используя переписанный ClusterMarker, там довольно тупой алгоритм группировки. Думаю тоже переделать, но пока некогда думать )).
суть примерна такова его:

filterIntersectingMapMarkers: function() {
                        var zoomLevel = this.gmap.getZoom();
                        for (var i = this.mapMarkers.length - 1; i >= 0; --i) {
                                if (!this.mapMarkers[i].ex.makeVisible) {
                                        continue;
                                }


                                var clusterGroup = [];
                                for (var j = i - 1; j >= 0; --j) {
                                        if (this.mapMarkers[j].ex.makeVisible
                                        && this.iconBounds[zoomLevel][i].intersects(this.iconBounds[zoomLevel][j])) {
                                                clusterGroup.push(j);
                                        }
                                }
                                if (clusterGroup.length > 0) {
                                        clusterGroup.push(i);
                                        for (var j = clusterGroup.length - 1; j >= 0; --j) {
                                                this.mapMarkers[clusterGroup[j]].ex.makeVisible = false;
                                        }
                                        this.clusterMarkers.push(this.createClusterMarker(clusterGroup));
                                }
                        }
                },

тоже самое можно сделать и на сервер сайде,

 

[zerkms]

а. т.е. если 2 иконки накладываются друг на друга. интересно.

-~{}~ 25.07.10 21:35:

группировать надо не сеткой а на основе расстояний между объектами

угу. такой вариант, как "улучшение" моего - тоже был.

-~{}~ 25.07.10 21:41:

возможно тебе поможет map-reduce или же просто перебор

а по поводу мап-редьюса, намекни? не могу придумать что здесь должны делать маппер и редьюсер.

 

[newARTix]

в качестве бреда: делим + округляем координаты до тех пор пока они не сольются. кол-во сгруппированных объектов прямо пропорционально делителю.

-~{}~ 26.07.10 08:55:

и правда бред, это ведь и есть группировка по квадратам.

 

[fixxxer]

можно несколько вложенных сеток. оптимизация так сказать

еще что-то их общих соображений кажется что гексагонами лучше чем квадратами =)

 

[zerkms]

fixxxer
сложность ощутимо увеличивается тогда

решил оставить тогда пока тупо прямоугольными секциями, а потом, если будет время и желание - переделаю на перебор соседних

 

[tz-lom]

я так подумал над map - reduce возможно стоит на map шаге создавать группы из 2х точек у которых |x1-x2|<criteria или |y1-y2|<criteria а в reduce группировать множество по условию наличия группировки как по X так и по Y

правда возможна ситуация если они стоят в линию - они могут сгруппироваться хотя не должны

 

[Dovg]

zerkms
http://ru.wikipedia.org/wiki/Кластерный_анализ

Там есть несколько методик определения центров кластеров и элементов, которые будут в них входить. http://ru.wikipedia.org/wiki/K-means , например

 

[zerkms]

ох спасибо

 

[AmdY]

zerkms

если в квадрате 2 объекта на противоположных углах - тогда после взвешивания получим один групповой маркер, в середине квадрата

может просто стоит уменьшить квадраты, чтобы значения размера маркера и размера квадрата не сильно отличались (2 либо 4 маркера на квадрат)


p.s. С Днём Рождения. Успехов в жизни, любви, работе.

 

[zerkms]

AmdY
тогда группировка теряет смысл. квадрат должен быть таки больше маркера

ps: спасибо

 

[Splurov]

zerkms
Какая разница больше или не больше маркера, если в одном кусочке 10х10 пикселов тысяча маркеров, а в соседнем кусочке два маркера, логично показать один маркер в первом кусочке и один во втором. Поэтому если у тебя сейчас квадраты 100х100 и маркеры рассредоточены от уменьшения квадратов ты только выиграешь.

 

[zerkms]

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

 

[Splurov]

zerkms
Ок, пусть будет 40х40, речь не о конкретных цифрах, а о уменьшении квадратов. Короче если возникает проблема номер один из сабжа, значит квадраты можно и нужно уменьшать.

 

[zerkms]

Угу, у меня сейчас размеры как раз подбираются "немного больше маркера"
Так что предложение AmdY было правильным.