групирование точек
От: Аноним  
Дата: 14.06.10 20:14
Оценка:
Есть масив точек, каждая из которых задаётся 2 координатами Х и У.
Как выбрать подмножество этих точек, растояние между которыми не будет привышать заданное?
Re: групирование точек
От: dilmah США  
Дата: 14.06.10 20:30
Оценка:
А>масив задаётся растояние привышать

офф: я восхищаюсь: правильно расставлены запятые и ДАЖЕ ТОЧКИ НАД Ё

по теме: наверно не просто подмножество, а максимальное или какое? Можно подмножество из одного элемента всегда выбрать..
Re[2]: групирование точек
От: Аноним  
Дата: 14.06.10 20:42
Оценка:
D>офф: я восхищаюсь: правильно расставлены запятые и ДАЖЕ ТОЧКИ НАД Ё

D>по теме: наверно не просто подмножество, а максимальное или какое? Можно подмножество из одного элемента всегда выбрать..


офф: Прошу прощения, русский — не мой родной, но я стараюсь)

по теме: да, конечно максимальное
Re: групирование точек
От: adalekin Россия IT Rightway
Дата: 14.06.10 21:31
Оценка:
Здравствуйте, Аноним, Вы писали:

> Есть масив точек, каждая из которых задаётся 2 координатами Х и У.

> Как выбрать подмножество этих точек, растояние между которыми не будет привышать заданное?

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

Возможно удастся модифицировать алгоритма Джарвиса (заворачивания подарка). В момент нахождения вершины выпуклой оболочки проверять расстояние между вершинами. Если расстояние между найденной вершиной и текущей превышает заданное, исключать найденную вершину из поиска и начинать обход Джарвиса заново.
avalon 1.0rc2 rev 272
Re: групирование точек
От: hudvin  
Дата: 14.06.10 21:35
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Есть масив точек, каждая из которых задаётся 2 координатами Х и У.

А>Как выбрать подмножество этих точек, растояние между которыми не будет привышать заданное?

возможно, kd tree
Re: групирование точек
От: denisko http://sdeniskos.blogspot.com/
Дата: 15.06.10 02:41
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Есть масив точек, каждая из которых задаётся 2 координатами Х и У.

А>Как выбрать подмножество этих точек, растояние между которыми не будет привышать заданное?
Построение диаграммы вороного и использование метода цепной развертки после этого. В инете есть все описания.
<Подпись удалена модератором>
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.