Выделение связных областей

Не совсем понял условие, но если нужно просто разбить на не пересекающиеся подмножества, то посмотри http://en.wikipedia.org/wiki/Disjoint-set_data_structure

c++ ибо пока с сд не определился язык любой.

листы между значениями(части) на одном узле или в «кластере» на «ближних» узлах конфигурационного пространства у которых(значений) ещё и «сферические координаты» в неконфигурационых коор. «близки»?

т.е стремление кластеризовать по близости(в конф) похожие(в сфер) измерения?

топик не читай , по сабжу отвечай.

Зато первый

Нифига не понял. Тебе что надо: кластеризацию или поиск связанных областей? Если поиск областей, могу код подбросить, реализовал когда-то для своих нужд (а то приходилось из-за одной этой фигни тащить целую лептонику!).

не можем их однозначно упорядочить (поскольку они на сфере, а не на кривой)

развёртка кривыми Гильберта-Пеано может быть поможет?

Эээ... а что в данном контексте подразумевается под словом «лист»?

«сечение»?

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

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

Ты бы хоть рисуночек какой привел, а то фиг поймешь!

прости, брателло - я не умею рисовать в пятимерном пр-ве;-(

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

Берем где-то в середине ожидаемого листа некий опорный узел с некоторым опорным значением. Считаем по алгоритму типа http://ru.wikipedia.org/wiki/Алгоритм_поиска_A* таблицу кратчайших растояний до опорной точки из любой другой точки. При этот сам алгоритм будет многомерен, перемещение из одного узла в сетки в другой можно совершить по разным значениям. Стоимость каждого перемещения рассчитывать исходя из удаленности значений на сфере.

«Лист» будет представлять собой совокупность узлов со значениями, которые «ближе всего» к опорной точке.

насчет сортировок, есть лексикографическая сортировка, ею можно упорядочивать многомерные множества

Не, я походу не прав.

Каждой точке сетки конфигурационного пространства соответствует список пар углов — координат на сфере?

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

Упорядочивать можно как угодно, но НЕВОЗМОЖНО упорядочить многомерное множество так, что бы близкие (по какой то там мере, напр эвклидовой) элементы были всегда близки в упорядоченном массиве, так что нифига это упорядочение не дает.

Да.

Пока вытанцовывается такой алгоритм. Надо для каждого значения найти номер листа (желательно, что бы листы были пронумерованы последовательно от нуля до какого то эн).

Берем последовательно одну за другой ячейки сетки в конфигурац. пр-ве. Для каждой ячейки берем ее узлы (4 в 2D случ, 8 в 3D), находим узел с мин. числом значений, перебираем все отсчеты, для каждого значения находим ближайшие значения из остальных узлов и помечаем как принадлежащие к общему листу (объединяем в маленький кластер), обрабатываем так все узлы. Остается объединить маленькие кластеры. Тут можно либо действовать рекурсивно (на удвоенной сетке), либо динамически приращивать новые значения к уже существующим кластерам и объединять кластеры в перевернутое дерево (от листьев к вершине).

Близость для точек листа меряется ещё и по координатам конфигурационного пространства? Т.е. лист неразрывен не только на сфере, но и на конфигурационном пространстве?

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

Но здесь очень важно правильно понять что и как надо перебирать. Тут должно быть что-то вроде последовательного «обволакивания».

Уф. Попробую объяснить.

Пускай у нас двухмерный случай и предположим, что у нас есть частичное решение А вида.

aa
aa

......
......
..aa..
..aa..
......
......

Так как фигура А является частью искомого листа, то добавим ещё один «обволакивающий» слой B:

......
.bbbb.
.baab.
.baab.
.bbbb.
......

Можно догадаться, присоединение слоя B возможно N способами, где N зависит количества значений во всех узлах слоя B. Соответственно мы можем для каждого из этих N способов посчитать целевую функцию f(А+B)

Добавим ещё один обволакивающий слой С:

сссссс
сbbbbс
сbaabс
сbaabс
сbbbbс
сссссс

Можно догадаться, что присоединение слоя С возможно M способами, где M зависит от количества значений во всех узлах слоя C. Для каждого из этих М способов нам достаточно выбрать только один (sic!) способ присоединения слоя B из N возможных. Выбираем самый оптимальный, с наилучшей целевой функцией, остальные отбрасываем. Так мы можем поступить потому, что связь слоев a-b внутренняя и никак не может повлиять на дальнее наращивание целевой функции при присоединении слоя С. Поэтому выбираем наилучший вариант N.

По такой схеме можно продолжить дальше.

Хотя, числа N и M могут быть весьма велики. Печаль. :(

Ну можно и так сказать. Вообще лист строится в конфиг. пр-ве.

Так а что вам в итоге то надо? Быстро искать близкие точки к заданой? Я бы попробовал загрубить координаты на сферах что то типа u_i = floor(x_i/cell_size) и зафигачить все в хеш-таблицу с ключами {u_i} и значениями {x_i}. Поскольку координаты узлов сетки не имеют ничего общего с координатами на сфере, то это просто еще одно поле в значении. Или я что то не понял?

Я так делал, когда надо было найти соседей (ближайшие точки) в девятимерном пространстве. Самое смешное что хватило питонова тупла с дефолтным хешем.

Ага и при этом точка не обязательно принадлежит узлу?

Уже в двух измерениях это не работает, см. про упорядочение.

Надо простроить неск листов;-)

В смысле? Если точка не принадлежит узлу, она принадлежит соседнему узлу, между узлами точек быть не может. Если в узле нету точки для соотв листа, в листе в этом месте дырка.

В смысле листу. Точка может не принадлежать какому-либо листу?

Надо простроить неск листов;-)

А что вы потом с этими листьями (или листами?) делать собираетесь?

Ну, гипотетически может существовать лист из одной точки.

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

Хм, для каждой точки можно посчитать пригодность к включению в лист аггрегируя расстояния до точек в соседних узлах. Точку с максимальной пригодностью, если пригодность выше некоторого порога, привязать к новому листу, затем из соседних узлов выбрать наиближайшую точку, привязать её к этому же листу. Затем из соседних к ним выбрать ещё одну, и т.д. пока расстояние не станет больше некоторого порога. Все точки, привязанные к этому листу удалить, повторить алгоритм заново.

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