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