Какой самый быстрый алгоритм для нахождения точки из набора точек, ближайшего к прямой?

Question

у меня есть:
- набор очков известного размера (в моем случае всего 6 очков)
- линия, характеризуемая x = s + t * r, где x, s и r - трехмерные векторы

Мне нужно найти точку, ближайшую к данной линии. Фактическое расстояние не имеет значения для меня.

Я взглянул на несколько разных вопросов, которые кажутся связанными (включая этот один), и знаю, как решить эту проблему на бумаге из моих уроков математики в старшей школе. Но я не могу найти решение без расчета каждого расстояния, и я уверен, что должен быть лучший / более быстрый путь. Производительность абсолютно необходима в моем приложении.

Еще одна вещь: все числа являются целыми числами (координаты точек и элементов векторов s и r). Опять же, из соображений производительности я хотел бы свести к минимуму математические вычисления с плавающей точкой.

Answer 1

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

Так как вам не важно фактическое расстояние, мы можем упростить вычисление расстояния до точки.Точное расстояние вычисляется как ( source ):

d^2 = |r⨯(p-s)|^2 / |r|^2

, где ⨯ - это перекрестное произведение, а |r|^2 - это квадрат длины вектора r.Поскольку |r|^2 является постоянным для всех точек, мы можем исключить его из вычисления расстояния без изменения результата:

d^2 = |r⨯(p-s)|^2

Сравните приблизительные квадратные расстояния и соблюдайте минимум.Преимущество этой формулы в том, что вы можете делать все с целыми числами, поскольку вы упомянули, что все координаты являются целыми числами.

Answer 2

Боюсь, что вам не удастся вычислить менее 6 расстояний (если бы вы могли, по крайней мере, одна точка была бы опущена - включая ближайшую).

Посмотрите, получится ли этосмысл предварительной обработки: линия фиксирована и точки меняются?Подумайте о повороте координат, чтобы сделать линию горизонтальной.

Поскольку точек немного, сомнительно, что это ваше узкое место. Измерьте , где находятся горячие точки, перепроектируйте алгоритмы / представление данных, оживите оптимизацию компилятора, скомпилируйте в сборку и запустите это.Строго в таком порядке.

«Написание эффективных программ» Джона Бентли (к сожалению, давно вышедших из печати) и «Программирование жемчужин» (2-е издание) полны советов по практическому программированию.