Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 1, средняя оценка - 5.00
Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
#1

Поиск трех ближайших точек к данной - C++

01.01.2014, 19:29. Просмотров 989. Ответов 21
Метки нет (Все метки)

Есть массив точек, заданных координатами х и y.
Нужно найти три ближайшие точки к данной, чтобы данная точка была в треугольнике, вершинами которого являются искомые точки.
Меня интересует самый быстрый алгоритм.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.01.2014, 19:29
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск трех ближайших точек к данной (C++):

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

Поиск двух ближайших друг к другу точек - C++
5. Разработать программу, которая ищет во введенном множестве точек (заданных парами координат) две ближайшие друг к другу и выводит...

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

Ввести координаты трех точек и ... - C++
Ввести координаты трех точек и по ним определить треугольник ето или нет если да то какой...Пожалуйста помогите очень надо (

Указать индексы седловых точек данной матрицы - C++
Элемент матрицы называется седловой точкой, если он является наименьшим в сторке и наибольшим в столбце или, наоборот, наибольшим в...

Определить образуют ли треугольник координаты трех точек - C++
Ввести числа , которые являются значениями коор-динат трех точек на плоскости. Определить, образуют ли они треуголь-ник (точки не лежат на...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
02.01.2014, 19:41  [ТС] #16
Цитата Сообщение от IrineK Посмотреть сообщение
И какое время хотелось бы получить?
Чем меньше тем лучше)
Пример выполняется за 0,003 с.
Но при увеличении колонн время существенно изменится.
0
IrineK
Заблокирован
03.01.2014, 06:44 #17
Основная идея альтернативного подхода такая.

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

В принципе, если я "сброшу" радиус сундука на эти препятствия, то задача сводится к прохождению пикселя, который может проходить и по границе препятствий (fig2 - там пиксель несколько преувеличен).

Дальше - волновой алгоритм нам в помощь. Заходим со стен комнаты.

Однако, волнует следующее. Обе картинки даны с зумом 50. Видим два пути, похожих на выходы: слева и внизу.

В реале сундук проходит внизу впритык (окружности касаются, но не пересекаются). Слева по расчетам сундуку не хватает 0,015 пикселя, чтобы протиснуться. Но мы ставим на построение карты, а не на расчеты. Исходя из "0,015" зума 200 достаточно, чтобы увидеть, что окружности слева "наезжают", а не касаются (fig3 - слева, fig4 - внизу, зум 200).

В общем, Брезенхейм и "правильный" масштаб нам алсо в помощь )
0
Миниатюры
Поиск трех ближайших точек к данной   Поиск трех ближайших точек к данной   Поиск трех ближайших точек к данной  

Поиск трех ближайших точек к данной  
Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
03.01.2014, 11:25  [ТС] #18
IrineK, Очень интересный метод!)
Спасибо)
0
Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
07.01.2014, 16:35  [ТС] #19
Никто не знает лучшего алгоритма?
1
uhx
60 / 60 / 6
Регистрация: 11.07.2013
Сообщений: 304
07.01.2014, 16:42 #20
Цитата Сообщение от Taras_Z Посмотреть сообщение
Четких ограничений на количество колонн сожалению нет.
Мде... классная задача. Тогда тайминг ничего не решает, ибо можно ввести максимальное число и тут даже самый оптимальный алгоритм не справится за секунду-другую.
0
Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
07.01.2014, 16:56  [ТС] #21
uhx, имеется в виду, что просто нужно улучшить алгоритм.
Я точно не знаю тайм-лимита, но мне нужно, чтобы он прошел.

Добавлено через 2 минуты
Со временем, попробую узнать ограничения.
0
HighPredator
5542 / 1848 / 345
Регистрация: 10.12.2010
Сообщений: 5,455
Записей в блоге: 2
08.01.2014, 00:05 #22
Цитата Сообщение от Taras_Z Посмотреть сообщение
Нужно найти три ближайшие точки к данной, чтобы данная точка была в треугольнике, вершинами которого являются искомые точки.
Плотно думать мне лень честно-говоря, но решение мне видится в следующем ключе. Поскольку исходное множество точек на плоскости расположено хаотично, то нужно его упорядочить, а именно отсортировать по возрастанию обеих координат. Это даст нам "неубывающую" последовательность точек. В таком случае, для поиска точек, удовлетворяющих условию задачи, нам нужно просто посмотреть К точек справа и слева от заданной, выбрать М минимальных расстояний и их проверять на "треугольник".
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.01.2014, 00:05
Привет! Вот еще темы с ответами:

Вычислить площадь треугольника по координатам трех точек на плоскости - C++
Пусть даны координаты трех точек на плоскости. Если они могут быть вершинами тупоугольного треугольника,вычислить его площадь. Выведите...

Вычислить координаты центра тяжести трех материальных точек - C++
Вычислить координаты центра тяжести трех материальных точек с массами m1, m2, m3 и координатами (x1, y1), (x2, y2), (x3, y3) по формулам: ...

найти номера координатных четвертей для трех точек с данными ненулевыми координатами - C++
Может кто помочь доделать програмку плиз.. Описать функцию Quarter(x,y) целого типа, определяющую номер координатной четверти, в...

найти номера координатных четвертей для трех точек с данными ненулевыми координатами - C++
Описать функцию Quarter(x, y) целого типа, определяющую номер ко-ординатной четверти, в которой находится точка с ненулевыми вещест-венными...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
08.01.2014, 00:05
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru