Дан треугольник и точка лежащая в этом тоеугошльнике. Как доказать что точка лежит в треугольнике? (точка может перемещаться)
Дан треугольник и точка лежащая в этом тоеугошльнике. Как доказать что точка лежит в треугольнике? (точка может перемещаться)
Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.
15 февраля 2008 в 0:04
еще один способ, похож на предложенный Дмитрием Потаповым #12 (кстати там вычитаний больше, т.к. AB.x = A.x – B.x)
в общем – если точка лежит с одной стороны от каждой из сторон треугольника (например с левой при обходе против часовой стрелки), то точка лежит внутри треугольника. в общем, несколько умножений/вычитаний.
14 февраля 2008 в 22:00
Если не секрет, на чем основаны критерии оптимальности? =)
1-й предложенный способ выполняет в разы больше арифметических действий, чем описанный выше. 2-й вообще (почти?) не выполняется в целых числах.
И, кстати, кто есть Меньшиков и как называется его соответствующая публикация? =)
14 февраля 2008 в 21:05
мда… уж. Оптимальных есть три способа:
1) высчитать сумму площадей по формуле abs(x1*y2+x2*y3+x3*y1-y1*x2-x3*y2-y3*x1)/2 и сравнить ее с площадью треугольника. ИМХО лучший способ.
2) по векторам сумму углов – хороший способ, но есть возможность погрешности.
3) читайте Меньшикова! хорошо пишет
11 февраля 2008 в 10:01
if( (AB.x*AO.y-AB.y*AO.x)*(AC.x*AO.y-AC.y*AO.x) < 0 && (BA.x*BO.y-BA.y*BO.x)*(BC.x*BO.y-BC.y*BO.x) < 0 )
std::cout<<"Inside"<<std::endl;
else
std::cout<<"Outside"<<std::endl;
10 умножений, 4 вычитания, два сравнения.
просто вычисляется что точка лежит внутри двух углов треугольника – этого достаточно
11 февраля 2008 в 7:01
можно через векторы, в D3D есть функции для этого
D3DXVec3Cross
D3DXVec3Dot
11 февраля 2008 в 6:02
еще вариант разбить главный треугольник на 3 треугольника с этой точкой, и посчитать сумму их плащадей, если будет больше главного треугольника значит вне его. Если площадь меньше или равна – значит внутри.
У меня на вводной практике была эта задача. решал этим способом в экселе ^_^
11 февраля 2008 в 6:01
1. Вариант
а) Соединяем точку с вершинами треугольника.
б) Считаем углы.
в) Точка лежит внутри труегольника <=> сумма углов = 360
2. Вариант
а) Считаем барицентрические коордниаты x, y.
б) Точка дежит внутри треугольника <=>
0<=x and 0<=y and x+y <= 1. При выполнении хотя бы одного равенства точка лежит на сторонах треугольнка.
3. Вариант ( описан ранее вариант с площадями )
4. Вариант ( уравнения прямых )
Что касается реализации – самые эффективные методы – 2 и 4. Они не требуют никаких трудоемких функций типа arccos или sqrt.
Вообще их дохренища алгоритмов – если будет интересно – поищи в гугле – есть несколько сайтов с мат алгоритмами, в том числе и геометрическими. Кпримеру, algolist.ru.
Ах, да, как можно такое забыть ?!!!
5. Метод трассировки луча
10 февраля 2008 в 23:00
Большое спасибо!!!!!!
10 февраля 2008 в 22:05
желательно всё что возможно!!!!!
Я хочу знать алгоритм!
Здесь очень нужна математика!
Доказательства без линеек!
А как определить в каком из трёх треугольников лежит точка?
И как определить какую боковую прямую треугольника она пересекает?
10 февраля 2008 в 22:05
мне программу не надо писать ни в коем случае – я сам напишу – мне нужен чисто математический алгоритм!!!!!!
10 февраля 2008 в 22:05
Иван, насчет еще вариантов ответил здесь: //vkontakte.ru/board.php?act=topic&tid=1956... +)
10 февраля 2008 в 22:04
Не понял, нужна математическая выкладка или программное решение?
10 февраля 2008 в 22:04
Судя по группе где задали вопрос думаю что все-таки программное
. Но сомневаюсь что кто-то захочет писать программу за автора вопроса, только возможные алгоритмы напишут. Кстати, еще есть варианты как решить эту задачу?
10 февраля 2008 в 22:03
Не думая на ум приходит такой алгоритм…
Пусть треугольник ABC и точка O.
Известны координаты точек => находим уравнения прямых AB, BC, AC, AO, BO, CO. Далее находим пересечения прямых AO и BC, BO и AC, CO и AB. И проверяем что точки пересечения принадлежат отрезкам BC, AC и AB соответственно.