Guest
Новичок
|
    
Кто-то мне раньше, на каком-то форуме писал такие(ниже) способы определения принадлежности точки параллелограмму, не мог бы кто-нибудь сейчас пояснить по конкретней решение. Допустим для двух векторов(a,b) определяющих парал-м. Другие методы: трассировки луча, разбиение на треугольники - я знаю.
1) определение, принадлежит ли некоторая точка на плоскости заданному параллелограмму.
Если так, то решение, например, такое. Без огр. общ. положим, вершина параллелограмма
лежит в т. (0, 0) и одна из его сторон лежит на оси x. Если не так, трансляцией/поворотом
плоскости всегда можно достичь этого. Затем тривиальным преобразованием плоскости $y'=y$,
$x'=x+ay$, где $a=\tan\alpha$, $\alpha$ --- угол в вершине параллелограмма, лежащей в
начале координат, переводим параллелограмм в прямоугольник. Определить, принадлежит ли
точка прямоугольнику не составляет труда.
2) Быстрее будет метод, который по данным вершинам параллелограмма A,B,C
(таким, что AB и AC суть смежные стороны) и данной точке X будет проверять,
удовлетворяют ли числа u,v, являющиеся решениями системы u(B-A)+v(C-A)=X-A,
неравенствам 0<u,v<1, не вычисляя самих этих чисел (т.е. не выполняя делений).
Причём при целочисленных данных алгоритм имеет целочисленную же реализацию.
Выписать необходимые для проверки неравенства нетрудно.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 17 марта 2005 16:41 | IP
|
|
sms
Удален
|
Есть такое смешное решение:
вычислить комплексный интеграл по контуру параллелограма от 1\(z-z0).
Если нуль-не принадлежит, если 2pi*i-то принадлежит.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 18 марта 2005 23:03 | IP
|
|
dm
Удален
|
sms
 
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 18 марта 2005 23:05 | IP
|
|
Guest
Новичок
|
2 sms: а что такое z и z0 в этом случае?
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 19 марта 2005 11:11 | IP
|
|
dm
Удален
|
z_0 - Ваша точка, которую вы проверяете, принадлежит или нет.
z - аргумент, по которому берется интеграл.
Если есть вопросы по методам № 1, 2 из первого поста, то конкретизуйте, что именно не понятно.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 19 марта 2005 12:39 | IP
|
|
sms
Удален
|
Кстати, этот комплексный интеграл по параллелограмму (как и по любому многоугольнику) элементарно вычисляется и, следовательно, программируется. Он сводится к обычным интегралам по отрезкам прямых-сторонам.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 20 марта 2005 10:49 | IP
|
|
Guest
Новичок
|
2 dm:
по второму методу:
u(B-A)+v(C-A)=X-A
0<u
v<1
это система, надо вычислить u и v?
что-то я про комплексные интегралы ничего не знаю, сейчас теорию поищу...
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 20 марта 2005 12:18 | IP
|
|
dm
Удален
|
Цитата: Guest написал 20 марта 2005 11:18
по второму методу:
u(B-A)+v(C-A)=X-A
0<u
v<1
это система, надо вычислить u и v?
Прорешайте один раз эту линейную систему относительно u,v. Запишите неравенства 0<u,v<1 и тем самым получите условия на коэффициенты (домножьте на знаменатели). Теперь достаточно проверять эти условия.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 20 марта 2005 12:58 | IP
|
|
dm
Удален
|
что-то я про комплексные интегралы ничего не знаю, сейчас теорию поищу...
внешняя ссылка удалена
См. 4.4 "Интегральная формула Коши". (с. 72)
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 20 марта 2005 13:06 | IP
|
|
Guest
Новичок
|
2 dm
Спасибо
А первый способ, что я написал в начале, это не аффинные преобразования?
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 27 марта 2005 11:38 | IP
|
|
|
Форум
Принадлежность точки параллелограмму
