Diskuze: bod v trojúhelníku

C++ C a C++ bod v trojúhelníku

Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Zdeněk Pavlátka:

Nevěděl by někdo, jak napsat funkci která by kontrolovala, jestli zadaný bod leží uvnitř trojúhelníku?

Odpovědět 24.3.2013 15:04
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Odpovídá na Zdeněk Pavlátka
Lukáš Hruda (Luckin):

Tohle je na mě moc matematika, ale dělal bych to asi pomocí odchylek vektorů.

 
Nahoru Odpovědět 24.3.2013 15:17
Avatar
expoox
Redaktor
Avatar
expoox:

asi by som na to siel podobne, mozno polroviny cez vektory, teda ak lezi bod od strany AC na lavo a zaroven od strany AB hore tak patri trojuholniku alebo nieco v tom zmysle

 
Nahoru Odpovědět 29.3.2013 22:16
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Zdeněk Pavlátka
David Čápka:

Mám to v Delphi, si to uprav :P

function spoctivektor(a1,a2,b1,b2: real): tvektor;
var vektor: tvektor;
begin
  vektor.a1:=b1 - a1;
  vektor.a2:=b2 - a2;
  spoctivektor:=vektor;
end;

// vrátí true, pokud leží bod v trojúhelníku
// počítá s faktem, že když leží bod v trujúhelníku, dá součet úhlů vektorů mezi tímto bodem a vrcholy troúhelníku 360 stupňů
function bodvtrojuhelniku(a1, a2, b1, b2, c1, c2, x1, x2: real): boolean;
var vektor1, vektor2, vektor3: tvektor;
    lezi: boolean;
    soucet: real;
begin
  vektor1:=spoctivektor(a1,a2,x1,x2);
  vektor2:=spoctivektor(b1,b2,x1,x2);
  vektor3:=spoctivektor(c1,c2,x1,x2);
  lezi:=false;
  soucet:=uhelvektoru(vektor1, vektor2) + uhelvektoru(vektor2, vektor3) + uhelvektoru(vektor3, vektor1);
  if (soucet = 360) then
  lezi:=true;
  bodvtrojuhelniku:=lezi;
end;

// vrátí true, pokud leží trojúhelník DEF v trojúhelníku ABC
// aby trojúhelník ležel celý v druhém,  musí v něm ležet každý jeho vrchol
function trojuhelnikvtrojuhelniku(a1, a2, b1, b2, c1, c2, d1, d2, e1, e2, f1, f2: real): boolean;
var lezi: boolean;
begin
  if bodvtrojuhelniku(a1,a2,b1,b2,c1,c2,d1,d2) and
     bodvtrojuhelniku(a1,a2,b1,b2,c1,c2,e1,e2) and
     bodvtrojuhelniku(a1,a2,b1,b2,c1,c2,f1,f2) then
  lezi:=true else lezi:=false;
  trojuhelnikvtrojuhelniku:=lezi;
end;
Nahoru Odpovědět 30.3.2013 7:21
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
expoox
Redaktor
Avatar
expoox:

ja som mal na mysli nieco taketo:

function bvt(a1,a2,b1,b2,c1,c2,m1,m2:integer):Boolean; //bodu M zistujeme ci patri 3u
var a,b,c:integer;
begin
  a:=(b2-c2)*m1+(c1-b1)*m2-((b2-c2)*b1+(c1-b1)*b2);
  b:=(a2-c2)*m1+(c1-a1)*m2-((a2-c2)*a1+(c1-a1)*a2);
  c:=(a2-b2)*m1+(b1-a1)*m2-((a2-b2)*a1+(b1-a1)*a2);

  if ((a>0) and (b<0) and (c>0)) then
    result:=true
  else
    result:=false;
end;

procedure TForm1.Button1Click(Sender: TObject);
var bod :boolean;
begin
  bod:=bvt(strtoint(edit1.text),strtoint(edit2.text),strtoint(edit3.text),strtoint(edit4.text),strtoint(edit5.text),strtoint(edit6.text),strtoint(edit7.text),strtoint(edit8.text));
  if bod then
    label1.caption:='bod patri trojuholniku'
  else
    label1.caption:='bod nepatri trojuholniku';
end;

ale sdraco-ve riesenie sa mi paci viac

Editováno 30.3.2013 9:54
 
Nahoru Odpovědět 30.3.2013 9:52
Avatar
Odpovídá na Zdeněk Pavlátka
Lukáš Hruda (Luckin):
#include <math.h>

struct Point
{
  double x;
  double y;
  Point(double X, double Y){x = X; y = Y;}
};

class Vector
{
  private:
    double x;
    double y;

  public:
    Vector(const Point &, const Point &);
    Vector(double,double,double,double);
    double operator*(const Vector & vector) const {return x * vector.x + y * vector.y;}
    double Size() const {return sqrt(x * x + y * y);}
    double Angle(const Vector & vector){return acos((*this * vector)/(Size() * vector.Size()));}
};

Vector::Vector(const Point & A, const Point & B)
{
  x = B.x - A.x;
  y = B.y - A.y;
}

Vector::Vector(double ax, double ay, double bx, double by)
{
  x = bx - ax;
  y = by - ay;
}


class Triangle
{
  private:
    Point a,b,c;

  public:
    Triangle() : a(0,0), b(0,0), c(0,0) {}
    Triangle(const Point & A, const Point & B, const Point & C) : a(A), b(B), c(C) {}
    Triangle(double ax, double ay, double bx, double by, double cx, double cy) : a(ax,ay), b(bx,by), c(cx,cy) {}
    bool IsIn(const Point &) const;
    bool IsIn(double x, double y) const {Point pt(x,y); return IsIn(pt);}
    //void Draw(BITMAP*) const;
};

bool Triangle::IsIn(const Point & p) const
{
  Vector ab = Vector(a,b);
  Vector ac = Vector(a,c);
  Vector ap = Vector(a,p);
  Vector ba = Vector(b,a);
  Vector bc = Vector(b,c);
  Vector bp = Vector(b,p);
  double ang_abac = ab.Angle(ac);
  double ang_babc = ba.Angle(bc);
  bool ABAC = ang_abac >= ab.Angle(ap) && ang_abac >= ac.Angle(ap);
  bool BABC = ang_babc >= ba.Angle(bp) && ang_babc >= bc.Angle(bp);
  return ABAC && BABC;
}

/*void Triangle::Draw(BITMAP* bitmap) const
{
  line(bitmap,(int)a.x,(int)a.y,(int)b.x,(int)b.y,0xff0000);
  line(bitmap,(int)b.x,(int)b.y,(int)c.x,(int)c.y,0xff0000);
  line(bitmap,(int)c.x,(int)c.y,(int)a.x,(int)a.y,0xff0000);
}*/

Vykomentovaná metoda Draw je pro allegro. Použití je jednoduché.

Point A = Point(34,12);
Point B = Point(257,102);
Point C = Point(129,430);
Triangle tr = Triangle(A,B,C); //nebo rovnou Triangle tr = Triangle(34,12,257,102,129,430);
...
Point pt = Point(120,215);
tr.IsIn(pt);  //vrátí true pokud je bod [120,215] uvnitř trojúhelníku, jinak false
tr.IsIn(120,215);  //nebo rovnou takto

K těm vektorům si klidně můžeš přidat další funkce, jako sčítání, odečítání a podobně.

Jinak ty bloky tříd by správně měly být v nějakém hlavičkovém souboru.

Editováno 30.3.2013 11:43
 
Nahoru Odpovědět 30.3.2013 11:41
Avatar
Lukáš Hruda (Luckin):

Teď mi došlo že to nebude fungovat pro bod ve vrcholu, protože vznikne nulový vektor. Je potřeba udělat menší úpravu.

struct Point
{
  double x;
  double y;
  Point(double X, double Y){x = X; y = Y;}
  bool operator==(const Point & p) const {return p.x == x && p.y == y;}
};

...

bool Triangle::IsIn(const Point & p) const
{
  if(p == a || p == b || p == c)
    return true;
  Vector ab = Vector(a,b);
  Vector ac = Vector(a,c);
  Vector ap = Vector(a,p);
  Vector ba = Vector(b,a);
  Vector bc = Vector(b,c);
  Vector bp = Vector(b,p);
  double ang_abac = ab.Angle(ac);
  double ang_babc = ba.Angle(bc);
  bool ABAC = ang_abac >= ab.Angle(ap) && ang_abac >= ac.Angle(ap);
  bool BABC = ang_babc >= ba.Angle(bp) && ang_babc >= bc.Angle(bp);
  return ABAC && BABC;
}
 
Nahoru Odpovědět 30.3.2013 14:27
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 7 zpráv z 7.