|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Polubasoff 2:5020/400 29 Oct 2001 11:35:05
To : Serge Kanilo
Subject : Точка в эпсилон окресности отрезка?
--------------------------------------------------------------------------------
Привет, Серж!
29.10.01 8:00, Serge Kanilo писал:
AB>>> Опсс... Координаты точек - целочисленные. e-окрестность -
AB>>> не превышает 15 единиц.
OP>> Тогда не забудь все промежуточные результаты считать в числах с
OP>> плавающей точкой с двойной точностью. Hе округляй промежуточные
OP>> результаты.
SK> Hу это уж слишком строго,
SK> все это можно посчитать и в целочисленной арифметике.
Понимаешь, Серж, я ведь пишу, исходя из собственных ошибок. Десяток лет
назад мы с коллегой, два придурка - математика, программировали один пакет,
в котором было много и геометрических задач. Мы старались писать максимально
эффективно и понятно (для нас), но совсем упустили из виду, что у машины -
своя математика, не такая, как у нас.
Глюки этого пакета уже надоели, и я сейчас решился его переписать.
Те алгоритмы уже давно забыты, бывший коллега мой уже давно живёт в Бостоне,
а исправлять ошибки, которые проявляются только раз в месяц гораздо труднее
проявляющихся постоянно. Формула, с виду, верна, а на каких-нибудь редких
данных глючит. Так что, обжегшись на молоке, дуем на воду. :)
Пусть A(0,0), B(0,0), C(0,0), e = 15.
SK> if(AB*AC<0) return AC*AC<e*e; // или <=, кто как определит границу
0 < 0? не выполняется.
SK> if(BA*BC<0) return BC*BC<e*e; // можно и if(AB*AC>AB*AB)
0 < 0? не выполняется.
SK> int ABxAC =(AB.x*AC.y-AB.y*AC.x); // векторное произведение
SK> return ABxAC*ABxAC<e*e*(AB*AB); // и никакого деления ;)
0 < 0? не выполняется. return false.
А правильный ответ - true.
SK> Скорее всего это что-то то вроде наведения мыши на отрезок на экране
SK> для фиксации наезда :) Так что числа должны быть совсем небольшими.
Скорее всего. :) Hо давай, посчитаем. Размером экрана в 2^9 - 2^10
пикселей уже никого не удивишь, так что квадрат векторного произведения
может достигать 2^36 - 2^40, что приведёт к целочисленному переполнению
и сильно удивит пользователя: выбираешь один отрезок, а подсвечивается
другой, совсем в другом углу.
OP>> else AC += AB; // иначе ближайшая точка - B
SK> Hе должно ли тут везде быть -=, вместо +=, (исходя из формулы сложения
SK> векторов AB+BC=AC)
Должно. Спасибо.
С уважением, Олег Полубасов.
PS: Вот, в соседнем треде "[* - гео] - середина дуги" ты привёл метод,
который, вроде бы, с математической точки зрения, верен. Hо алгоритм явно
не выписал. А вдруг машинная точка зрения окажется другой? :)
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
