Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C++ Builder > Как определить попала ли точка в треугольник

Автор: BOB4uK 16.6.2008, 17:55

Есть треугольник координаты вершин которого известны! И есть точка с координатами Х и У!
Как определить попала ли точка в треугольник?

Автор: Jorjio 16.6.2008, 18:04

Геометрия
Плоскость определена 3-мя прямыми. Идешь далле к принадлежности точки плоскости.
Думаю изобретать велосипед не стоит, открой справочник по математике.

Автор: BOB4uK 16.6.2008, 18:47

Пожалуйста пишите по существу, а не размазано, например пользуйся гуглем...

Автор: jonie 16.6.2008, 19:34

Возможны два варианта взаимного расположения точки и плоскости, ограниченной кривой: либо точка принадлежит плоскости, либо нет. Три точки задают плоскость тогда, и только тогда, когда они попарно различны, и не лежат на одной прямой
точка= (x,y,z)
обозначим плоскость как : $(xp_i, yp_i, zp_i), i=1..3$
уравнение плоскости : $ ax+by+cz = d $
где
\begin{eqnarray*}
a &=& (yp_2 -yp_1 )(zp_3 -zp_1 ) - (yp_3 -yp_1 )(zp_2 -zp_1 ); \\
b &=& -(xp_2 -xp_1 )(zp_3 -zp_1 ) + (xp_3 -xp_1 )(zp_2 -zp_1 ); \\
c &=& (xp_2 -xp_1 )(yp_3 -yp_1 ) - (xp_3 -xp_1 )(yp_2 -yp_1 ); \\
d &=& xp_1 a+yp_1 b+zp_1 c
\end{eqnarray*}
остается только проверить удовлетворяет ли (x,y,z) приведенному уравнению.

Автор: BOB4uK 19.6.2008, 04:19

Если чесно нифига не понятно! а треугольник плоский, координата Z не нужна!

Автор: ksili 19.6.2008, 06:13

BOB4uK, а мне непонятно при чём тут Builder. Если непонятен алгоритм решения задачи, задавай вопрос в форуме по алгоритмам.

Цитата(BOB4uK @ 19.6.2008, 08:19

)

а треугольник плоский, координата Z не нужна!

Ну так подставь z=0

Цитата(jonie @ 16.6.2008, 23:34

)

остается только проверить удовлетворяет ли (x,y,z) приведенному уравнению.

Там не уравнение должно быть, а система неравенств

Автор: Mayk 19.6.2008, 06:32

Цитата(BOB4uK @ 19.6.2008, 08:19

)

Если чесно нифига не понятно! а треугольник плоский, координата Z не нужна!

Доступное описание алгоритма есть в Кормене et al.

Цитата(ksili @ 19.6.2008, 10:13

)

BOB4uK, а мне непонятно при чём тут Builder.

Кстати неалгоритмиеческое решение на WinAPI может подразумевать использование
ф-ций CreatePolygonRgn + PtInRegion.

Автор: BOB4uK 19.6.2008, 15:24

Цитата(Mayk @ 19.6.2008, 06:32)

Доступное описание алгоритма есть в Кормене et al.

Это где?

Автор: Walker 20.6.2008, 08:03

Цитата

Пожалуйста пишите по существу, а не размазано, например пользуйся гуглем...

А по существу - в "Центр помощи" с такими вопросами и наездами. http://smiles2k.net/angry_smiles/index.html
В Google, кстати, ответ на этот вопрос обнаруживается в течение пяти секунд.

Хинт - точка находится в треугольнике, если площадь исходного треугольника равна сумме площадей треугольников, образованных каждой из сторон треугольника и "проблемной" точкой. Всё!
ABC - треугольник, D - точка
SABC = SABD + SACD + SBCD.
Задача решается комбинацией трёх функций.
1. Сравнение площадей.
2. Нахождение площади по трём сторонам по http://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%93%D0%B5%D1%80%D0%BE%D0%BD%D0%B0.
3. Нахождение длины отрезка по двум точкам.
Функции приведены в последовательности, выводимой из логического рассуждения.

Удачи!
ИМХО, тему можно закрывать!

Автор: Dmi3ev 20.6.2008, 12:12

Walker правильно говорит, что-то типа этого

Код


//---------------------------------------------------------------------------

#include <vcl.h>
#include <mypoint.h>
#include <mysegment.h>
#pragma hdrstop

#include "tr_U.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
long double SGeron (MySeg a, MySeg b, MySeg c)
{
 long double p=(a.Length()+b.Length()+c.Length())/2;
 return sqrt(p*(p-a.Length())*(p-b.Length())*(p-c.Length()));
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
MyPoint A(1,2), B(2,8), C(1,6);
MyPoint P(1,1);
MySeg AB(A,B), BC(B,C), AC(A,C);
MySeg AP(A,P), BP(B,P), CP(C,P);
long double s, s1, s2, s3;
s=SGeron(AB, BC, AC);
s1=SGeron (AB, AP, BP);
s2=SGeron (BC, BP, CP);
s3=SGeron (AC, AP, CP);
if ((s1+s2+s3)>s)
 MessageBox(NULL, "Точка вне треугольника!", "Сообщение", MB_OK);
else
 MessageBox(NULL, "Точка внутри треугольника!", "Сообщение", MB_OK);
Edit1->Text=FloatToStr(s);
Edit2->Text=FloatToStr(s1);
Edit3->Text=FloatToStr(s2);
Edit4->Text=FloatToStr(s3);
}
//---------------------------------------------------------------------------

создал класс точки MyPoint
вот текст mypoint.h

Код


#ifndef MYPOINT_H
#define MYPOINT_H
class MyPoint
{
public:
MyPoint(double a=0.0, double b=0.0){x=a; y=b;};
void Set(double a, double b){x=a; y=b;};
double Getx(){return x;};
double Gety(){return y;};
~MyPoint(){};
private:
double x, y;
};
#endif

создал класс отрезка
вот текст mysegment.h

Код


#include <mypoint.h>
#include <math.h>
#define XX(x) ((x)*(x))
class MySeg
{
public:
 MySeg (MyPoint A, MyPoint B)
  {
   p1=A; p2=B;
  };
 void Set (MyPoint A, MyPoint B)
  {
   p1=A; p2=B;
  };
 long double Length ()
  {
   return sqrt(XX(p1.Gety()-p2.Gety())+XX(p1.Getx()-p2.Getx()));
  };
 ~MySeg (){};
private:
 MyPoint p1, p2;
};

я все делал быстро, но должно работать

Автор: Mayk 20.6.2008, 12:55

Цитата(BOB4uK @ 19.6.2008, 19:24

)

Это где?

http://www.ozon.ru/context/detail/id/2429691/

Автор: BOB4uK 20.6.2008, 16:02

Спасибо!