Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.64/1412: Рейтинг темы: голосов - 1412, средняя оценка - 4.64
12 / 12 / 3
Регистрация: 09.05.2010
Сообщений: 384
1

Как проверить принадлежит ли точка треугольнику?

13.06.2010, 02:17. Показов 256398. Ответов 19
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Как проверить принадлежит ли двумерная точка треугольнику с двумерными координатами?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.06.2010, 02:17
Ответы с готовыми решениями:

Как проверить, принадлежит ли точка треугольнику
Пожалуйста, помогите найти ошибку: Sub xy() Dim x1, y1, x2, y2, x3, y3 As Single x1 =...

Проверить, принадлежит ли точка M(x,y) треугольнику с заданными вершинами
помогите плиз две задачки решить: Проверить, принадлежит ли точка M(x,y) треугольнику с...

Проверить принадлежит ли точка плоскости с координатами (x,y) треугольнику с заданными вершинами
Даны два вещественных числа x,y. Если точка плоскости с координатами (x,y) принадлежит треугольнику...

Принадлежит ли точка треугольнику
дан три угольник ABC с координатами вершин A(xa,ya), B(xb,yb), C(xc,yc), Пользователь водит...

19
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
Цитата Сообщение от Somebody Посмотреть сообщение
Уже было - 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)
Если они одинакового знака, то точка внутри треугольника, если что-то из этого - ноль, то точка лежит на стороне, иначе точка вне треугольника.
вот решения по данной формуле выше
namespace zadacha_2
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
    class Program
    {
        static void Main(string[] args)
        {
 
            int[] x = new int[4];
            int[] y = new int[4];
            for (int i = 0; i < 4; ++i)
            {
               Console.Write("Введите (x" + i.ToString() + ",y" + i.ToString() + "): ");
                x[i] = Console.Read();
                y[i] = Console.Read();
                Console.ReadLine();
            }
            int a = (x[1] - x[0]) * (y[2] - y[1]) - (x[2] - x[1]) * (y[1] - y[0]);
            int b = (x[2] - x[0]) * (y[3] - y[2]) - (x[3] - x[2]) * (y[2] - y[0]);
            int c = (x[3] - x[0]) * (y[1] - y[3]) - (x[1] - x[3]) * (y[3] - y[0]);
 
            if ((a >= 0 && b >= 0 && c >= 0) || (a <= 0 && b <= 0 && c <= 0))
            {
                Console.WriteLine("Принадлежит треугольнику");
            }
            else
            {
                Console.WriteLine("Не принадлежит треугольнике");
            }
            Console.ReadKey();
        }
Добавлено через 13 минут
вот ещо одно решения етой задачи


C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 class Program
    {
        static void Main(string[] args)
        {
            int x, y, x1, y1, x2, y2, x3, y3;
            int s, s1, s2, s3;
            Console.WriteLine("\nVvedite koordinaty treugolnika:");
            Console.WriteLine("x1=");
            x1 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("y1="); 
            y1 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("x2=");
            x2 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("y2="); 
            y2 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("x3=");
            x3 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("y3");
            y3 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("\nVVedite koordinaty tochki: ");
            Console.WriteLine("y=");
            x = Int32.Parse(Console.ReadLine());
            Console.WriteLine("x=");
            y = Int32.Parse(Console.ReadLine());
 
            if ((x1==x2==x3) || (y1==y2==y3))
            {
                Console.WriteLine("\nNevernye koordinaty treugolnika!");
            }
            {
                s = 1 / 2 *Math.Abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1));
                s1 = 1 / 2 *Math.Abs((x2 - x1) * (y - y1) - (x - x1) * (y2 - y1));
                s2 = 1 / 2 *Math.Abs((x - x1) * (y3 - y1) - (x3 - x1) * (y - y1));
                s3 = 1 / 2 *Math.Abs((x2 - x) * (y3 - y) - (x3 - x) * (y2 - y));
 
                if (s == s1 + s2 + s3)
                
                    Console.WriteLine("\n Tochka v treugolnike! ");
                else 
                    Console.WriteLine("\n Vne treugolnika!");
                
                }
            Console.ReadKey();
 
 
            }
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]Хотел бы прокоментировать сообщение последнего автора.
Первое решение, на мой взгляд в разы лучше второго по одной простой причине. Известно, что квадратный корень есть очень медленная функция. Решение 2 прокатит, если нужно проверить один треугольник, и все. Но если мы программируем графику, к примеру, или что-нибудь еще, где нам это надо считать на каждом кадре и/или для каждого пикселя, то есть очень много раз, то оно совершенно неприемлимо. Тут скорость не спасет даже замена на Fast Inverse Square Root(см. Википедия), хотя она же и ужасно снизит нам точность.
Мораль, господа! избегайте sqrt(), sin() и cos() в вашем коде.
Любое вычисление более-менее извращенных функций, вроде синуса-косинуса, или квадратного корня, явно снизит скорость выполнения данного алгоритма. Тут без вопросов, и спорить не о чем. Остается только согласиться.

С другой стороны, задача-то простая. Не элементарная, но достаточно простая. Somebody уже показал, что все решается без особого выпендрежа. Ну, и нафиг оно, усложнение!
0
Почетный модератор
64304 / 47599 / 32743
Регистрация: 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++)
Выкладываю код моего решения, которое проверено и работает (косметические изменения плюс исправленая ошибка, для тех, кто обожает копипасту с форумов =) ).

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// p1 - p3: вершины треугольника, ptest: проверяемая точка.
// VEC - структура, содержащая поля X, Y, написанная нами.
// Можно вполне использовать POINT из <windows.h>
// Возвращается TRUE, если принадлежит, иначе - FALSE.
BOOL IsInTriangle( VEC P1, VEC P2, VEC P3, VEC PTest )
{
  int a = (P1.X - PTest.X) * (P2.Y - P1.Y) - (P2.X - P1.X) * (P1.Y - PTest.Y);
  int b = (P2.X - PTest.X) * (P3.Y - P2.Y) - (P3.X - P2.X) * (P2.Y - PTest.Y);
  int c = (P3.X - PTest.X) * (P1.Y - P3.Y) - (P1.X - P3.X) * (P3.Y - PTest.Y);
 
  if ((a >= 0 && b >= 0 && c >= 0) || (a <= 0 && b <= 0 && c <= 0))
    return TRUE;
  else
    return FALSE;
}
3
Эксперт С++
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
11.03.2011, 19:55 11
Цитата Сообщение от cgsg11 Посмотреть сообщение
"гадит" мимо массива (из-за ++i вместо i++)
Конкретно в данном случае они эквивалентны, лол.
0
12 / 12 / 2
Регистрация: 09.03.2011
Сообщений: 38
12.03.2011, 00:07 12
Я подозревал, что облажаюсь так. )
Ошибку понял:
При обнаружении в программе цикла for первым выполняется инициализирующее_выражение, в котором обычно устанавливается счетчик цикла. Это происходит только один раз перед запуском цикла. Затем анализируется условное_выражение, которое также называется условием прекращения цикла. Пока оно равно true, цикл не прекращается.

Каждый раз после всех строк тела цикла выполняется модифицирующее_выражение, в котором происходит изменение счетчика цикла. Как только проверка условного_выражения даст результат false, все строки тела цикла и модифицирующее_выражение будут пропущены и управление будет передано первому выражению, следующему за телом цикла.
Я почему-то решил, что ++ выполнится до условного выражения и до тела цикла. Но по мне так писать ++i в форе все равно моветон. никогда такого изврата не встречал. имхо это нелогично.
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
Вот решение для С++ Это в ООП
Вложения
Тип файла: txt 13.txt (1.6 Кб, 188 просмотров)
Тип файла: txt geometry.cpp.txt (807 байт, 147 просмотров)
Тип файла: txt geometry.h.txt (493 байт, 109 просмотров)
0
0 / 0 / 0
Регистрация: 26.04.2020
Сообщений: 13
14.07.2021, 14:05 17
Я написал, это так на c#. По-моему красота. Можно ли еще улучшить и оптимизировать этот метод?
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
        public static bool Is_point_in_triangle(Point[] triangle, Point point, bool include_borders)
        {
            float a = (triangle[0].X - point.X) * (triangle[1].Y - triangle[0].Y) - (triangle[1].X - triangle[0].X) * (triangle[0].Y - point.Y);
            float b = (triangle[1].X - point.X) * (triangle[2].Y - triangle[1].Y) - (triangle[2].X - triangle[1].X) * (triangle[1].Y - point.Y);
            float c = (triangle[2].X - point.X) * (triangle[0].Y - triangle[2].Y) - (triangle[0].X - triangle[2].X) * (triangle[2].Y - point.Y);
 
            int summ = 0;
 
            if (a > 0)
                summ++;
            else if (a < 0)
                summ--;
 
            if (b > 0)
                summ++;
            else if (b < 0)
                summ--;
 
            if (c > 0)
                summ++;
            else if (c < 0)
                summ--;
 
            summ = Math.Abs(summ);
 
            if (summ == 3)
                return true;
            else if (include_borders && summ == 2)
                return true;
            else
                return false;
        }
Добавлено через 32 минуты
По версии Герона тоже написал для эксперимента. Красиво, по своему.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        public static bool Is_point_in_triangle_geron(Point[] triangle, Point point)
        {
            float S = Find_triangle_S(triangle); //S значит площадь
 
            float SA = Find_triangle_S(new Point[] { point, triangle[1], triangle[2] });
            float SB = Find_triangle_S(new Point[] { triangle[0], point, triangle[2] });
            float SC = Find_triangle_S(new Point[] { triangle[0], triangle[1], point });
 
            return SA + SB + SC == S;
        }
 
        public static float Find_triangle_S(Point[] triangle)
        {
            float min_x = Math.Min(Math.Min(triangle[0].X, triangle[1].X), triangle[2].X);
            float max_x = Math.Max(Math.Max(triangle[0].X, triangle[1].X), triangle[2].X);
            float min_y = Math.Min(Math.Min(triangle[0].Y, triangle[1].Y), triangle[2].Y);
            float max_y = Math.Max(Math.Max(triangle[0].Y, triangle[1].Y), triangle[2].Y);
 
            return (max_x - min_x) * (max_y - min_y) / 2;
        }
Добавлено через 9 минут
А еще эффективней будет и деление на 2 убрать. И не объявлять отдельно площади, если их потом все-равно складывать.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        public static bool Is_point_in_triangle_geron(Point[] triangle, Point point)
        {
            float double_S = Find_triangle_S(triangle); //S значит площадь
 
            float double_S_from_ABC_summ = Find_triangle_double_S(new Point[] { point, triangle[1], triangle[2] });
            double_S_from_ABC_summ += Find_triangle_double_S(new Point[] { triangle[0], point, triangle[2] });
            double_S_from_ABC_summ += Find_triangle_double_S(new Point[] { triangle[0], triangle[1], point });
 
            return double_S_from_ABC_summ == double_S;
 
            float Find_triangle_double_S(Point[] t)
            {
                float min_x = Math.Min(Math.Min(t[0].X, t[1].X), t[2].X);
                float max_x = Math.Max(Math.Max(t[0].X, t[1].X), t[2].X);
                float min_y = Math.Min(Math.Min(t[0].Y, t[1].Y), t[2].Y);
                float max_y = Math.Max(Math.Max(t[0].Y, t[1].Y), t[2].Y);
 
                return (max_x - min_x) * (max_y - min_y);
            }
        }
Добавлено через 46 минут
Упрощенный первый метод:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
        public static bool Is_point_in_triangle_easier(PointF[] triangle, PointF point)
        {
            int summ = 0;
 
            float a = (triangle[0].X - point.X) * (triangle[1].Y - triangle[1].Y) - (triangle[1].X - triangle[0].X) * (triangle[0].Y - point.Y);
            float b = (triangle[1].X - point.X) * (triangle[2].Y - triangle[1].Y) - (triangle[2].X - triangle[1].X) * (triangle[1].Y - point.Y);
            float c = (triangle[2].X - point.X) * (triangle[0].Y - triangle[2].Y) - (triangle[0].X - triangle[2].X) * (triangle[2].Y - point.Y);
 
            if (a > 0)
                summ++;
            else if (a < 0)
                summ--;
 
            if (b > 0)
                summ++;
            else if (b < 0)
                summ--;
 
            if (c > 0)
                summ++;
            else if (c < 0)
                summ--;
 
            return Math.Abs(summ) >= 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,883
01.12.2023, 10:24 19
Цитата Сообщение от Somebody Посмотреть сообщение
Уже было - 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)
Если они одинакового знака, то точка внутри треугольника, если что-то из этого - ноль, то точка лежит на стороне, иначе точка вне треугольника.
1)Подскажите пожалуйста, а x1, x2 и x3 - в каком порядке должны быть ? В любом ?
То есть x1 - может быть любой угол, а x2 и x3 - следующие углы, как по часовой стрелке, так и против часовой стрелки ?

2)"Если они одинакового знака, то точка внутри треугольника..." - одинакового знака или одинакового знака больше нуля ?
0
1017 / 1904 / 178
Регистрация: 07.05.2013
Сообщений: 3,931
Записей в блоге: 12
02.12.2023, 02:51 20
Цитата Сообщение от EviLordus Посмотреть сообщение
triangle[1].Y - triangle[1].Y
...
0
02.12.2023, 02:51
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.12.2023, 02:51
Помогаю со студенческими работами здесь

Принадлежит ли точка M(x,y) треугольнику?
принадлежит ли точка M(x,y) треугольнику А(-1;0),В(0;1),С(1;0) на паскале Незнаю как ,знаю только...

Точка принадлежит треугольнику
Public Class Form1 Private _abs As Integer Private Property Abs(ByVal p1 As Integer)...

Принадлежит ли точка треугольнику
Даны вершины треугольника А, В, С на координатной плоскости. М - произвольная точка плоскости....

Принадлежит ли точка М(а,3) треугольнику
Принадлежит ли точка М(а,3) треугольнику, образованному прямыми y=x, y=8-x,y=2? Двнные для ввода:...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru