Заочная физико-техническая школа Московского физико-технического института         
Задачи и решения
  Вернуться к сообщениям форума  |  Ответить на сообщение 
Использовать векторное произведение
Сообщение прислал(а): Гега (CELERON)
Дата написания: 10 февраля 2004г. 19:00:10
Второй способ , пускай и более програмистский -
использовать веторное произведение.
Если один вектор получается из другого поворотом против часовой
стрелки - то векторное произведение положительное ,
если поворотом по - то произведение отрицательное.
Так , если некоторый вектор v2 лежит между двумя векторами
v1 и v3 , то векторные произведения v1*v2 и v1*v3 должны
быть разных знаков ( одно положительное - второе
отрицательное , но не равно нулю ).
Так можно проверить лежит ли точка во "внутренней" части
двух пересекающихся прямых. ( точнее лежит
ли точка между прямыми a2 и a3 , которые задаюстся векторами
v1 и v3 соответственно ).

Для треугольника.
Пускай известны координаты его точек: (x1,y1) (x2,y2) (x3,y3).
Если точка лежит внутри угла <( (x1,y1) , (x2,y2) )

( опять же под углом здесь понимается внутренняя часть
между прямыми , содержащими векторы <((x1,y1),(x2,y2).
Это вроде как прямую содержащую один вектор мы поворачиваем,
чтобы получить прямую содержащуб второй вектор ( при этом
таким образом , чтобы замётанный угол получился наименньшим))

и одновременно лежит внутри угла <( (x2,y2) , (x3,y3) ) ,
то очевидно она лежит внутри треугольника. Нарисуйте картинку,
это и вправду очевидно.

То есть надо проверить 4 векторных произведения.

Векторное произведение для двух векторов (x1,y1) и (x2,y2)
задаётся как

x1*y2-x2*y1 ( произведения тут скалярные ) (*)

Замечу , что вектор задаётся только двумя числами,
при этом считается , чтовектор начинается в начале координат.

Итого проверка следующая:
Переносим начало координат в точку (x3,y3) , чтобы можно было
пользоваться векторным произведением (*)
Координаты первого вектора:
(x1-x3,y1-y3)
второго вектора:
(x2-x3,y2-y3).
Координаты точки ( m1 , m2 )
Тогда произведения
m1*(y1-y3) - (x1-x3)*m2 и
m1*(y2-y3) - (x2-x3)*m2 должны быть разных знаков.

Анологично для второй пары векторов:
Переносим начало координат в точку (x1,y1)
Тогда координаты векторов (x2-x1,y2-y1) и (x3-x1,y3-y1).
Координаты точки (m1,m2)
И произведения:
m1*(y2-y1) - (x2-x1)*m2
m1*(y3-y1) - (x3-x1)*m2
должны быть разных знаков.
и всё =)

И считать ничего не надо , и идея простая.
А программить это одно большое счастье !!!
Вычислительная геометрия - сюжет огромнейший.
Если кого это тема заинтересует - можно пообщаться =)

P.S всем программерам большой привет из Риги =)







Сообщения в данном потоке
 Про точку и треугольник (4319) - Анка (ttk-vlan705-vcdvo.ascnet.ru) [09.02.04 04:13]
 Использовать векторное произведение (4333) - Гега (CELERON) [10.02.04 19:00]
 Ответ и замечания. (4398) -  Sergey A.Belyaev  (shine.4ka.mipt.ru) [12.02.04 14:49]
 Re: Использовать векторное произведение (3842) - Анка (ttk-vlan705-vcdvo.ascnet.ru) [11.02.04 04:54]
 Уравнение треугольника (4184) -  Sergey A.Belyaev  (shine.4ka.mipt.ru) [10.02.04 11:40]
 Re: Уравнение треугольника (4268) - Гега (CELERON) [10.02.04 19:04]
 Ответ (4173) -  Sergey A.Belyaev  (shine.4ka.mipt.ru) [11.02.04 00:59]
 Странно (4031) - Анка (ttk-vlan705-vcdvo.ascnet.ru) [11.02.04 04:29]
 Ответ Анке (3910) -  Sergey A.Belyaev  (shine.4ka.mipt.ru) [12.02.04 14:33]
 Спасиб. Теперь все понятно (пусто) (4057) - Анка (ttk-vlan705-vcdvo.ascnet.ru) [13.02.04 09:42]
 Например, для прямой y=ax+b число можно получить, (3908) - Далекий (mail.rgi.com) [11.02.04 05:35]
 Хорошая мысль чуть опоздала. О том, что (4002) - Далекий (mail.rgi.com) [11.02.04 06:54]

Ответить на сообщение
При публикации вопросов, связанных с задачами, приводите, пожалуйста, ИХ УСЛОВИЯ.
Тема сообщения:
Ваше имя:
Ваш E-Mail:
Текст сообщения:
[Добавить формулу]
Сотрудник ЗФТШ:   
  

© 2002-2019, ЗФТШ МФТИ
    Пожелания вебмастеру
ЛЕКТОРИЙ | ПРОГРАММЫ ОБУЧЕНИЯ | МЕТОДИСТЫ | ШКОЛЬНИКАМ
Разработка 100ляров