Привет всем, у меня на координатной плоскости есть множество точек,

я выбираю одну из них и хочу найти ближайшую, можно ли это сделать быстрее, чем О(n)?

2 ответов

12 просмотров

Если точки фиксированы, и нужно часто получать ближайшую точку из множества, то можно единожды рассчитать lookup таблицу для всех точек и просто смотреть туда. Если точки постоянно разные, то, наверное, никак (но можно оптимизировать, чтобы проверять не все точки). Если меняется не слишком много точек, то можно делать амортизации таблицы, меняя её, например

Такую штуку делали Entagma (уроки по Houdini). Секунд 20-30 посмотрите, сразу поймете о чем речь. https://www.youtube.com/watch?v=uhYe-Cs46hs Сам экспериментировал и выходили кастомные варианты. Если заточиться и перевести с VEX -> GDScript / не уверен что есть функция аналог PCFind

Похожие вопросы

Обсуждают сегодня

Но, может, есть уже проверенная? Наши требования такие: 1. Сообщения должны приходить из Инста в CRM оду 2. Должна быть возможность подключить несколько экаунтов Инстаграм. Р...
Alexander Sharoiko MSE / Александр Шаройко
13
Как думаете через какой сервис они верифицируют?
inc.
5
Это может быть все-таки не флудвейт? у меня ботфазер принимает изменения и отображает даже что они изменились, на видео видно что он прислал якобы уже измененное описание, н...
OVERLINK
13
Добрый день! Подскажите, каким сборщиком фронта для OctoberCMS кто пользуется? Я имею ввиду сборщики, с которыми можно работать по стандартной схеме директорий октября. Я испо...
Николай Афанасенко
2
Вопрос: Здравствуйте! У меня возникла проблема с использованием плагина Mall в OctoberCMS. Я использую все файлы и компоненты в их исходном виде, без изменений. Однако на стр...
𐩱𐩪𐩣𐩱𐩲𐩺𐩡
8
Я правильно понимаю что нет способов получить список ожидающих заявок на вступление в группу с помощью бота из mtproto?
Шамиль Прилов
9
На чём в основном щас пишут мини апы? Vuejs?
Goot evening Not everyone
6
Добрый день. Мне посоветовали обратиться к вам в чат за помощью. Ситуация описана на скрине. Как мне сказали, мне на бота навесили флудвейт. Есть ли возможность снять его ра...
OVERLINK
7
🙋 Ребята, всем привет. Поправил задачу: Нужно каждому новому сообщению (1 раз по каждому юзеру) в чате прибавлять снизу кнопку с предложением подписаться на канал. Как добавит...
Alexander
1
Просто по очереди выпиливаешь на ручной маппинг? По методу за раз
Andrii Kurdiumov
7
Карта сайта