0 / 0 / 0
Регистрация: 23.09.2018
Сообщений: 5
1

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

23.09.2018, 18:12. Показов 4319. Ответов 15

Author24 — интернет-сервис помощи студентам
Треугольник задан в плоскости точками A, B, C: A (xa, ya) B (xb, yb) C (xc, yc). Составить алгоритм и программу для определения принадлежности данном треугольнике точки M (x, y).
Подскажите с кодом как это можно посчитать. И желательно самым простым вариантом без усложнений.
А то я несколько часов сижу ищу в интернете как это расписать но всё по нулям.
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
23.09.2018, 18:12
Ответы с готовыми решениями:

Определение принадлежности точки фигуре
Всем привет. Есть задача определения принадлежности точки фигуре. Как думаете, нормальный...

Определение принадлежности точки к графику
Помогите написать текст, для такого графика

Определение принадлежности точки к области
Надо определить принадлежность точки к заданной области. Рисунок прикрепил. Вот код который...

Определение принадлежности точки указанной области (перевести с Pascal на C++)
var x,y: real; begin write('Введите значения x, y: '); readln(x,y); if...

15
Модератор
Эксперт С++
 Аватар для zss
13727 / 10923 / 6480
Регистрация: 18.12.2011
Сообщений: 29,157
23.09.2018, 19:22 2
Внизу этой страницы есть нужные ссылки
например https://www.cyberforum.ru/post7631589.html
0
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
23.09.2018, 19:53 3
Алгоритм такой. Пишешь уравнение стороны Ax + By + C = 0;
Если при подстановке точки и третьей вершины выражение Ax + By + C дает один знак - значит точка и вершина лежат по одну сторону от прямой. И так для всех трех. Если где-то дает разный знак - точка не лежит в треугольнике.

Добавлено через 7 минут
Цитата Сообщение от zss Посмотреть сообщение
Не решает задачу. Из-за сравнения на равенство плавающих чисел.
0
Модератор
Эксперт С++
 Аватар для zss
13727 / 10923 / 6480
Регистрация: 18.12.2011
Сообщений: 29,157
23.09.2018, 20:43 4
Цитата Сообщение от Байт Посмотреть сообщение
Не решает задачу.
Ну хотя бы предложен метод.
Дальше уж можно допилить.

Цитата Сообщение от Байт Посмотреть сообщение
Если где-то дает разный знак
Как раз должно быть 2 одного знака и 1 другого.
Т.е. точка лежит под 2 прямыми и над третьей
или точка лежит над 2 прямыми и под третьей.
0
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
23.09.2018, 20:49 5
zss, нет.
Байт всё правильно написал.

Знак означает направление отклонения.
Для каждой вершины направление отклонения должно совпадать с точкой.
1
Модератор
Эксперт С++
 Аватар для zss
13727 / 10923 / 6480
Регистрация: 18.12.2011
Сообщений: 29,157
23.09.2018, 20:55 6
Цитата Сообщение от Байт Посмотреть сообщение
Ax + By + C = 0;
Это уравнение прямой. Положительное отклонение означает, что точка лежит над прямой,
отрицательное - под прямой.
Т.к. точка внутри треугольника лежит под 2 сторонами и над третьей (или наоборот).
То один из знаков должен отличаться.
0
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
23.09.2018, 21:00 7
Вот для ТС формула.
Вертикальные чёрточки означают определитель.
https://www.cyberforum.ru/cgi-bin/latex.cgi?sign(\begin{vmatrix}<br />
x1-x3 & y1-y3\\ <br />
x2-x3 & y2-y3<br />
\end{vmatrix}) <br />
==<br />
sign(\begin{vmatrix}<br />
xt-x3 & yt-y3\\ <br />
x2-x3 & y2-y3<br />
\end{vmatrix})

xt, yt — координаты точки, 1,2,3 — точки прямой, причём в роли точки 1 должна побывать по одному разу каждая вершина.

Добавлено через 3 минуты
zss, ты не понял Байта.
Он имеет в виду, что надо проверить каждую сторону.

Смотри. Если третья вершина под прямой, то и точка должна быть под прямой. Если же вершина над прямой, то и точка должна быть над прямой. То есть, точка и вершина должны быть с одной стороны. То есть, при подстановке третьей вершины в уравнение стороны, должен быть такой же знак, что и при подстановке точки.
2
0 / 0 / 0
Регистрация: 23.09.2018
Сообщений: 5
23.09.2018, 21:03  [ТС] 8
Можете показать код как это должно быть, а то я как-то не понял что нужно сделать.
0
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
23.09.2018, 21:21 9
Цитата Сообщение от ImmortalReaper Посмотреть сообщение
Можете показать код
Зачем? Вы ничего не показываете, ни попыток, ни набросков... А чем мы хуже? Алгоритм вам рассказали. Кодинг - дело техники. И не очень интересно.

Добавлено через 5 минут
Цитата Сообщение от zss Посмотреть сообщение
Дальше уж можно допилить.
Кстати, да. Просто вместо "==" написать "<=".
Но тут такая штука. Если все входные данные - целые, предложенный мной метод позволяет оставаться в тех же целых числах. А уж целые числа комп считает точно.
0
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
23.09.2018, 22:06 10
Лучший ответ Сообщение было отмечено Байт как решение

Решение

ImmortalReaper,
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
#include <iostream>
#include <array>
 
struct FVector2D
{
    float x;
    float y;
};
 
float get_line_func_value(const FVector2D a, const FVector2D b, const FVector2D point)
{
    return (point.x-a.x)*(b.y-a.y) - (point.y-a.y)*(b.x-a.x);
}
 
typedef std::array<FVector2D, 3> Triangle;
 
bool is_inside(const FVector2D point, const Triangle& triangle)
{
    auto f = *get_line_func_value;
    return f(triangle[0], triangle[1], point)*f(triangle[0], triangle[1], triangle[2]) > 0 &&
        f(triangle[0], triangle[2], point)*f(triangle[0], triangle[2], triangle[1]) > 0 &&
        f(triangle[1], triangle[2], point)*f(triangle[1], triangle[2], triangle[0]) > 0;
}
 
int main()
{
    std::cout<<is_inside({0.0f, 0.0f}, Triangle{
            FVector2D{1.0f, -1.0f}, FVector2D{0.0f, 1.0f}, FVector2D{-1.0f, -1.0f}
        });
}
2
0 / 0 / 0
Регистрация: 23.09.2018
Сообщений: 5
23.09.2018, 22:10  [ТС] 11
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
#include <iostream>
#include <math.h>
#include <iomanip>
 
using namespace std;
 
float X1, X2, X3, Y1, Y2, Y3; // координаты треугольника ABC
float X, Y; // координаты точки P
 
float AB, AC, BC; // длины отрезков треугольника ABC
float PA, PB, PC; // длины отрезков из точки P
 
float APB, APC, BPC; // углы у вершины P
 
int main()
{
  setlocale(0, "");
 
  cout << "Введите X1 :";
  cin >> X1;
  cout << "Введите Y1 :";
  cin >> Y1;
  cout << "Введите X2 :";
  cin >> X2;
  cout << "Введите Y2 :";
  cin >> Y2;
  cout << "Введите X3 :";
  cin >> X3;
  cout << "Введите Y3 :";
  cin >> Y3;
  cout << "Введите X :";
  cin >> X;
  cout << "Введите Y:";
  cin >> Y;
 
  AB = sqrt(pow((X1 - X2), 2) + pow((Y1 - Y2), 2));
  AC = sqrt(pow((X1 - X3), 2) + pow((Y1 - Y3), 2));
  BC = sqrt(pow((X2 - X3), 2) + pow((Y2 - Y3), 2));
  // ----------------------------------------
  PA = sqrt(pow((X - X1), 2) + pow((Y - Y1), 2));
  PB = sqrt(pow((X - X2), 2) + pow((Y - Y2), 2));
  PC = sqrt(pow((X - X3), 2) + pow((Y - Y3), 2));
 
  cout << endl << AB << endl << AC << endl << BC << endl;
  cout << endl << PA << endl << PB << endl << PC << endl;
  // ----------------------------------------------
  APB = acos((pow(PB, 2) + pow(PA, 2) - pow(AB, 2)) / (2 * PA*PB));
  APC = acos((pow(PC, 2) + pow(PA, 2) - pow(AC, 2)) / (2 * PA*PC));
  BPC = acos((pow(PB, 2) + pow(PC, 2) - pow(BC, 2)) / (2 * PC*PB));
 
  cout << endl << APB << endl << APC << endl << BPC << endl;
  // ----------------------------------------
  double Summ = (APB + APC + BPC);// сумма углов у вершины P
  cout << endl << Summ << endl;
 
  cout << fixed;               // оставляем два знака после запятой
  cout << setprecision(2);
  cout << endl << Summ << endl;
  int Summ1 = (Summ / 2) * 100; // приводим к int
 
  cout << endl << Summ1 << endl;
 
  // -----------------------------------
  switch (Summ1)
  {
  case 314:
 
    cout << endl << "YES!" << endl;
    break;
 
  default:
    cout << endl << "NO!" << endl;
  }
}
Тут друг помог с кодом.Теперь можете мне расписать что именно тут происходит поэтапно. А то я в геометрии профан, и желательно название темы в геометрии что-бы почитать.
0
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
23.09.2018, 22:31 12
Цитата Сообщение от ImmortalReaper Посмотреть сообщение
acos((pow(PB, 2) + pow(PA, 2) - pow(AB, 2)) / (2 * PA*PB));
Если возможно, в геометрии такого надо избегать.
1
0 / 0 / 0
Регистрация: 23.09.2018
Сообщений: 5
23.09.2018, 22:44  [ТС] 13
Ну это в геометрии)) А это алгоритм к тому же рабочий.
0
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
23.09.2018, 22:55 14
Цитата Сообщение от ImmortalReaper Посмотреть сообщение
рабочий.
Да, приведение 100*pi к int - прием остроумный... Правда, если точка вне и близко к одной из сторон тоже не поможет...
0
0 / 0 / 0
Регистрация: 23.09.2018
Сообщений: 5
23.09.2018, 23:29  [ТС] 15
Я уже проверял что будет если точка вне и близко к одной из сторон. То алгоритм выдает NO!(она за треугольником).

Добавлено через 25 минут
А можно пожалуйста более подробно описать как тут происходит расчёт и как оно понимает точка внутри триугольника или снаружи(мне это важно узнать что-бы понять как происходит расчёт)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
double Summ = (APB + APC + BPC);// сумма углов у вершины P
  cout << endl << Summ << endl;
 
  cout << fixed;               // оставляем два знака после запятой
  cout << setprecision(2);
  cout << endl << Summ << endl;
  int Summ1 = (Summ / 2) * 100; // приводим к int
 
  cout << endl << Summ1 << endl;
 
  // -----------------------------------
  switch (Summ1)
  {
  case 314:
 
    cout << endl << "YES!" << endl;
    break;
 
  default:
    cout << endl << "NO!" << endl;
  }
}
0
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
23.09.2018, 23:55 16
ImmortalReaper, проблема в том, что лично мне пытаться понять чужой код лень.
Тем более, что он что-то непонятное делает.

Вот мой код делает именно то, что описывал Байт, по приведённой мной формуле.
Он прост для понимания, вычисляется намного быстрее.
1
23.09.2018, 23:55
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
23.09.2018, 23:55
Помогаю со студенческими работами здесь

Определение принадлежности точки треугольнику
Написать программу определения принадлежности точки треугольника

Определение принадлежности точки треугольнику
Заранее спасибо.

Определение принадлежности точки задаваемому треугольнику
Задаем координаты вершин треугольника на координатной плоскости. Затем находим длину этих сторон....

Программа определения принадлежности точки треугольнику
Составить алгоритм определения принадлежности (x;y) внутренней части треугольника с заданными...


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

Новые блоги и статьи
Как скрыть клавиатуру на Android
hw_wired 24.01.2025
При разработке Android-приложений часто возникает необходимость управлять видимостью экранной клавиатуры для улучшения пользовательского опыта. Одним из наиболее эффективных способов контроля. . .
Как обучить нейросеть создания картинок на Python
bytestream 24.01.2025
В эпоху цифровых технологий искусственный интеллект становится неотъемлемой частью творческого процесса. Особое место в этой области занимает разработка и обучение нейронных сетей для создания. . .
Как обучить нейросеть генерации текста на Python
bytestream 24.01.2025
В современном мире искусственный интеллект и машинное обучение становятся неотъемлемой частью многих технологических решений. Одной из наиболее интересных и востребованных задач в этой области. . .
Машинное обучение на Python
bytestream 24.01.2025
Введение в машинное обучение на Python Машинное обучение представляет собой одну из наиболее динамично развивающихся областей информационных технологий, которая позволяет компьютерным системам. . .
Как удалить вирус-майнер с компьютера
hw_wired 24.01.2025
Вирусы-майнеры стали одной из наиболее серьезных угроз для пользователей компьютеров. Эти вредоносные программы тайно используют вычислительные ресурсы зараженного устройства для добычи криптовалюты. . .
Что такое веб-сервер, для чего он нужен и как работает
bytestream 24.01.2025
В современную эпоху цифровых технологий веб-сервер является фундаментальным компонентом интернет-инфраструктуры, обеспечивающим функционирование множества онлайн-сервисов и веб-сайтов. Этот. . .
Как в цикле for перебрать все элементы в словаре в Python
bytestream 24.01.2025
Словари в Python представляют собой мощные структуры данных, которые позволяют хранить информацию в формате ключ-значение. Эта особенность делает их незаменимыми при работе с данными, где требуется. . .
Как отменить rebase в Git
hw_wired 24.01.2025
Git rebase представляет собой мощный инструмент для управления историей коммитов в системе контроля версий Git. Этот механизм позволяет разработчикам изменять последовательность, комбинировать или. . .
Как поменять цвет input placeholder с помощью CSS
bytestream 24.01.2025
В веб-разработке оформление элементов пользовательского интерфейса играет ключевую роль в создании привлекательного и интуитивно понятного дизайна. Особое внимание уделяется формам ввода данных, где. . .
Как перебрать все значения в перечислении (enum) в C#
bytestream 24.01.2025
Перечисление (enum) в языке программирования C# представляет собой специальный тип данных, который позволяет определить набор именованных констант. Этот мощный инструмент особенно полезен, когда. . .
Как обойтись без проверки на null, чтобы избежать NullPointerExce­ption в Java
bytestream 24.01.2025
NullPointerException (NPE) является одним из самых распространенных исключений в Java, создающих серьезные проблемы при разработке программного обеспечения. Данное исключение возникает при попытке. . .
Что лучше использовать в href ссылок в JavaScript: "#" или "javascript:voi­­d(0)­"
bytestream 24.01.2025
При разработке веб-приложений важную роль играет правильное использование HTML-ссылок в сочетании с JavaScript. Одним из ключевых аспектов является выбор корректного значения атрибута href для. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru