Как узнать, лежит ли точка внутри триугольника или нет по заданным координатам.

@yuraha18 · Регистрация: 16.12.2009

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

дано координати точки А, и координати 3 сторон триугольника
как узнать есть ли точка внутри триугольника или нет

@snake32 · 29.12.2009, 00:31

Проводим луч из точки А в любую сторону и счетаем сколько раз этот луч пересекает стороны треугольника. Если нечётное кол-во раз значит внутри, иначе - нет. Это правило подходит и для полигонов. Возможно для треугольника есть и проще метод, но я такого не знаю.
Если кто знает поделитесь.

@odip · 29.12.2009, 21:40

1-ый способ
Пусть есть треугольник ABC и точка D.
Пишем уравнения трех прямых AB, AC, BC.
Каждая прямая разбивает плоскость на две полуплоскости.
a) Для прямой AB проверяем что точка D лежит в той же полуплоскости что и точка C.
b) Для прямой AC проверяем что точка D лежит в той же полуплоскости что и точка B.
c) Для прямой BC проверяем что точка D лежит в той же полуплоскости что и точка A.
Если все три условия (a),(b),(c) верны, то точка лежит внутри треугольника.
Нужно только учесть вариант, когда точка D лежит прямо на стороне треугольника.

2-ой способ
Пусть есть треугольник ABC и точка D.
По трем точкам ABC считаем площадь треугольника S(ABC)
Проверяем условие S(ABC) == S(ABD)+S(ACD)+S(BCD)
Если верно, то точка лежит внутри треугольника.
Если какая-то из площадей S(ABD), S(ACD), S(BCD) равна 0, то это значит что точка D лежит на прямой, проходящей через сторону треугольника.

3-ий способ приведен выше

@ShadoW · 23.01.2010, 01:07

Да, а первый способ еще можно расширить до бинарного поиска по полигону..

@CyBOSSeR · 23.01.2010, 01:12

Откопал свою древнюю лабораторную по данной теме, вот:

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
#include <iostream>
#include <math.h>
 
using std::cout;
using std::cin;
using std::endl;
 
// Структура предназначенная для хранения координат точки в плоскости
// x - координата x точки
// y - координата y точки
typedef struct tagPoint2D {
    double x;
    double y;
} Point2D;
 
// Служебная функция вычисляющая площадь треугольника заданного тремя точками
//
// Аргументы
// a - координаты первой вершины треугольника
// b - координаты второй вершины треугольника
// с - координаты третьей вершины треугольника
//
// Возвращаемое значение
// Площадь треугольника
double TriangleSquare(const Point2D& a, const Point2D& b, const Point2D& c)
{
    return fabs(0.5*((b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y)));
}
 
// Функция определяющая принадлежность точки треугольнику
//
// Аргументы
// p - координаты точки для проверки на принадлежание треугольнику
// a - координаты первой вершины треугольника
// b - координаты второй вершины треугольника
// с - координаты третьей вершины треугольника
//
// Возвращаемое значение
// true - если точка принадлежит треугольнику, false в противном случае
//
// Дополнительная информация
// Точка считается принадлежащей треугольнику, если она:
// - лежит внутри треугольника
// - лежит на одной из сторон треугольника
// - совпадает с одной из вершин  треугольника
bool IsPointInTriangle(const Point2D& p, const Point2D& a, const Point2D& b, const Point2D& c)
{
    return TriangleSquare(a, b, c) == TriangleSquare(p, a, b) + TriangleSquare(p, b, c) + TriangleSquare(p, a, c);
}
 
// Обработка пользовательского ввода
void InputCoordinates(Point2D* a, Point2D* b, Point2D* c, Point2D* p)
{ 
        cout << "Введите координаты точки а треугольника abc:" << endl
           << "x: ";
        cin >> a->x;
    cout << "y: ";
    cin >> a->y;
 
    cout << "Введите координаты точки b треугольника abc:" << endl
           << "x: ";
    cin >> b->x;
    cout << "y: ";
    cin >> b->y;
 
    cout << "Введите координаты точки c треугольника abc:" << endl
           << "x: ";
    cin >> c->x;
    cout << "y: ";
    cin >> c->y;
 
    cout << "Введите координаты точки p для проверки принадлежанию треугольнику abc:" << endl
           << "x: ";
    cin >> p->x;
    cout << "y: ";
    cin >> p->y;
}
 
int main()
{
    Point2D a, b, c, p;
 
        setlocale(LC_ALL, "Russian");  // Устанавливаем русскую кодовую страницу
 
        InputCoordinates(&a, &b, &c, &p);
 
    cout << "Точка p(" << p.x << "," << p.y << ") " 
           <<(IsPointInTriangle(p, a, b, c)? "принадлежит" : "не принадлежит" ) 
           << " треугольнику abc" << endl;
 
    system("pause");
 
    return 0; 
}

Способ решения аналогичен способу номер 2, предложенному odip'ом.

@snake32 · 23.01.2010, 01:21

Ф-ия IsPointInTriangle редко возвращает TRUE, если координаты не целые числа.
Лучше использовать абсолютную разность при работе с флоатом:

C++
1
2
3
4
5
const eps = 1e-5;
bool IsPointInTriangle(const Point2D& p, const Point2D& a, const Point2D& b, const Point2D& c)
{
        return fabs(TriangleSquare(a, b, c) - TriangleSquare(p, a, b) + TriangleSquare(p, b, c) + TriangleSquare(p, a, c) )<eps;
}

@CyBOSSeR · 23.01.2010, 01:29

snake32, это да. Преподаватель также на это указывал и долго, упорно на разных исходных данных пытался доказать что без EPS такой вариант не сработает. Безрезультатно.

Но совет верный, добавить EPS не мешало бы.

Новые блоги и статьи Все статьи Все блоги /
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

Как узнать, лежит ли точка внутри триугольника или нет по заданным координатам.

Решение

Решение

@yuraha18 2 / 2 / 0 Регистрация: 16.12.2009 Сообщений: 261

	Как узнать, лежит ли точка внутри триугольника или нет по заданным координатам. 28.12.2009, 17:28. Показов 6250. Ответов 6 Метки нет (Все метки) дано координати точки А, и координати 3 сторон триугольника как узнать есть ли точка внутри триугольника или нет 1

@snake32 3504 / 1687 / 236 Регистрация: 26.02.2009 Сообщений: 8,409 Записей в блоге: 6
	29.12.2009, 00:31
	Сообщение было отмечено как решение Решение Проводим луч из точки А в любую сторону и счетаем сколько раз этот луч пересекает стороны треугольника. Если нечётное кол-во раз значит внутри, иначе - нет. Это правило подходит и для полигонов. Возможно для треугольника есть и проще метод, но я такого не знаю. Если кто знает поделитесь. 3

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	29.12.2009, 21:40
	Сообщение было отмечено как решение Решение 1-ый способ Пусть есть треугольник ABC и точка D. Пишем уравнения трех прямых AB, AC, BC. Каждая прямая разбивает плоскость на две полуплоскости. a) Для прямой AB проверяем что точка D лежит в той же полуплоскости что и точка C. b) Для прямой AC проверяем что точка D лежит в той же полуплоскости что и точка B. c) Для прямой BC проверяем что точка D лежит в той же полуплоскости что и точка A. Если все три условия (a),(b),(c) верны, то точка лежит внутри треугольника. Нужно только учесть вариант, когда точка D лежит прямо на стороне треугольника. 2-ой способ Пусть есть треугольник ABC и точка D. По трем точкам ABC считаем площадь треугольника S(ABC) Проверяем условие S(ABC) == S(ABD)+S(ACD)+S(BCD) Если верно, то точка лежит внутри треугольника. Если какая-то из площадей S(ABD), S(ACD), S(BCD) равна 0, то это значит что точка D лежит на прямой, проходящей через сторону треугольника. 3-ий способ приведен выше 3

@ShadoW 7 / 7 / 0 Регистрация: 01.04.2009 Сообщений: 109
	23.01.2010, 01:07
	Да, а первый способ еще можно расширить до бинарного поиска по полигону.. 1

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675
	23.01.2010, 01:29
	snake32, это да. Преподаватель также на это указывал и долго, упорно на разных исходных данных пытался доказать что без EPS такой вариант не сработает. Безрезультатно. Но совет верный, добавить EPS не мешало бы. 0