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

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

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

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

01.01.2014, 19:29. Просмотров 988. Ответов 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++
Ввести числа , которые являются значениями коор-динат трех точек на плоскости. Определить, образуют ли они треуголь-ник (точки не лежат на...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
01.01.2014, 19:34 #2
люди, вы когда задачи придумываете, придумывайте их решаемыми... как я должен понять фразу "в треугольнике"? если данная точка лежит на одной из сторон? может ли треугольник вырождаться в прямую?...
0
Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
01.01.2014, 20:16  [ТС] #3
salam, точка также может лежать на стороне треугольника. Вершины треугольника - три искомые точки.
0
AndrSlav
44 / 44 / 6
Регистрация: 20.12.2013
Сообщений: 259
01.01.2014, 21:34 #4
На вскидку:
Вычислить длины векторов из точки к точкам массива, а потом добавлять в выборку по очереди точки, соответствующие минимальным длинам векторов и сортировать их по описывающему контуру вместе с заданной точкой. Когда заданная точка не будет попадать в выборку- она внутри и последняя добавленная точка с соседними в выборке образуют искомый треугольник.
0
Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
01.01.2014, 23:38  [ТС] #5
AndrSlav,
Цитата Сообщение от Taras_Z Посмотреть сообщение
Меня интересует самый быстрый алгоритм.
Как по мне это не самый быстрый алгоритм. У меня сделано все так же, но это работает очень долго и поэтому мне надо быстрый способ.
0
IrineK
Заблокирован
02.01.2014, 07:55 #6
Есть такая мысль:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
//точка С в треугольнике из трех других точек р1, р2, р3
//если параметры одинакового знака, то точка внутри треугольника
//если какой-то параметр = 0, то точка лежит на стороне
//иначе - точка вне треугольника
int IsInTriangle (TPoint *p1, TPoint *p2, TPoint *p3, TPoint *c)
{   int param1 = (p1->X - c->X)*(p2->Y - p1->Y) - (p2->X - p1->X)*(p1->Y - c->Y);
    int param2 = (p2->X - c->X)*(p3->Y - p2->Y) - (p3->X - p2->X)*(p2->Y - c->Y);
    int param3 = (p3->X - c->X)*(p1->Y - p3->Y) - (p1->X - p3->X)*(p3->Y - c->Y);
 
    if (param1*param2 >= 0 && param2*param3 >= 0)
        return 1;
    return 0;
}
Если воспользоваться, то массив из 200 точек, перебранных по три by brute force, "сдается" менее чем за секунду.
0
Миниатюры
Поиск трех ближайших точек к данной  
IrineK
Заблокирован
02.01.2014, 08:08 #7
А это - уже для 2000 точек.
Время выполнения: чуть больше 2 минут.

При этом, поскольку вы разрешили точке находиться на стороне, она приютилась в вершине треугольника )
0
Миниатюры
Поиск трех ближайших точек к данной  
Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
02.01.2014, 12:37  [ТС] #8
IrineK, Оно то так, но я делаю олимпиадную задачу, где надо уложиться в определенный тайм-лимит. В задаче, кроме этого алгоритма есть еще куча других, и вместе они будут выполняться достаточно долго. Мне просто нужно усовершенствовать это место.
Две минуты это очень долго. И точка может находиться на стороне, но не на вершине. Извиняюсь, что не указал этого раньше.
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
02.01.2014, 12:50 #9
Тогда бы уж дали ссылку на задачу.
0
Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
02.01.2014, 15:18  [ТС] #10
salam, Ссылку дать не могу, так как такой не существует.
Могу объяснить суть задачи.
В комнате есть большой круглый (синий ) сундук посреди комнаты.
Надо перенести сундук из комнаты - но мешают колонны ( оранжевые ) .
Нужно найти , через какую стену возможно вынести сундук ( левая, правая , верхняя , нижняя) . (Если это возможно).
Переносить сундук через угол нельзя.
В файле задается размер комнаты ( XY ) , координаты и диаметр сундука , количество колонн n , их координаты и диаметр.
Выводить 0 , если сундук вынести из комнаты нельзя , или указывать номер стены , через которую можно вынести ящик ( все варианты ) .
Если нижняя стена - 1
Верхняя - 2
Левая - 3
Правая - 4
Пример файла:
Кликните здесь для просмотра всего текста
31 14
17 8 6
11
2 3 3
5 1 2
11 1 2
18 1 2
26 1 2
8 9 2
1 12 2
13 12 2
21 11 3
25 8 2
29 12 2

Ответ: 1
0
Миниатюры
Поиск трех ближайших точек к данной  
IrineK
Заблокирован
02.01.2014, 18:08 #11
Две минуты для 2000 "колонн".
Для тех 11, которые мы видим в примере - речь идет о долях миллисекунд.
Кстати, в корректно поставленной спортивной задаче должно быть дано ограничение на их кво.
Каковы границы этого числа?
0
Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
02.01.2014, 18:35  [ТС] #12
IrineK, 11 колонн это лишь пример.
Четких ограничений на количество колонн сожалению нет. Не надо за меня решать всю задачу. Она уже решена. Я просто хочу улучшить время ее выполнения. То что мне нужно, сказано в моем первом сообщении. Если вы не знаете лучшего алгоритма, то не надо писать то, что здесь было уже написано.
0
IrineK
Заблокирован
02.01.2014, 19:12 #13
Цитата Сообщение от Taras_Z Посмотреть сообщение
Она уже решена
Почему меня это должно останавливать? )

Все-таки хочется знать порядок величин, в частности заинтересовали ограничения на площадь комнаты: каждая стена длиной до сотен, до тысяч? Думаю, эдакий bitmap помещения может сильно помочь.

Цитата Сообщение от Taras_Z Посмотреть сообщение
Я просто хочу улучшить время ее выполнения
Т.е. не все тесты проходим. Тогда задача - не совсем решена
0
Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
02.01.2014, 19:26  [ТС] #14
IrineK, У меня нет точных ограничений. Также я не знаю, проходит ли мое решение по времени, потому что не могу проверить его. Вы можете решать эту задачу. Даже, если хотите, можете мне рассказать свою идею ррешения задачи. Просто все, что я хочу сейчас это усовершенствовать свой ​​метод.
0
IrineK
Заблокирован
02.01.2014, 19:31 #15
ОК.
Тогда сориентируйте во времени, которое необходимо вашему коду, чтобы перемолоть пример.
И какое время хотелось бы получить?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.01.2014, 19:31
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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