12 / 12 / 3
Регистрация: 09.05.2010
Сообщений: 384
|
|
1 | |
Как проверить принадлежит ли точка треугольнику?13.06.2010, 02:17. Показов 258255. Ответов 19
Метки нет (Все метки)
0
|
13.06.2010, 02:17 | |
Ответы с готовыми решениями:
19
Как проверить, принадлежит ли точка треугольнику Проверить, принадлежит ли точка M(x,y) треугольнику с заданными вершинами Проверить принадлежит ли точка плоскости с координатами (x,y) треугольнику с заданными вершинами Принадлежит ли точка треугольнику |
4 / 4 / 2
Регистрация: 17.04.2010
Сообщений: 55
|
|
13.06.2010, 02:56 | 2 |
пусть твоя точка имеет координаты (х,у), а вершины треугольника - (х1,у1), (х2,у2), (х3,у3).
точка будет принадлежать треугольнику, если будет принадлежать одновременно трем полуплоскостям, пересечение которых и есть треугольник. точка с координатами (х,у) принадлежит полуплоскости, когда находится по одну из сторон некоторой прямой, а именно y-(kx+b)>=0 , где k, b - параметры данной прямой. далее нужно найти уравнения прямых, которые содержат стороны треугольника, составить 3 неравенства, и решить систему из этих 3х неравенств. составить уравнение прямых можно с помощью уравнения прямой, проходящей через 2 точки на плоскости
1
|
2836 / 1645 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
|
13.06.2010, 14:33 | 3 |
Сообщение было отмечено как решение
Решение
Уже было - https://www.cyberforum.ru/showthread.php?t=8234.
Математическая часть - векторное и псевдоскалярное произведения. Реализация - считаются произведения (1, 2, 3 - вершины треугольника, 0 - точка): (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0) (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0) (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0) Если они одинакового знака, то точка внутри треугольника, если что-то из этого - ноль, то точка лежит на стороне, иначе точка вне треугольника.
23
|
12 / 12 / 3
Регистрация: 09.05.2010
Сообщений: 384
|
|
13.06.2010, 22:18 [ТС] | 4 |
junkier, Somebody - спасибо...
1
|
42 / 42 / 3
Регистрация: 11.04.2010
Сообщений: 177
|
|||||||||||
22.06.2010, 22:15 | 5 | ||||||||||
вот решения по данной формуле выше
namespace zadacha_2
вот ещо одно решения етой задачи
3
|
12 / 12 / 2
Регистрация: 09.03.2011
Сообщений: 38
|
|
09.03.2011, 23:26 | 6 |
Хотел бы прокоментировать сообщение последнего автора. Первое решение, на мой взгляд в разы лучше второго по одной простой причине. Известно, что квадратный корень есть очень медленная функция. Решение 2 прокатит, если нужно проверить один треугольник, и все. Но если мы программируем графику, к примеру, или что-нибудь еще, где нам это надо считать на каждом кадре и/или для каждого пикселя, то есть очень много раз, то оно совершенно неприемлимо. Тут скорость не спасет даже замена на Fast Inverse Square Root(см. Википедия), хотя она же и ужасно снизит нам точность.
Мораль, господа! избегайте sqrt(), sin() и cos() в вашем коде. А что касается последних, учтите, что синус и косинус сопроцессор считает в один присест и просто пихает их на стек один поверх другого. компилляторы(даже VS) не умеют оптимизировать используя это. так что иногда имеет смысл(особенно в графике, при рассчете матриц поворота) переписать эти куски кода на АСМе... хотя если вы пишите на C#... фу, классический С форевер! =)
2
|
Українець
424 / 318 / 16
Регистрация: 26.09.2009
Сообщений: 844
|
|
10.03.2011, 04:41 | 7 |
.спасибо
0
|
294 / 206 / 2
Регистрация: 20.02.2011
Сообщений: 551
|
|
10.03.2011, 14:01 | 8 |
[QUOTE=cgsg11;1435009]Хотел бы прокоментировать сообщение последнего автора.
С другой стороны, задача-то простая. Не элементарная, но достаточно простая. Somebody уже показал, что все решается без особого выпендрежа. Ну, и нафиг оно, усложнение!
0
|
Почетный модератор
64303 / 47600 / 32742
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
10.03.2011, 14:11 | 9 |
Мне кажется аналогично по сложности решение через площади треугольников, естественно не по Герону...
1
|
12 / 12 / 2
Регистрация: 09.03.2011
Сообщений: 38
|
||||||
11.03.2011, 01:26 | 10 | |||||
Сообщение было отмечено как решение
Решение
Господа. Должен заметить, что код первого решения вроде как неверен... Я не знаю, проверял ли ПроСтоСанек свое решение, но он в цикле явно "гадит" мимо массива (из-за ++i вместо i++)
Выкладываю код моего решения, которое проверено и работает (косметические изменения плюс исправленая ошибка, для тех, кто обожает копипасту с форумов =) ).
3
|
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
|
|
11.03.2011, 19:55 | 11 |
0
|
12 / 12 / 2
Регистрация: 09.03.2011
Сообщений: 38
|
|
12.03.2011, 00:07 | 12 |
Я подозревал, что облажаюсь так. )
Ошибку понял:
0
|
1 / 1 / 0
Регистрация: 27.02.2011
Сообщений: 25
|
|
11.05.2011, 21:40 | 13 |
Спасибо за методы. Очень пригодились!
0
|
7 / 7 / 3
Регистрация: 11.01.2011
Сообщений: 73
|
|
16.05.2011, 15:07 | 14 |
есть ище лучший для понимание!
типа создаеш функцию которая разчитавает площадь треугольника за теоремой Герона(площадь только со сторонами) потом пусть будет (x,y) точки. далле ищеш площу загальнова трикутныка S= (х1,у1,х2,у2,х3,у3) потом S1=(х1,у1,х2,у2,х,у) и ище S2=(х1,у1,х,у,х3,у3) S3=(х,у,х2,у2,х3,у3) тогда если S1+S2+S3=S; то точка лежыт в треугольнике!! если непонятоно стучи в скайп snayper_ukr ростолкую понтяней
0
|
12 / 12 / 2
Регистрация: 09.03.2011
Сообщений: 38
|
|
28.05.2011, 19:41 | 15 |
Если бы вы посмотрели чуточку выше в чате, там была фраза "не по Герону, разумеется". Вас это на мысль не навело? В свое время в этой теме был холивар про использование квадратного корня. Герон использует его, по вашему алгоритму, четырежды. Это совершенно неприемлемо по нескольким причинам:
а) Потеря точности б) Нереальная потеря времени. Это основное, на мой взгляд. Особенно, если функция используется много и часто. Так что, герон есть крайне неоптимальный вариант, и лучше забыть о нем, как и обо всех, где хоть как то затронут корень и/или тригонометрические функции.
1
|
5 / 5 / 2
Регистрация: 07.05.2018
Сообщений: 14
|
|
07.05.2018, 17:53 | 16 |
Вот решение для С++ Это в ООП
0
|
0 / 0 / 0
Регистрация: 26.04.2020
Сообщений: 13
|
|||||||||||||||||||||
14.07.2021, 14:05 | 17 | ||||||||||||||||||||
Я написал, это так на c#. По-моему красота. Можно ли еще улучшить и оптимизировать этот метод?
По версии Герона тоже написал для эксперимента. Красиво, по своему.
А еще эффективней будет и деление на 2 убрать. И не объявлять отдельно площади, если их потом все-равно складывать.
Упрощенный первый метод:
0
|
0 / 0 / 0
Регистрация: 26.04.2020
Сообщений: 13
|
|
14.07.2021, 14:09 | 18 |
По факту первый метод действительно быстрее Герона. Тут один миллион случайных треугольников и точек, с float координатами в диапазоне [0, 1);
0
|
136 / 49 / 5
Регистрация: 10.01.2017
Сообщений: 1,894
|
|
01.12.2023, 10:24 | 19 |
1)Подскажите пожалуйста, а x1, x2 и x3 - в каком порядке должны быть ? В любом ?
То есть x1 - может быть любой угол, а x2 и x3 - следующие углы, как по часовой стрелке, так и против часовой стрелки ? 2)"Если они одинакового знака, то точка внутри треугольника..." - одинакового знака или одинакового знака больше нуля ?
0
|
02.12.2023, 02:51 | 20 |
0
|
02.12.2023, 02:51 | |
02.12.2023, 02:51 | |
Помогаю со студенческими работами здесь
20
Принадлежит ли точка M(x,y) треугольнику? Точка принадлежит треугольнику Принадлежит ли точка треугольнику Принадлежит ли точка М(а,3) треугольнику Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |