Тест HalfSpace to Point
Я хотел бы узнать больше об очень конкретном способе получения расстояния от точки до линии в 2D. Вот как это делается:
// Given an arbitrary point, and a normal vector
// to a line along with a scalar offset
distance = DotProduct(normal, point) - offset
Я знаю, что это правда, потому что Эрин Катто использует этот метод в своем исходном коде Box2D Lite. На эта страница программист упоминает уравнение:
distance = (V dot normal) - offset
Это единственный ресурс, который я могу найти для такого вычисления. обычный способ проверки пересечения полупространства с точкой состоит в том, чтобы расставить точки вектора из рассматриваемой плоскости к вашей точке, а затем проверить, не направлен ли он в сторону от нормали к этой плоскости или по направлению к ней, проверив знак (+ или -) результирующий скаляр.
Это может быть нежелательно в приложениях реального времени, где нахождение точки на плоскости (или в данном случае двухмерной линии) может быть дорогостоящим, и у вас есть только нормаль к этой линии вместе со смещением.
Короче говоря, что это за «смещение» и как вы можете его вычислить? Что представляет собой это смещение? Из того, что я в настоящее время знаю о своих собственных исследованиях, я предпочитаю, что это переменная c из общего уравнения линии в 2D:
ax + by + c = 0
Дополнительная информация:
Эрин Катто вычисляет свое смещение таким образом в нескольких местах (в контексте обнаружения столкновений в Oriented Bounding Box), но я не понимаю здесь математики или того, что происходит:
offsetScalar = Dot(BoxPositionVector, normalVector) + BoxYHalfWidthScalar;
Решение
Полупространство в n размеры определяются однозначно по уравнению
a * x >= c
куда a а также x векторы длины n, * скалярное (точечное) произведение, и c это скаляр a вектор, ортогональный к гиперплоскости a * x = c, Как вы сказали, в двух измерениях это уравнение ax + by - c = 0все скаляры.
То, что вы сказали, совершенно верно; offset связано со значением этой константы c, Для любой точки p в гиперплоскости у вас будет a * p = c, Для любой точки в полупространстве у вас будет a * p >= c, Любая точка не в полупространстве удовлетворит a * p < c,
Для какой-то точки p, значение a * p - c также даст вам ортогональное расстояние от точки до гиперплоскости — если a это единичный вектор. Это из-за эквивалентность определения скалярного произведения скалярной проекции; a/||a|| * p это проекция p на a, Следовательно, при определении гиперплоскостей в вычислениях удобно нормализовать a и масштаб c соответственно. c затем смещение или, что эквивалентно, расстояние от гиперплоскости до начала координат — мы должны отрегулировать это после проецирования на a,
TL; версия DR: offset = c/||a||, что значит offset = c если a это единичный вектор.
Другие решения
offset это расстояние от линии до начала координат, если линия представлена в виде:
ax + by + c = 0
затем offset = c/sqrt(a*a+b*b).
Увидеть Вот для получения дополнительной информации.