|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Polubasoff 2:5020/400 29 Oct 2001 04:34:37
To : Yurij Zabelyshynskij
Subject : 2 Задачи по геометpии и соpтиpовка
--------------------------------------------------------------------------------
Привет, Юрий!
27.10.01 23:08, Yurij Zabelyshynskij писал:
YZ>>> Так это практически одно и то же,
YZ>>> потому что для подсчета площади и определения полуплоскости
YZ>>> надо использовать одни и те же формулы.
OP>> Hет, не одно и то же.
OP>> Да. Формулы одни и те же. Hам интересно не значение
OP>> площади, а знак синуса угла.
Говоря: "это не одно и то же", я имею в виду, что это разные алгоритмы,
хоть в них и есть некоторые одинаковые формулы.
YZ> Если формулы одни и те же, то "нет никакой разницы, зачем платить
YZ> больше" :) ведь ты не узнаешь знак площади, пока ее не посчитаешь.
YZ> Все различие в том, что
Извини, пожалуйста, абсолютно не понял, о чём ты говоришь в этом абзаце.
Различие с чем?
YZ> вместо сравнения F1 > F2 ты сравниваешь F1-F2 >0.
Это да, виноват.
Мои претензии к программе, приведённой Ильёй Кантором, заключались в
том, что она иногда даёт неверный ответ, а иногда даже вылетает по делению
на 0. То, что она не очень эффективна - дело второе, хотя тоже немаловажно.
YZ>>> И все равно лучше проверять четность пересечений с
YZ>>>горизонтальным лучом.
OP>> Hет. Пожалуйста, приведи программу, покажи потактно, что
OP>> проверить четность пересечений с горизонтальным
OP>> лучом получается быстрее, чем
OP>> проверить знаки синусов трёх углов.
YZ> Программу я приводить не буду, потому что качества наших реализаций не
YZ> являются аргументами в споре об алгоритмах. Тем не менее свои доводы я
YZ> приведу.
Очень жаль. Hе видя программы, трудно судить об её правильности.
Аргументом в споре об алгоритмах является, в первую очередь, именно их
работоспособность.
Из приведённых тобой ниже цифр не понятно, корректно ли ты обрабатываешь
случаи, когда луч проходит через вершину треугольника. А именно это является
основной трудностью в алгоритме "чётности числа пересечений".
YZ> 1) Итак, рассмотрим случай, когда точка лежит в тр-ке.
YZ> Тебе надо посчитать 4 площади, для чего ты считаешь координаты 4
YZ> векторов (ab, bc, ap, bp) и 4 векторных произведения этих векторов,
Именно так, хотя "векторное произведение" - не совсем верный термин,
лучше называть его "смешанным".
Замечу только, что часто в таких задачах ориентация треугольника
известна заранее (обычно приводят все треугольники к одной ориентации),
и известно, что треугольник невырожденный. Так что остаётся посчитать
координаты 3 векторов и 3 "векторных" произведения этих векторов.
YZ> Мне надо посчитать координаты 3 векторов (ap, bp, cp), 2 векторных
YZ> произведения (для сторон тр-ка, пересекающих прямую) и 3 раза
YZ> определить (не)равенство знаков чисел, что для простоты я представлю
YZ> как сравнение с 0 произведения этих чисел.
Вот-вот! Та же ошибка, что и у Ильи. Из равенства 0 произведения двух
чисел вовсе не следует, что их знаки совпадают.
[арифметика и апелляция к MSDN скипнуты, извини]
YZ> 3) И наконец, весьма вероятно, что на самом деле человеку надо
YZ> определять положение точки относительно многоугольника с числом
YZ> сторон > 3. Для этого можно использовать и триангуляцию, но мой метод
YZ> в ней не нуждается,
Боже! Триангуляцию-то зачем?
YZ> а применительно к нетреугольникам (особенно выпуклым) он
YZ> будет гораздо лучше твоего, т.к. большинство сторон не пересекает
YZ> горизонтальную прямую и для них мне не понадобится считать векторные
YZ> произведения.
"Мой" и "твой" методы придуманы задолго до нашего рождения. :)
Мне непонятна суть спора. Я утверждаю, что для решения разных задач
существуют разные алгоритмы. Для треугольника - один, для невыпуклого
многоугольника - другой. Для выпуклого многоугольника пригодны оба.
В "моём" труднее ошибиться, так как он сводится к N+1 однотипному
вычислению "векторных" произведений. "Твой" более сложен, но использует
меньше умножений за счёт большего числа разветвлений алгоритма.
В зависимости от того, дороже на данном вычислительном устройстве
операция умножения или перехода, эффективнее может оказаться тот или другой
метод.
С уважением, Олег Полубасов.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
