|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yurij Zabelyshynskij 2:5020/400 28 Oct 2001 00:08:57
To : Oleg Polubasoff
Subject : Re: 2 Задачи по геометpии и соpтиpовка
--------------------------------------------------------------------------------
Hi, Oleg.
Oleg Polubasoff wrote
YZ>> Так это практически одно и то же,
YZ>> потому что для подсчета площади и определения полуплоскости
YZ>> надо использовать одни и те же формулы.
OP> Hет, не одно и то же.
OP> Да. Формулы одни и те же. Hам интересно не значение
OP> площади, а знак синуса угла.
Если формулы одни и те же, то "нет никакой разницы, зачем платить
больше" :) ведь ты не узнаешь знак площади, пока ее не посчитаешь. Все
различие в том, что вместо сравнения F1 > F2 ты сравниваешь F1-F2 >0.
Причем тоже 3 раза. Только ориентацию исходного тр-ка ты считаешь 1
раз, а IK - 3 раза, но это, по-моему, очевидная оптимизация.
YZ>> И все равно лучше проверять четность пересечений с
YZ>>горизонтальным лучом.
OP> Hет. Пожалуйста, приведи программу, покажи потактно, что
OP> проверить четность пересечений с горизонтальным
OP> лучом получается быстрее, чем
OP> проверить знаки синусов трёх углов.
Программу я приводить не буду, потому что качества наших реализаций не
являются аргументами в споре об алгоритмах. Тем не менее свои доводы я
приведу.
1) Итак, рассмотрим случай, когда точка лежит в тр-ке.
Тебе надо посчитать 4 площади, для чего ты считаешь координаты 4
векторов (ab, bc, ap, bp) и 4 векторных произведения этих векторов,
т.е. 8 вычитаний и еще 8 умножений и 4 вычитания, итого 8 умножений и
12 вычитаний. Кроме того, еще 4 сравнения и 2 "and".
Мне надо посчитать координаты 3 векторов (ap, bp, cp), 2 векторных
произведения (для сторон тр-ка, пересекающих прямую) и 3 раза
определить (не)равенство знаков чисел, что для простоты я представлю
как сравнение с 0 произведения этих чисел. Итого 7 умножений, 8
вычитаний и 5 сравнений. Еще мне надо 1 раз инвертировать булевский
result и 2 раза применить "and" (для пересекающих прямую сторон: между
сравнениями знаков ординат и знаков площадей).
Итак, в этом случае, (если считать сложение и вычитание равнозначными)
у меня 1 лишнее сравнение и 1 "not", а у тебя - 1 умножение и 4
сложения.
Для полного анализа, конечно, надо рассмотреть и другие случаи
расположения точки, т.к. тогда некоторые вычисления и в твоем, и в
моем алгоритмах можно пропускать, но тут нам понадобится считать
вероятности конфигураций, для чего надо точно знать параметры тр-ка и
окружающей области. Я такой анализ проводить не берусь, хотя, если его
сделаешь ты, охотно почитаю.
2) Еще один метод в споре - привести авторитетное мнение. Я привел
пример из MSDN, возможно, ты сумеешь привлечь более авторитетный
источник. Ждем-с.
3) И наконец, весьма вероятно, что на самом деле человеку надо
определять положение точки относительно многоугольника с числом сторон
> 3. Для этого можно использовать и триангуляцию, но мой метод в ней
не нуждается, а применительно к нетреугольникам (особенно выпуклым) он
будет гораздо лучше твоего, т.к. большинство сторон не пересекает
горизонтальную прямую и для них мне не понадобится считать векторные
произведения.
WBR, Yura.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
