Тест HalfSpace to Point

Question

Я хотел бы узнать больше об очень определенном способе получения расстояния от точки до линии в 2D. Вот как это делается:

// Given an arbitrary point, and a normal vector 
// to a line along with a scalar offset 
distance = DotProduct(normal, point) - offset 

Я знаю, что это правда, потому что Эрин Катто использует этот метод в его исходном коде Box2D Lite. На this page программист упоминает уравнение:

distance = (V dot normal) - offset 

Этот единственный ресурс, я могу найти для такого расчета. обычный способ проверки пересечения полупространства с точкой состоит в том, чтобы выровнять вектор от рассматриваемой плоскости к вашей точке, а затем посмотреть, обращена ли она в сторону от или к нормали к этой плоскости, проверив знак (+ или -) полученного скаляра.

Это может быть нежелательным в приложениях реального времени, где поиск точки на плоскости (или 2D-линия в этом случае) может быть дорогостоящим, и у вас есть только нормальная эта линия вместе со смещением.

Итак, что это за «смещение» и как вы можете его вычислить? Что представляет собой это смещение? Из того, что я в настоящее время известно о моих собственных исследований моя догадка, что это с переменной из общего уравнения линии в 2D:

ax + by + c = 0 

Дополнительная информация: Erin Катто это вычислительное его смещение, как это в несколько мест (в контексте Oriented обнаружения столкновений Ограничительная Box), но я не понимаю математику здесь или что происходит:

offsetScalar = Dot(BoxPositionVector, normalVector) + BoxYHalfWidthScalar; 

Answer 1

полупространство в 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 является единичным вектором. Это из-за equivalence of definition of dot product to scalar projection; a/||a|| * p - проекция p на a. Следовательно, при определении гиперплоскостей при вычислении удобно нормировать a и масштаб c соответственно. Тогда c - это смещение, или эквивалентное расстояние от гиперплоскости до начала координат - мы должны отрегулировать для этого после проецирования на a.

TL; DR версия: offset = c/||a||, что означает offset = c, если a единичный вектор.

Answer 2

offset расстояние от линии до начала координат, если линия представлена ​​в виде:

ax + by + c = 0 

Тогда offset = c/sqrt(a*a+b*b).

Смотрите here для получения дополнительной информации.