Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        Принадлежность точки параллелограмму
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 ]
Модераторы: Roman Osipov, RKI, attention, paradise
  

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

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 ]

Форум работает на скрипте © Ikonboard.com