|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yurij Zabelyshynskij 2:5020/400 30 Oct 2001 00:35:36
To : Oleg Polubasoff
Subject : Re: 2 Задачи по геометpии и соpтиpовка
--------------------------------------------------------------------------------
Hi, Oleg.
Oleg Polubasoff wrote
OP>Из приведённых тобой ниже цифр не понятно, корректно ли
OP> ты обрабатываешь случаи, когда луч проходит через вершину
OP> треугольника. А именно это является основной трудностью
OP> в алгоритме "чётности числа пересечений".
Для таких случаев нет никаких трудностей: есть четкие правила, когда
считать пересечения, когда - нет. Правда, это требует дополнительных
сравнений. Я просто не включил этот вариант в письмо, т.к. все равно
рассматривалась только 1 конфигурация. Аналогично я не рассматривал
случай точки на стороне, для которого у тебя требуются дополнительные
операции, а у меня - нет.
YZ>> Тебе надо посчитать 4 площади, для чего ты считаешь координаты 4
YZ>> векторов (ab, bc, ap, bp) и 4 векторных произведения этих
YZ>>векторов,
OP> Именно так, хотя "векторное произведение" - не совсем верный
OP> термин, лучше называть его "смешанным".
В формуле для площади (и ориентации) используется именно векторное
произведение. Смешанное используется в формуле для объема. Hа всякий
случай определение: смешанное произведение 3 векторов - это скалярное
произведение 1-го на векторное произведение 2-го и 3-го.
YZ>> определить (не)равенство знаков чисел, что для простоты я
YZ>> представлю как сравнение с 0 произведения этих чисел.
OP> Вот-вот! Та же ошибка, что и у Ильи. Из равенства 0 произ-
OP> ведения двух чисел вовсе не следует, что их знаки совпадают.
Конечно. Hо ошибки тут нет. Совпадение знаков следует из того, что
произведение >0. Если оно <= 0, то нужна дальнейшая проверка. Впрочем,
я уже написал про это выше.
YZ>> 3) И наконец, весьма вероятно, что на самом деле человеку надо
YZ>> определять положение точки относительно многоугольника с числом
YZ>> сторон > 3. Для этого можно использовать и триангуляцию,
OP> Боже! Триангуляцию-то зачем?
Есть многое на свете, друг Горацио... Когда я искал авторитетные
источники, нашел много интересного. Почитай здесь:
http://www.acm.org/pubs/tog/editors/erich/ptinpoly/
OP> Мне непонятна суть спора. Я утверждаю, что для решения разных
OP> задач существуют разные алгоритмы. [...] В "моём" труднее
OP> ошибиться, так как он сводится к N+1 однотипному
OP> вычислению "векторных" произведений. "Твой" более сложен, но
OP> использует меньше умножений за счёт большего числа
OP> разветвлений алгоритма. В зависимости от того, дороже на
OP> данном вычислительном устройстве операция умножения или
OP> перехода, эффективнее может оказаться тот или другой метод.
Для треугольника полностью согласен. Для многоугольника не полностью.
Hо все равно пора этот спор прекращать, потому что друг друга мы,
видимо, не переспорим, а спрашивавший получил достаточно методов и
выберет сам.
OP> С уважением, Олег Полубасов.
Взаимно, Yura.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
