C ++, точка и линия в 2D устойчивы к ошибкам округления и позиции

Question

Линия определяется двумя конечными точками P1 [x1, y1], P2 [x2, y2].Пусть Q [xq, yq] - проверенная точка.Обе координаты двойные.

Разности:

dx1 = x2 - x1
dy1 = y2 - y1
dx2 = xq - x1
dy2 = yq - y1

Нормы

double n1_sq = sqrt(dx1 * dx1 + dy1 * dy1);
double n2_sq = sqrt(dx2 * dx2 + dy2 * dy2);

Мое предположение: тест с нормализованными векторами менее чувствителен к ошибкам округления

double test = (dx1 / n1_sq  )  * (dy2 / n2_sq) - ( dx2 / n2_sq ) * ( dy1 / n1_sq );

чем

double test = dx1 * dy2 - dx2 * dy1;

Проблема возникает в следующих случаях:

A) Проверенная точка - это Q на линии

Q = [0.5(x1 + x2), 0.5(y1 + y2)]

Во многихв случаях, результат не ноль, а

test >> 0

B) Неправильная конфигурация линии / проверенной точки

Случай 1) длинный сегмент:

Переместим проверенную точку в начальную точку, dist (Q, | p1, p2 |) = 7e-4

P1 = [0, 0]
P2 = [1000000000.00001, 1000000000.00001]
Q = [0.0,0.001] 

Нормализованный тест: 0,7 Ненормализованный тест: 1.0e + 6

Случай 2) длинный сегмент:

Переместим проверенную точку в конечную точку dist (Q, | p1, p2 |) = 7e-4

P1 = [0, 0]
P2 = [1000000000.00001, 1000000000.00001]
Q = [1000000000.0, 1000000000.001] 

Нормализованный тест: 5.0e-13 Ненормализованный тест: 1.1 e + 6

Случай 3) короткий сегмент:

Переместим тестируемую точку кначальная точка, dist (Q, | p1, p2 |) = 7e-4

P1 = [0, 0]
P2 = [0.00001, 0.00001]
Q = [0.0,0.001] 

Нормализованный тест: 0,7 Ненормализованный тест: 1.0e-8

Результаты:

A) Нормализованный тест для длинных сегментов менее надежен.Случай 2 можно рассматривать как нулевой механизм со следующим решением: Q включен | p1, p2 | ...

B) Для коротких сегментов ситуация обратная, ненормализованный тест дает нулевой уровень оборудования.

Но результат обоих тестов не является постоянным, и полученное значение не приносит никакой информации о реальном расстоянии точки Q от линии | p1, p2 |.Использование порога в обоих тестах не дает правильного результата ... И значение порога не может быть определено раньше ..

Что мне делать?

Мое решение состоит в том, чтобы заменить оба теста новым тестом: проверить расстояние от точки Q до линии P1, p2 и использовать некоторый порог eps.Точка Q с

dist (Q,|P1,P2|) < eps,  (for example 1e-10) 

будет размещена на линии P1, P2 ... Результат теста не зависит от конфигурации точек (т.е. если мы переместим контрольную точку Q вдоль сегмента P1,P2)

Кто-нибудь использует лучший тест или имеет другое решение этой проблемы?

Answer 1

Вы используете продукт клина (который в 2d является определяющим), чтобы найти ваше расстояние.Я полагаю, проблема в том, что вы можете вычитать аналогичные величины, чтобы ваш результат был преодолен с ошибкой усечения.Попробуйте вместо этого использовать точечное произведение.d = d1.d2 / | d1 |.

Answer 2

Я не понимаю ваш тест. Похоже, он не включает координаты Q вообще. Кроме того, для двух значений u и v норма вычисляется с минимальным округлением как M * sqrt(1 + m / M), где M = max(|u|, |v|) и m = min(|u|, |v|). Что касается функции dist, это лучший подход, хотя вы можете сделать порог функцией длины отрезка линии. Это действительно зависит от вашего приложения.