1 | ||||||
Принадлежность точки треугольнику08.08.2017, 21:59. Показов 8693. Ответов 9
Метки нет (Все метки)
Доброго дня
Сделал, используя формулу плоскости по двум точкам. Но либо не допонял что-то, либо не так сделал что-то. Мне попались координаты, при которых программа говорит, что точка лежит на стороне треугольника, хотя это далеко не так. Вот кусок кода рассчётов: Кликните здесь для просмотра всего текста
Так вот, при координатах pt(0,9), а _triangle((-6,-5),(-6,-3),(-5,-1)), программа говорит, что точка лежит на стороне треугольника. Подскажите, в чём ошибка? Спасибо заранее.
0
|
08.08.2017, 21:59 | |
Ответы с готовыми решениями:
9
принадлежность точки треугольнику Принадлежность точки многоугольнику Принадлежность точки многоугольнику с++ принадлежность точки квадрату |
Айлурофил
|
||||||
09.08.2017, 00:32 | 2 | |||||
Вот рабочий алгоритм:
1
|
09.08.2017, 01:31 [ТС] | 3 | |||||
Добавил проверку на попадания в границы отрезка, ибо, оказывается, эта точка вылетала за границы отрезка. Сначала были расхождения, но после добавил проверку на горизонтальные и вертикальные отрезки. Вроде работает. Вот код проверки:
Потестил, у вас с вещественными числами даже. А у меня целые Мне проще.
0
|
1471 / 826 / 140
Регистрация: 12.10.2013
Сообщений: 5,456
|
|
09.08.2017, 19:04 | 4 |
0
|
10.08.2017, 21:47 | 6 |
В процессорах нет бесконечной точности вещественных вычислений. Поэтому практически никогда не возможно определить факт нахождения точки на грани треугольника. Т.е. понятие "на грани" в компьютерных вычисления существует только в пределах погрешности
Добавлено через 3 минуты А вообще, есть такая вещь, как барицентрические координаты. В 3д-графике их используют как раз для этих целей - определения, находится ли точка внутри реугольника
1
|
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); } Vec3f - вектор из трёх float'ов Параметр "Vec2i *pts" - это массив из трёх точек, каждая точка - это 2d-координаты треугольника Параметр "Vec2i P" - это точка (2d-координаты треугольника), для которой надо понять, внутри она или снаружи cross - функция вычисления векторного произведения На выходе функции - барицентрические координаты точки P в системе координат треугольника. Это набор из трёх чисел. Если в этом наборе хотя бы одно из чисел меньше нуля, то точка P находится вне треугольника Добавлено через 51 секунду Хотя в итоге получается вроде бы как то же самое, что и код из поста #2 Добавлено через 31 секунду Правда в совокупности с теорией тут можно реально понять, что делается, а не просто содрать код
1
|
Айлурофил
|
|
11.08.2017, 06:21 | 10 |
Теоретически - да. С практической точки зрения во многих случаях нужно знать, находится ли точка достаточно близко к стороне, например, при триангуляции, чтобы изменить конфигурацию разбивки.
0
|
11.08.2017, 06:21 | |
11.08.2017, 06:21 | |
Помогаю со студенческими работами здесь
10
Алгоритм на принадлежность точки стороне Определить принадлежность точки замкнутой 3D области Принадлежность точки треугольнику Принадлежность точки к треугольнику Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |