|
12 / 12 / 3
Регистрация: 09.05.2010
Сообщений: 384
|
|
Как проверить принадлежит ли точка треугольнику?13.06.2010, 02:17. Показов 270115. Ответов 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 | |
|
пусть твоя точка имеет координаты (х,у), а вершины треугольника - (х1,у1), (х2,у2), (х3,у3).
точка будет принадлежать треугольнику, если будет принадлежать одновременно трем полуплоскостям, пересечение которых и есть треугольник. точка с координатами (х,у) принадлежит полуплоскости, когда находится по одну из сторон некоторой прямой, а именно y-(kx+b)>=0 , где k, b - параметры данной прямой. далее нужно найти уравнения прямых, которые содержат стороны треугольника, составить 3 неравенства, и решить систему из этих 3х неравенств. составить уравнение прямых можно с помощью уравнения прямой, проходящей через 2 точки на плоскости
1
|
|
|
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
|
| 13.06.2010, 14:33 | |
Сообщение было отмечено как решение
Решение
Уже было - 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 [ТС] | |
|
junkier, Somebody - спасибо...
1
|
|
|
42 / 42 / 3
Регистрация: 11.04.2010
Сообщений: 177
|
||||||||||||
| 22.06.2010, 22:15 | ||||||||||||
|
namespace zadacha_2
вот ещо одно решения етой задачи
3
|
||||||||||||
|
12 / 12 / 2
Регистрация: 09.03.2011
Сообщений: 38
|
|
| 09.03.2011, 23:26 | |
|
Хотел бы прокоментировать сообщение последнего автора. Первое решение, на мой взгляд в разы лучше второго по одной простой причине. Известно, что квадратный корень есть очень медленная функция. Решение 2 прокатит, если нужно проверить один треугольник, и все. Но если мы программируем графику, к примеру, или что-нибудь еще, где нам это надо считать на каждом кадре и/или для каждого пикселя, то есть очень много раз, то оно совершенно неприемлимо. Тут скорость не спасет даже замена на Fast Inverse Square Root(см. Википедия), хотя она же и ужасно снизит нам точность.
Мораль, господа! избегайте sqrt(), sin() и cos() в вашем коде. А что касается последних, учтите, что синус и косинус сопроцессор считает в один присест и просто пихает их на стек один поверх другого. компилляторы(даже VS) не умеют оптимизировать используя это. так что иногда имеет смысл(особенно в графике, при рассчете матриц поворота) переписать эти куски кода на АСМе... хотя если вы пишите на C#... фу, классический С форевер! =)
2
|
|
|
Українець
424 / 318 / 16
Регистрация: 26.09.2009
Сообщений: 844
|
|
| 10.03.2011, 04:41 | |
|
.спасибо
0
|
|
|
294 / 206 / 2
Регистрация: 20.02.2011
Сообщений: 551
|
||
| 10.03.2011, 14:01 | ||
|
[QUOTE=cgsg11;1435009]Хотел бы прокоментировать сообщение последнего автора.
С другой стороны, задача-то простая. Не элементарная, но достаточно простая. Somebody уже показал, что все решается без особого выпендрежа. Ну, и нафиг оно, усложнение!
0
|
||
|
Почетный модератор
64314 / 47610 / 32743
Регистрация: 18.05.2008
Сообщений: 115,168
|
|
| 10.03.2011, 14:11 | |
|
Мне кажется аналогично по сложности решение через площади треугольников, естественно не по Герону...
1
|
|
|
12 / 12 / 2
Регистрация: 09.03.2011
Сообщений: 38
|
||||||
| 11.03.2011, 01:26 | ||||||
Сообщение было отмечено как решение
Решение
Господа. Должен заметить, что код первого решения вроде как неверен... Я не знаю, проверял ли ПроСтоСанек свое решение, но он в цикле явно "гадит" мимо массива (из-за ++i вместо i++)
Выкладываю код моего решения, которое проверено и работает (косметические изменения плюс исправленая ошибка, для тех, кто обожает копипасту с форумов =) ).
3
|
||||||
|
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
|
|
| 11.03.2011, 19:55 | |
|
0
|
|
|
12 / 12 / 2
Регистрация: 09.03.2011
Сообщений: 38
|
||
| 12.03.2011, 00:07 | ||
|
Я подозревал, что облажаюсь так. )
Ошибку понял:
0
|
||
|
1 / 1 / 0
Регистрация: 27.02.2011
Сообщений: 25
|
|
| 11.05.2011, 21:40 | |
|
Спасибо за методы. Очень пригодились!
0
|
|
|
7 / 7 / 3
Регистрация: 11.01.2011
Сообщений: 73
|
|
| 16.05.2011, 15:07 | |
|
есть ище лучший для понимание!
типа создаеш функцию которая разчитавает площадь треугольника за теоремой Герона(площадь только со сторонами) потом пусть будет (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 | |
|
Если бы вы посмотрели чуточку выше в чате, там была фраза "не по Герону, разумеется". Вас это на мысль не навело? В свое время в этой теме был холивар про использование квадратного корня. Герон использует его, по вашему алгоритму, четырежды. Это совершенно неприемлемо по нескольким причинам:
а) Потеря точности б) Нереальная потеря времени. Это основное, на мой взгляд. Особенно, если функция используется много и часто. Так что, герон есть крайне неоптимальный вариант, и лучше забыть о нем, как и обо всех, где хоть как то затронут корень и/или тригонометрические функции.
1
|
|
|
5 / 5 / 2
Регистрация: 07.05.2018
Сообщений: 14
|
|
| 07.05.2018, 17:53 | |
|
Вот решение для С++ Это в ООП
0
|
|
|
0 / 0 / 0
Регистрация: 26.04.2020
Сообщений: 13
|
|||||||||||||||||||||
| 14.07.2021, 14:05 | |||||||||||||||||||||
|
Я написал, это так на c#. По-моему красота. Можно ли еще улучшить и оптимизировать этот метод?
По версии Герона тоже написал для эксперимента. Красиво, по своему.
А еще эффективней будет и деление на 2 убрать. И не объявлять отдельно площади, если их потом все-равно складывать.
Упрощенный первый метод:
0
|
|||||||||||||||||||||
|
0 / 0 / 0
Регистрация: 26.04.2020
Сообщений: 13
|
|
| 14.07.2021, 14:09 | |
|
По факту первый метод действительно быстрее Герона. Тут один миллион случайных треугольников и точек, с float координатами в диапазоне [0, 1);
0
|
|
|
-41 / 49 / 5
Регистрация: 10.01.2017
Сообщений: 1,915
|
||
| 01.12.2023, 10:24 | ||
|
То есть x1 - может быть любой угол, а x2 и x3 - следующие углы, как по часовой стрелке, так и против часовой стрелки ? 2)"Если они одинакового знака, то точка внутри треугольника..." - одинакового знака или одинакового знака больше нуля ?
0
|
||
|
|
|
| 02.12.2023, 02:51 | |
|
0
|
|
| 02.12.2023, 02:51 | |
|
Помогаю со студенческими работами здесь
20
Принадлежит ли точка треугольнику
Точка принадлежит треугольнику
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
|
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
|
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов
На странице:
https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/
нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
|
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
|
|
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
|
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут.
В век Веб все очень привыкли к дизайну Single-Page-Application .
Быстренько разберем подход "на фреймах".
Мы делаем одну. . .
|
Фото: Daniel Greenwood
kumehtar 13.11.2025
|
Расскажи мне о Мире, бродяга
kumehtar 12.11.2025
— Расскажи мне о Мире, бродяга,
Ты же видел моря и метели.
Как сменялись короны и стяги,
Как эпохи стрелою летели.
- Этот мир — это крылья и горы,
Снег и пламя, любовь и тревоги,
И бескрайние. . .
|
PowerShell Snippets
iNNOKENTIY21 11.11.2025
Модуль PowerShell 5. 1+ : Snippets. psm1
У меня модуль расположен в пользовательской папке модулей, по умолчанию: \Documents\WindowsPowerShell\Modules\Snippets\
А в самом низу файла-профиля. . .
|