11 / 11 / 6
Регистрация: 19.01.2012
Сообщений: 195
Записей в блоге: 2
1

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

08.08.2017, 21:59. Показов 8693. Ответов 9
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Доброго дня
Сделал, используя формулу плоскости по двум точкам. Но либо не допонял что-то, либо не так сделал что-то.
Мне попались координаты, при которых программа говорит, что точка лежит на стороне треугольника, хотя это далеко не так. Вот кусок кода рассчётов:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int triangle::point_on_triangle(Point pt)
{
    // уравнение прямой по двум точкам. Если все три переменные одинакового знака, то точка внутри треугольника;
    // если одна из переменных == 0, то точка лежит на отрезке треугольника;
    // иначе точка вне треугольника
        // this->_triangle[0] - точка А
        // this->_triangle[1] - точка B
        // this->_triangle[2] - точка C
        // pt - проверяемая точка
    int _x = (pt.y - this->_triangle[0].y) * (this->_triangle[1].x - this->_triangle[0].x) - (this->_triangle[1].y - this->_triangle[0].y) * (pt.x - this->_triangle[0].x);
    int _y = (pt.y - this->_triangle[1].y) * (this->_triangle[2].x - this->_triangle[1].x) - (this->_triangle[2].y - this->_triangle[1].y) * (pt.x - this->_triangle[1].x);
    int _z = (pt.y - this->_triangle[2].y) * (this->_triangle[0].x - this->_triangle[2].x) - (this->_triangle[0].y - this->_triangle[2].y) * (pt.x - this->_triangle[2].x);
 
    if (_x == 0 || _y == 0 || _z == 0) // лежит на стороне треугольника
        return 0;
    else if ((_x > 0 && _y > 0 && _z > 0) || (_x < 0 && _y < 0 && _x < 0)) // лежит внутри треугольника
        return 1;
    return -1; // лежит вне треугольника
}

Так вот, при координатах pt(0,9), а _triangle((-6,-5),(-6,-3),(-5,-1)), программа говорит, что точка лежит на стороне треугольника. Подскажите, в чём ошибка? Спасибо заранее.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.08.2017, 21:59
Ответы с готовыми решениями:

принадлежность точки треугольнику
как определить принадлежность точки треугольнику?Если с векторами,то объясните получше.Венктора не...

Принадлежность точки многоугольнику
Хочу разобраться с алгоритмом нахождения точки в многоугольнике. Алгоритм нашел здесь. В общем, для...

Принадлежность точки многоугольнику
зная координаты вершин нужно определить принадлежность точки фигуре. количество вершин может быть...

с++ принадлежность точки квадрату
как определить принадлежность точки квадрату по координатам.Объясните человеку,который еще не знает...

9
Айлурофил
440 / 374 / 107
Регистрация: 27.05.2017
Сообщений: 2,146
Записей в блоге: 1
09.08.2017, 00:32 2
Вот рабочий алгоритм:
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//  1 - Внутри треугольника
// -1 - Вне треугольника
//  0 - На границе
//
function InTriangle(const x,y:array of double;Tria:TPoly;x1,y1:double):integer;
var a,b,c:Extended;
begin
a:=(x[Tria.p[0]]-x1)*(y[Tria.p[1]]-y[Tria.p[0]])-(x[Tria.p[1]]-x[Tria.p[0]])*(y[Tria.p[0]]-y1);
b:=(x[Tria.p[1]]-x1)*(y[Tria.p[2]]-y[Tria.p[1]])-(x[Tria.p[2]]-x[Tria.p[1]])*(y[Tria.p[1]]-y1);
c:=(x[Tria.p[2]]-x1)*(y[Tria.p[0]]-y[Tria.p[2]])-(x[Tria.p[0]]-x[Tria.p[2]])*(y[Tria.p[2]]-y1);
if (Abs(a)<0.00001) and (((b<0) and (c<0)) or ((b>0) and (c>0))) then begin Result:=0;exit;end;
if (Abs(b)<0.00001) and (((a<0) and (c<0)) or ((a>0) and (c>0))) then begin Result:=0;exit;end;
if (Abs(c)<0.00001) and (((a<0) and (b<0)) or ((a>0) and (b>0))) then begin Result:=0;exit;end;
if ((a>=0) and (b>=0) and (c>=0)) or ((a<0) and (b<0) and (c<0)) then Result:=1 else Result:=-1;
end;
1
11 / 11 / 6
Регистрация: 19.01.2012
Сообщений: 195
Записей в блоге: 2
09.08.2017, 01:31  [ТС] 3
Добавил проверку на попадания в границы отрезка, ибо, оказывается, эта точка вылетала за границы отрезка. Сначала были расхождения, но после добавил проверку на горизонтальные и вертикальные отрезки. Вроде работает. Вот код проверки:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool point_on_line(int x , int y, int x1, int x2, int y1, int y2)
{
// x и y - искомая точка
// x1 и y1 - начало отрезка
// x2 и y2 - коне отрезка (как в формуле о прямой по двум точкам)
    if (x1 == x2 || y1 == y2)
    {
        if (((x <= x2 && x >= x1) || (x >= x2 && x <= x1)) && ((y <= y2 && y >= y1) || (y >= y2 && y <= y1)))
            return true;
    }
    if (((x < x2 && x > x1) || (x > x2 && x < x1)) && ((y < y2 && y > y1) || (y > y2 && y < y1)))
        return true;
    return false;
}
Massaraksh7
Потестил, у вас с вещественными числами даже. А у меня целые Мне проще.
0
1471 / 826 / 140
Регистрация: 12.10.2013
Сообщений: 5,456
09.08.2017, 19:04 4
Как проверить принадлежит ли точка треугольнику?
0
11 / 11 / 6
Регистрация: 19.01.2012
Сообщений: 195
Записей в блоге: 2
09.08.2017, 19:48  [ТС] 5
По данной ссылке была такая же проблема, программа определяла, точка лежит в или вне треугольнике, но не на его грани.
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
10.08.2017, 21:47 6
Цитата Сообщение от Lagos Посмотреть сообщение
По данной ссылке была такая же проблема, программа определяла, точка лежит в или вне треугольнике, но не на его грани
В процессорах нет бесконечной точности вещественных вычислений. Поэтому практически никогда не возможно определить факт нахождения точки на грани треугольника. Т.е. понятие "на грани" в компьютерных вычисления существует только в пределах погрешности

Добавлено через 3 минуты
А вообще, есть такая вещь, как барицентрические координаты. В 3д-графике их используют как раз для этих целей - определения, находится ли точка внутри реугольника
1
11 / 11 / 6
Регистрация: 19.01.2012
Сообщений: 195
Записей в блоге: 2
10.08.2017, 21:55  [ТС] 7
как барицентрические координаты.
Спасибо, ушёл искать литературу.
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
10.08.2017, 22:08 8
Собственно, вот выдранный отсюда код на Си++. Там же написано на пальцах, что такое барицентрические координаты (хотя мне, как не математику, это было плохо понятно)

C++
template <typename T> vec<3,T> cross(vec<3,T> v1, vec<3,T> v2) {
    return vec<3,T>(v1.y*v2.z - v1.z*v2.y, v1.z*v2.x - v1.x*v2.z, v1.x*v2.y - v1.y*v2.x);
}
 
Vec3f barycentric(Vec2i *pts, Vec2i P) {
    Vec3f u = cross(Vec3f(pts[2][0]-pts[0][0], pts[1][0]-pts[0][0], pts[0][0]-P[0]), Vec3f(pts[2][1]-pts[0][1], pts[1][1]-pts[0][1], pts[0][1]-P[1]));
    if (std::abs(u[2])<1) return Vec3f(-1,1,1); // triangle is degenerate, in this case return smth with negative coordinates
    return Vec3f(1.f-(u.x+u.y)/u.z, u.y/u.z, u.x/u.z);
}
Vec2i - вектор из двух int'ов (в твоём случае это будут float'ы)
Vec3f - вектор из трёх float'ов
Параметр "Vec2i *pts" - это массив из трёх точек, каждая точка - это 2d-координаты треугольника
Параметр "Vec2i P" - это точка (2d-координаты треугольника), для которой надо понять, внутри она или снаружи
cross - функция вычисления векторного произведения

На выходе функции - барицентрические координаты точки P в системе координат треугольника. Это набор из трёх чисел. Если в этом наборе хотя бы одно из чисел меньше нуля, то точка P находится вне треугольника

Добавлено через 51 секунду
Хотя в итоге получается вроде бы как то же самое, что и код из поста #2

Добавлено через 31 секунду
Правда в совокупности с теорией тут можно реально понять, что делается, а не просто содрать код
1
11 / 11 / 6
Регистрация: 19.01.2012
Сообщений: 195
Записей в блоге: 2
10.08.2017, 22:30  [ТС] 9
Evg, большое спасибо, никогда и не слышал о таком...Код полностью понятен. А про стороны решу вопрос используя погрешность.
0
Айлурофил
440 / 374 / 107
Регистрация: 27.05.2017
Сообщений: 2,146
Записей в блоге: 1
11.08.2017, 06:21 10
Цитата Сообщение от Evg Посмотреть сообщение
В процессорах нет бесконечной точности вещественных вычислений. Поэтому практически никогда не возможно определить факт нахождения точки на грани треугольника. Т.е. понятие "на грани" в компьютерных вычисления существует только в пределах погрешности
Теоретически - да. С практической точки зрения во многих случаях нужно знать, находится ли точка достаточно близко к стороне, например, при триангуляции, чтобы изменить конфигурацию разбивки.
0
11.08.2017, 06:21
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.08.2017, 06:21
Помогаю со студенческими работами здесь

Алгоритм на принадлежность точки стороне
Нужен алгоритм на принадлежность точки стороне многоугольника. Имеются координаты вершин...

Определить принадлежность точки замкнутой 3D области
Здравствуйте. Как определить находится ли точка внутри замкнутой односвязной 3D области?...

Принадлежность точки треугольнику
Нужно сделать программу, в которой при 3х кликах на форму (в разных местах) эти 3 точки соединялись...

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


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

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

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