Генерализовать точечные объекты по количеству

Question

Приветствую всех

Сижу и туплю ;)

Дано: точечный слой. Задача: создать другой точечный слой, где каждая точка будет создана "примерно" центрально от заданного числа точек, ну, скажем, вокруг 200 точек.

Просто генерализовать группы точек в несколько крупных - не проблема, есть инструменты типа Aggregate points в Cartography toolbox и другие.. Но вот чтобы сказать - создать точку, которая будет представлять типа центроида заданного числа точек поблизости - не знаю.

Идеи в студию! :)

Answer 1

...Просто генерализовать группы точек в несколько крупных - не проблема...

    
What about ConvexHull?

Answer 2

Подробнее можно? Вы имеете в виду xtools? Если чисто инструментами ArcGIS?

Answer 3

1) ArcGIS 10: "Minimum Bounding Geometry" tool
http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//00170000003q000000.htm

2) ArcGIS 9.3:
- Custom geoprocessing function tool (Convex Hull)
http://resources.esri.com/help/9.3/arcgisengine/dotnet/6E47DF32-5B74-471A-8F76-156C7B9C7D78.htm

- "Create Minimum Convex Polygons" in Hawth's Tools
http://www.spatialecology.com/htools/download.php

Answer 4

Все бы хорошо, но вот как указать, какое количество точек будет объеденено в одну? Например, сказать 200 точек будут объединены в одну, которая будет представлять вроде их центроида что ли.. потом другие 200 точек объединены в центроид.. естественно точки из первого набора уже не участвуют в "группировке".

Answer 5

Я немного запутался. В первом ответе я специально процитировал:
"...Просто генерализовать группы точек в несколько крупных - не проблема..." - я думал эта проблема решена.
Если так и использовался Aggregate points too, то получим полигоны - затем получаем centroids.

"...как указать, какое количество точек будет объеденено в одну..."

Теперь не понимаю... Можно поподробнее?

Answer 6

Alexander, спасибо за обратную связь

Прошу прощения, самому-то понятно, чего надо, а вот объяснить.. ))

Если есть слой с 1000 точками, то я хочу на выходе получить только 5 точек, каждая из которых таким образом, будет представлять 200 точек из первого слоя. Т.е., алгоритм должен разбить все имеющиеся точки на 5 групп (в нашем примере), и для каждой из которых найти центроид.

Answer 7

Вроде готовая кластеризация есть только по максимальной дистанции между элементами, но не по числу элементов в кластере.
Видимо придётся изобретать.

Answer 8

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

Поэтому вот самое простое, что приходит в голову.
Брать самую удалённую вершину, объединять её и N ближайших к ней вершин в кластер.
И повторять для оставшихся вершин, пока они есть.
Ну и потом, понятное дело, для каждого из кластеров посчитать центр - например как среднее арифметическое координат вершин.

В некоторых случаях, конечно, может получиться некрасиво. Но в целом возможно и сгодится.

Или может быть можно построить Гамильтонов путь в графе и разбить его на участки по нужному числу вершин. При этом наложить условие на минимальную длину пути, т.е. это классическая "задача коммивояжера". Возможно получится более-менее нормально. А может и нет, понятия не имею.

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

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

Answer 9

В чём, кстати, прикладной смысл задачи?

Answer 10

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

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

- Для каждого кластера G1:
-- Найти центр C1 кластера G1.
-- Для каждой вершины V1 кластера G1:
--- Для каждого кластера G2, не равного G1:
---- Найти центр C2 кластера G2.
---- Найти в кластере G2 вершину, ближайшую к C1. Пусть это будет вершина V2.
---- Проверить, как изменится критерий оптимальности для G1 и G2 (с помощью C1 и C2), если V1 включить в G2, а V2 включить в G1. Если стало лучше, то меняем вершины и начинаем всё заново.

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