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

@Taras_Z · Регистрация: 27.10.2010

Студворк — интернет-сервис помощи студентам

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

@salam · 01.01.2014, 19:34

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

@Taras_Z · 01.01.2014, 20:16 **[ТС]**

salam, точка также может лежать на стороне треугольника. Вершины треугольника - три искомые точки.

@AndrSlav · 01.01.2014, 21:34

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

@Taras_Z · 01.01.2014, 23:38 **[ТС]**

AndrSlav,

Сообщение от Taras_Z

Меня интересует самый быстрый алгоритм.

Как по мне это не самый быстрый алгоритм. У меня сделано все так же, но это работает очень долго и поэтому мне надо быстрый способ.

@IrineK · 02.01.2014, 07:55

Есть такая мысль:

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, "сдается" менее чем за секунду.

@IrineK · 02.01.2014, 08:08

А это - уже для 2000 точек.
Время выполнения: чуть больше 2 минут.

При этом, поскольку вы разрешили точке находиться на стороне, она приютилась в вершине треугольника )

@Taras_Z · 02.01.2014, 12:37 **[ТС]**

IrineK, Оно то так, но я делаю олимпиадную задачу, где надо уложиться в определенный тайм-лимит. В задаче, кроме этого алгоритма есть еще куча других, и вместе они будут выполняться достаточно долго. Мне просто нужно усовершенствовать это место.
Две минуты это очень долго. И точка может находиться на стороне, но не на вершине. Извиняюсь, что не указал этого раньше.

@salam · 02.01.2014, 12:50

Тогда бы уж дали ссылку на задачу.

@Taras_Z · 02.01.2014, 15:18 **[ТС]**

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

@IrineK · 02.01.2014, 18:08

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

@Taras_Z · 02.01.2014, 18:35 **[ТС]**

IrineK, 11 колонн это лишь пример.
Четких ограничений на количество колонн сожалению нет. Не надо за меня решать всю задачу. Она уже решена. Я просто хочу улучшить время ее выполнения. То что мне нужно, сказано в моем первом сообщении. Если вы не знаете лучшего алгоритма, то не надо писать то, что здесь было уже написано.

@IrineK · 02.01.2014, 19:12

Сообщение от Taras_Z

Она уже решена

Почему меня это должно останавливать? )

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

Сообщение от Taras_Z

Я просто хочу улучшить время ее выполнения

Т.е. не все тесты проходим. Тогда задача - не совсем решена

@Taras_Z · 02.01.2014, 19:26 **[ТС]**

IrineK, У меня нет точных ограничений. Также я не знаю, проходит ли мое решение по времени, потому что не могу проверить его. Вы можете решать эту задачу. Даже, если хотите, можете мне рассказать свою идею ррешения задачи. Просто все, что я хочу сейчас это усовершенствовать свой метод.

@IrineK · 02.01.2014, 19:31

ОК.
Тогда сориентируйте во времени, которое необходимо вашему коду, чтобы перемолоть пример.
И какое время хотелось бы получить?

@Taras_Z · 02.01.2014, 19:41 **[ТС]**

Сообщение от IrineK

И какое время хотелось бы получить?

Чем меньше тем лучше)
Пример выполняется за 0,003 с.
Но при увеличении колонн время существенно изменится.

@IrineK · 03.01.2014, 06:44

Основная идея альтернативного подхода такая.

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

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

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

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

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

В общем, Брезенхейм и "правильный" масштаб нам алсо в помощь )

@Taras_Z · 03.01.2014, 11:25 **[ТС]**

IrineK, Очень интересный метод!)
Спасибо)

@Taras_Z · 07.01.2014, 16:35 **[ТС]**

Никто не знает лучшего алгоритма?

@uhx · 07.01.2014, 16:42

Сообщение от Taras_Z

Четких ограничений на количество колонн сожалению нет.

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

Новые блоги и статьи Все статьи Все блоги /
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Programma_Boinc 01.01.2026 Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2

	Поиск трех ближайших точек к данной 01.01.2014, 19:29. Показов 4011. Ответов 21 Метки нет (Все метки) Есть массив точек, заданных координатами х и y. Нужно найти три ближайшие точки к данной, чтобы данная точка была в треугольнике, вершинами которого являются искомые точки. Меня интересует самый быстрый алгоритм. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	01.01.2014, 19:34
	люди, вы когда задачи придумываете, придумывайте их решаемыми... как я должен понять фразу "в треугольнике"? если данная точка лежит на одной из сторон? может ли треугольник вырождаться в прямую?... 0

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2
	01.01.2014, 20:16 [ТС]
	salam, точка также может лежать на стороне треугольника. Вершины треугольника - три искомые точки. 0

@AndrSlav 71 / 59 / 14 Регистрация: 20.12.2013 Сообщений: 721
	01.01.2014, 21:34
	На вскидку: Вычислить длины векторов из точки к точкам массива, а потом добавлять в выборку по очереди точки, соответствующие минимальным длинам векторов и сортировать их по описывающему контуру вместе с заданной точкой. Когда заданная точка не будет попадать в выборку- она внутри и последняя добавленная точка с соседними в выборке образуют искомый треугольник. 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	02.01.2014, 08:08
	А это - уже для 2000 точек. Время выполнения: чуть больше 2 минут. При этом, поскольку вы разрешили точке находиться на стороне, она приютилась в вершине треугольника ) Миниатюры 0

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2
	02.01.2014, 12:37 [ТС]
	IrineK, Оно то так, но я делаю олимпиадную задачу, где надо уложиться в определенный тайм-лимит. В задаче, кроме этого алгоритма есть еще куча других, и вместе они будут выполняться достаточно долго. Мне просто нужно усовершенствовать это место. Две минуты это очень долго. И точка может находиться на стороне, но не на вершине. Извиняюсь, что не указал этого раньше. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	02.01.2014, 12:50
	Тогда бы уж дали ссылку на задачу. 0

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2
	02.01.2014, 15:18 [ТС]
	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 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	02.01.2014, 18:08
	Две минуты для 2000 "колонн". Для тех 11, которые мы видим в примере - речь идет о долях миллисекунд. Кстати, в корректно поставленной спортивной задаче должно быть дано ограничение на их кво. Каковы границы этого числа? 0

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2
	02.01.2014, 18:35 [ТС]
	IrineK, 11 колонн это лишь пример. Четких ограничений на количество колонн сожалению нет. Не надо за меня решать всю задачу. Она уже решена. Я просто хочу улучшить время ее выполнения. То что мне нужно, сказано в моем первом сообщении. Если вы не знаете лучшего алгоритма, то не надо писать то, что здесь было уже написано. 0

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2
	02.01.2014, 19:26 [ТС]
	IrineK, У меня нет точных ограничений. Также я не знаю, проходит ли мое решение по времени, потому что не могу проверить его. Вы можете решать эту задачу. Даже, если хотите, можете мне рассказать свою идею ррешения задачи. Просто все, что я хочу сейчас это усовершенствовать свой метод. 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	02.01.2014, 19:31
	ОК. Тогда сориентируйте во времени, которое необходимо вашему коду, чтобы перемолоть пример. И какое время хотелось бы получить? 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	03.01.2014, 06:44
	Основная идея альтернативного подхода такая. Мне нужно пронести круглый сундук с определенным конечным радиусом, обходя круглые препятствия (fig1). В принципе, если я "сброшу" радиус сундука на эти препятствия, то задача сводится к прохождению пикселя, который может проходить и по границе препятствий (fig2 - там пиксель несколько преувеличен). Дальше - волновой алгоритм нам в помощь. Заходим со стен комнаты. Однако, волнует следующее. Обе картинки даны с зумом 50. Видим два пути, похожих на выходы: слева и внизу. В реале сундук проходит внизу впритык (окружности касаются, но не пересекаются). Слева по расчетам сундуку не хватает 0,015 пикселя, чтобы протиснуться. Но мы ставим на построение карты, а не на расчеты. Исходя из "0,015" зума 200 достаточно, чтобы увидеть, что окружности слева "наезжают", а не касаются (fig3 - слева, fig4 - внизу, зум 200). В общем, Брезенхейм и "правильный" масштаб нам алсо в помощь ) Миниатюры 0

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2
	03.01.2014, 11:25 [ТС]
	IrineK, Очень интересный метод!) Спасибо) 0

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2
	07.01.2014, 16:35 [ТС]
	Никто не знает лучшего алгоритма? 1