LINUX.ORG.RU

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

 , интересная задача


0

4

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

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

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

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

★★★★★

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

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

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

qulinxao ★★☆
()

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

Anon
()

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

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

cool-e-bin
()
Ответ на: комментарий от qulinxao

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

AIv ★★★★★
() автор топика
Ответ на: комментарий от pathfinder

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

AIv ★★★★★
() автор топика
Ответ на: комментарий от Anon

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

AIv ★★★★★
() автор топика
Ответ на: комментарий от cool-e-bin

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

AIv ★★★★★
() автор топика

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

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

pathfinder ★★★★
()
Последнее исправление: pathfinder (всего исправлений: 1)

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

anonymous
()

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

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

O02eg ★★★★★
()
Ответ на: комментарий от anonymous

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

AIv ★★★★★
() автор топика
Ответ на: комментарий от O02eg

Да.

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

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

AIv ★★★★★
() автор топика
Ответ на: комментарий от AIv

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

O02eg ★★★★★
()
Ответ на: комментарий от AIv

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

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

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

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

aa
aa
Здесь каждый символ сетки, это узел. Для каждого из этих узлов известно правильное значение (на сфере), так, что суммарная «близость на сфере» всех значений смежных узлов оптимальна. Cам лист с неизвестными оптимальными значениями имеет вид:
......
......
..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.

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

pathfinder ★★★★
()
Последнее исправление: pathfinder (всего исправлений: 1)

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

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

ebantrop
()
Ответ на: комментарий от ebantrop

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

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

AIv ★★★★★
() автор топика
Ответ на: комментарий от O02eg

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

AIv ★★★★★
() автор топика
Ответ на: комментарий от ebantrop

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

AIv ★★★★★
() автор топика
Ответ на: комментарий от AIv

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

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

O02eg ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.