Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Точка в треугольнике

Точка в треугольнике

Страницы: 1 2 3 Следующая »
AutПостоялецwww4 мая 200613:18#0
Есть треугольник в декартовой системе координат (X, Y) и имеется точка. Нужно определить - попадает ли эта точка в данный треугольник. Как быть?
YzeerbНовичокwww4 мая 200613:38#1
Aut
Поискать по форуму неделю назад тема расматривалас!!!!!!!!!!
AutПостоялецwww4 мая 200613:40#2
Yzeerb
Хотя бы скажи как тема называлась!
WebErrAtorНовичокwww4 мая 200613:47#3
Учить линейную алгебру.
Определители и скалярное произведение.
ArthurПостоялецwww4 мая 200613:47#4
Я так проверяю:

Function PointInTriangle(px#,py#, ax#,ay#,bx#,by#,cx#,cy#)

        Local bc#,ca#,ab#,ap#,bp#,cp#,abc#
        bc# = bx*cy - by*cx
        ca# = cx*ay - cy*ax
        ab# = ax*by - ay*bx
        ap# = ax*py - ay*px
        bp# = bx*py - by*px
        cp# = cx*py - cy*px
        abc# = Sgn(bc + ca + ab)
        If (abc*(bc-bp+cp)>0) And (abc*(ca-cp+ap)>0) And (abc*(ab-ap+bp)>0) Return True

End Function

На свой язык думаю не составит труда переписать...

AutПостоялецwww4 мая 200613:56#5
Arthur
Несколько вопросов:
В каких переменных хранятся  координаты треугольника, а в каких координаты точки?
Что означает #?
И что такое Sgn?
Lion007Постоялецwww4 мая 200614:11#6
Aut
насколько помню ВАСИК - # - это признак, что число double
Sgn - функция, возвашающая знак числа - (-1) если меньше нуля, 1 - если больше и 0 если равно нулю

кусок кода примерно на ту же тему

//=============================================================================
// Modifyed barycentic coords :
// if U and V are modifyed barycentic coords for point P and triangle ABC
// P = (1-U-W) * A + U * B + V * C
// if P lies inside triangle :
//  U     >= 0
//  V     >= 0
//  U + V <= 1
void BarycentricCoords(const Vec2 * v, const Vec2 & pos, float & U, float & V)
{
  Vec2 a(v[1].x - v[0].x, v[1].y - v[0].y);
  Vec2 b(v[2].x - v[0].x, v[2].y - v[0].y);
  Vec2 p( pos.x - v[0].x,  pos.y - v[0].y);

  U = (p.y * b.x - p.x * b.y) / (a.y * b.x - a.x * b.y);
  V = (p.y * a.x - p.x * a.y) / (a.x * b.y - a.y * b.x);
}

// somewhere in code
  Vec2 ABC[3]; // our triangle
  Vec2 P; // our point
  // blah-blah
  float U, V;
  BarycentricCoords(ABC, P, U, V);
  // now U and V are our barycentric coords
  // fix rounding errors and check if point inside trinagle
  float eps = 1.0e-4f;
  if (fabs(U)   < eps) U = 0;
  if (fabs(U-1) < eps) U = 1;
  if (fabs(V)   < eps) V = 0;
  if (fabs(V-1) < eps) V = 1;
  if ((U >= 0) && (V >= 0) && ((U + V) <= 1))
  {
    // WOW! we are inside triangle
  } else
  {
    // WOW! we are outside
  }

AutПостоялецwww4 мая 200614:27#7
Lion007
Код почти понял, но все таки есть вопросы.
eps = 1.0e-4f это значит 1*10^(-4) или нет?
Что такое fabs?
&& - означает AND или OR?
doc.Постоялецwww4 мая 200614:39#8
>Поискать по форуму неделю назад тема расматривалас!!!!!!!!!!

=))  раз в две недели стабильно возникает.

A,B,C - точки треугольника, P - точка

N1 = (By-Ay)*(Px-Ax) - (Bx-Ax)*(Py-Ay);
N2 = (Cy-By)*(Px-Bx) - (Cx-Bx)*(Py-By);
N3 = (Ay-Cy)*(Px-Cx) - (Ax-Cx)*(Py-Cy);

Result = ((N1>0) and (N2>0)  and (N3>0)) or ((N1<0) and (N2<0) and (N3<0));

AutПостоялецwww4 мая 200614:47#9
doc.
Не большое уточнение:
Если условия
>(N1>0) and (N2>0) and (N3>0)
или
>(N1<0) and (N2<0) and (N3<0)
выполняются, то значит точка находится в треугольнике?
WebErrAtorНовичокwww4 мая 200614:48#10
doc.
Ай, молодца!
Хоть кто-то ещё определители 2х2 считать умеет! 8) 8) 8)
Lion007Постоялецwww4 мая 200614:58#11
Aut
1.0e-4f = (float)0.0001
fabs = абсолютная величина
&& = логическое AND
в принципе, если надо посчитать ТОЛЬКО попадание-непопадание точки в треугольник, то эти самые барицентрические координаты дают некий оверхед... зато если надо еще и посчитать некий параметр, задонный в вершинах треугольника, в этой точке - то самое оно.
doc.Постоялецwww4 мая 200615:03#12
Aut
если одинакового знака то внутри, если хоть одно число =0 то точка лежит на грани, в остальных случаях лежит вне треугольника.

Правка: если Result = true то внутри.

WebErrAtor
>Хоть кто-то ещё определители 2х2 считать умеет!
Почему 2x2?  3x3!!! =)) , векторное произведение однако ;)

AutПостоялецwww4 мая 200615:04#13
Спасибо всем!
Я и не знал, что существует так много способов.
doc.Постоялецwww4 мая 200615:19#14
Да, метод годится нетолько для треугольника но и для любого выпуклого многоугольника, только добавятся соответствующие N4, N5 и т.д.
Страницы: 1 2 3 Следующая »

/ Форум / Программирование игр / Графика

2001—2018 © GameDev.ru — Разработка игр