Определите, принадлежит ли точка треугольнику

@Ferum · Регистрация: 26.12.2020

Студворк — интернет-сервис помощи студентам

Дана точка A(x,y). Определите принадлежит ли она треугольнику с вершинами в
точках (x1, y1), (x2,y2), (x3,y3

@Svetlana Saphon · 29.04.2021, 19:54

Ferum, берете отрезок от точки А до одной из вершин треугольника и проверяете на пересечение с прямой, проходящей через 2 другие вершины. То же самое делаете для двух других вершин. Если есть хоть одно пересечение, значит, точка вне треугольника. Если нет ни одного пересечения, значит, точка внутри треугольника

@liv · 29.04.2021, 20:02

Сообщение от Svetlana Saphon

Если есть хоть одно пересечение

А как Вы предлагаете проверять пересечение?

Лучше вспомнить векторную алгебру... Рассматриваем последовательно три вектора AB, BC, CA и проверяем по какую сторону от вектора находится точка. Если по одну для всех, значит - внутри.

@Svetlana Saphon · 29.04.2021, 20:09

Сообщение от liv

А как Вы предлагаете проверять пересечение?

Довольно просто... Находим по координатам точек уравнения прямых и, если они не параллельны, то находим точку пересечения.

@liv · 29.04.2021, 20:13

Сообщение от Svetlana Saphon

находим точку пересечения

Это понятно. А как определить "Если нет ни одного пересечения, значит, точка внутри треугольника", т.е. по какую сторону от стороны находится точка?

@Svetlana Saphon · 29.04.2021, 20:19

Сообщение от liv

т.е. по какую сторону от стороны находится точка?

Зачем нам определять по какую сторону от стороны находится точка? Нужно определить только есть ли пересечение или нет. Как определить есть ли пересечение, написано в посте выше)))

@liv · 29.04.2021, 20:25

Svetlana Saphon, дело-то в том, что пересечение ПРЯМЫХ будет всегда! А нам надо пересечение отрезков!
Давайте лучше напишите программку, как Вы это видите

А там посмотрим...

@Svetlana Saphon · 30.04.2021, 01:18

Сообщение от liv

А нам надо пересечение отрезков!

Ну, вообще то не отрезков, а отрезка и прямой))) И это важно! Ибо проверка на пересечение отрезков будет далеко не всегда показывать где точка!

Сообщение от liv

Давайте лучше напишите программку, как Вы это видите

А она уже давно написана... Правда, на C#... Но, думаю, в плане теории это роли не играет. Я поэтому и говорю, что метод рабочий, потому что он уже реализован в коде и проверен

@liv · 30.04.2021, 08:14

Svetlana Saphon, покажите на С#. Интересно же

@Annemesski · 30.04.2021, 10:21

Сообщение от Svetlana Saphon

Нужно определить только есть ли пересечение или нет.

Это не решение

Точка А снаружи треугольника, а пересечений нет

@liv · 30.04.2021, 11:50

Вот мое решение:

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
#include <cmath>
 
typedef struct
{
    double x;
    double y;
}point;
 
// вычисляет положение точки D относительно AB
// важен знак
int g(point a, point b, point d)
{
    double r = (d.x - a.x) * (b.y - a.y) - (d.y - a.y) * (b.x - a.x);
    if (fabs(r) < 0.000001)
        return 0;   //точка на прямой, на которой вектор
    else if (r < 0)
        return -1;  //точка слева от вектора
    else 
        return 1;   //точка справа от вектора
}
 
// возвращает 1/0, если точка x внутри треугольника abc
bool f(point a, point b, point c, point x)
{
    //определяем, точка слева, справа или на отрезках (прямых)
    int ab = g(a, b, x);
    int bc = g(b, c, x);
    int ca = g(c, a, x);
    //внутри треугольника (включая границу), если все >=0 или все <= 0
    return ((ab >= 0 && bc >= 0 && ca >= 0) || (ab <= 0 && bc <= 0 && ca <= 0));
}
 
int main()
{
    point   a = { 1,1 };
    point   c = { 5,5 };
    point   b = { 6,0 };
 
    point   x = { 4, 2 };
 
    bool inTreangle = f(a, b, c, x);
 
    return 0;
}

Добавлено через 1 минуту

Сообщение от Svetlana Saphon

Я поэтому и говорю

Надо не говорить, а показывать...

@повар1 · 30.04.2021, 12:18

Сообщение от liv

Лучше вспомнить векторную алгебру

Ну ее подальше. Обозначим точку, например D, а треугольник ABC. Точка с вершинами треугольника образует три треугольника DAC, DBC и DAB. Ищем площади этих треугольников по формуле Герона. Если сумма этих площадей будет равна площади треугольника ABC то точка принадлежит, а иначе нет.
Код написать не составит труда.

@liv · 30.04.2021, 12:31

Сообщение от повар1

Ну ее подальше

Вот это зря...

Хорошая вещь!
Но и Ваш метод хорош!

@Svetlana Saphon · 30.04.2021, 19:22

Сообщение от Annemesski

Это не решение

А Вы прочитайте внимательно! проверяется не пересечение отрезков, а отрезка от точки до вершины с прямой, проходящей через 2 другие вершины! На Вашем рисунке как раз отрезок [A, x2] пересекает прямую проходящую через вершины [x1, x3]

Сообщение от liv

покажите на С#. Интересно же

Да без проблем! )))

Кликните здесь для просмотра всего текста

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
        public bool ContainsPoint(Point p)
        {
            Point p1, p2, p3;
 
            p1 = vertices[0].ToPoint();
            p2 = vertices[1].ToPoint();
            p3 = vertices[2].ToPoint();
 
            return !(checkIntersectionOfTwoLines(p, p1, p2, p3) || checkIntersectionOfTwoLines(p, p2, p1, p3) || checkIntersectionOfTwoLines(p, p3, p1, p2));
        }
 
        private bool checkIntersectionOfTwoLines(Point p1, Point p2, Point p3, Point p4)
        {
            if (p2.X < p1.X)
            {
 
                Point tmp = p1;
                p1 = p2;
                p2 = tmp;
            }
            if (p4.X < p3.X)
            {
 
                Point tmp = p3;
                p3 = p4;
                p4 = tmp;
            }
            if (p2.X < p3.X)
            {
                return false; 
            }
 
            if ((p1.X - p2.X == 0) && (p3.X - p4.X == 0))
            {
                if (p1.X == p3.X)
                {
                    if (!((Math.Max(p1.Y, p2.Y) < Math.Min(p3.Y, p4.Y)) ||
                            (Math.Min(p1.Y, p2.Y) > Math.Max(p3.Y, p4.Y))))
                    {
 
                        return true;
                    }
                }
 
                return false;
            }
 
            double Xa, A1, A2, b1, b2, Ya;
 
            if (p1.X - p2.X == 0)
            {
                Xa = p1.X;
                A2 = (p3.Y - p4.Y) / (double)(p3.X - p4.X);
                b2 = p3.Y - A2 * p3.X;
                Ya = A2 * Xa + b2;
 
                if (p3.X <= Xa && p4.X >= Xa && Math.Min(p1.Y, p2.Y) <= Ya &&
                        Math.Max(p1.Y, p2.Y) >= Ya)
                {
 
                    return true;
                }
 
                return false;
            }
            if (p3.X - p4.X == 0)
            {
                Xa = p3.X;
                A1 = (p1.Y - p2.Y) / (double)(p1.X - p2.X);
                b1 = p1.Y - A1 * p1.X;
                Ya = A1 * Xa + b1;
 
                if (p1.X <= Xa && p2.X >= Xa && Math.Min(p3.Y, p4.Y) <= Ya &&
                        Math.Max(p3.Y, p4.Y) >= Ya)
                {
 
                    return true;
                }
 
                return false;
            }
            A1 = (p1.Y - p2.Y) / (double)(p1.X - p2.X);
            A2 = (p3.Y - p4.Y) / (double)(p3.X - p4.X);
            b1 = p1.Y - A1 * p1.X;
            b2 = p3.Y - A2 * p3.X;
 
            if (A1 == A2)
            {
                return false;
            }
 
            Xa = (b2 - b1) / (A1 - A2);
 
            if ((Xa > Math.Max(p1.X, p2.X)) || (Xa < Math.Min(p1.X, p2.X)))
            {
                return false; 
            }
            else
            {
                return true;
            }
        }

Ну и сама прога, если кому интересно: Triangle.zip

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@Ferum 1 / 1 / 0 Регистрация: 26.12.2020 Сообщений: 80

	Определите, принадлежит ли точка треугольнику 29.04.2021, 19:35. Показов 3478. Ответов 13 Метки С++ для начинающих (Все метки) Дана точка A(x,y). Определите принадлежит ли она треугольнику с вершинами в точках (x1, y1), (x2,y2), (x3,y3 0

@Svetlana Saphon 76 / 54 / 22 Регистрация: 26.02.2017 Сообщений: 206
	29.04.2021, 19:54
	Ferum, берете отрезок от точки А до одной из вершин треугольника и проверяете на пересечение с прямой, проходящей через 2 другие вершины. То же самое делаете для двух других вершин. Если есть хоть одно пересечение, значит, точка вне треугольника. Если нет ни одного пересечения, значит, точка внутри треугольника 0

@liv 5120 / 4574 / 855 Регистрация: 07.10.2015 Сообщений: 9,462
	29.04.2021, 20:25
	Svetlana Saphon, дело-то в том, что пересечение ПРЯМЫХ будет всегда! А нам надо пересечение отрезков! Давайте лучше напишите программку, как Вы это видите А там посмотрим... 0

@liv 5120 / 4574 / 855 Регистрация: 07.10.2015 Сообщений: 9,462
	30.04.2021, 08:14
	Svetlana Saphon, покажите на С#. Интересно же 0