Diskuze: bod v trojúhelníku

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:24.3.2013 15:04

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.

Lukáš Hruda

Tvůrce

Lukáš Hruda:24.3.2013 15:17

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

Nahoru Odpovědět

24.3.2013 15:17

expoox

Tvůrce

expoox:29.3.2013 22:16

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

David Hartinger

Vlastník

David Hartinger:30.3.2013 7:21

Mám to v Delphi, si to uprav

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

New kid back on the block with a R.I.P

expoox

Tvůrce

expoox:30.3.2013 9:52

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

Lukáš Hruda

Tvůrce

Lukáš Hruda:30.3.2013 11:41

#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

Lukáš Hruda

Tvůrce

Lukáš Hruda:30.3.2013 14:27

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

Petr M

Člen

Petr M:28.8.2023 14:24

Možná mi něco uniklo, ale mám pocit, že ve funkci "bodvtrojuhelniku" mi ještě chybí ověření, že žádný z úhlů, tvořených testovaným bodem a vrcholy trojúhelníku, není větší než 180°. Součet úhlů bude vždy 360, ať je bod uvnitř nebo vně trojúhelníku, ale žádný z úhlů nesmí být větší než 180°. Pokud je některý z úhlů roven 180°, potom leží testovaný bod na hraně trojúhelníku, resp. spojnici dvou vrcholů.

Nahoru Odpovědět

28.8.2023 14:24

JerryM

Člen

JerryM:8.9.2023 10:24

tady najdeš v týhle knížce odpověď
https://www.knihydobrovsky.cz/…ce-414784133
dělá se to tak, že určíš zda bod leží vpravo nebo vlevo od přímky takže dostaneš + nebo - a to uděláš pro všechny 3 přímky na kterých leží úsešky trojuhelníku.

Nahoru Odpovědět

8.9.2023 10:24

Michal Hadraba

Člen

Michal Hadraba:14.9.2023 10:55

Funguje to obecně na uzavřenou polyline (uzavřená křivka neboli mnohoúhelník).
Pokud bod neleží na některé ze stran trojůhelníku (nebo na některé ze stran polyline), tak jakákoli polopřímka z bodu někam (libovolným směrem) má buďto jeden průsečík (v případě polyline jeden nebo "n" průsečíků, přičemž "n" je liché číslo) - potom bod LEŽÍ uvnitř, v opačném případě (0 nebo sudý počet průsečíků) leží mimo.
U "divných" mnoho úhelníků (třeba hvězda) mohou nastat případy, že ta polopřímka bude kolineární s nějakou stranou, i když bod neleží na žádné straně, ale to pro trojúhelník nehrozí. To se musí ošetřit zvlášť. V případě zájmu namaluju.

Nahoru Odpovědět

14.9.2023 10:55

DarkCoder

Člen

DarkCoder:14.9.2023 16:06

Pozor na to, i bod nacházející se uvnitř trojúhelníku, který neleží na stranách trojúhelníku, může mít při vytažení polopřímky "někam" 2 prusečíky. Taková situace může nastat prochází-li polopřímka jedním z vrcholů trojúhelníku.

Nahoru Odpovědět

14.9.2023 16:06

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Michal Hadraba

Člen

Michal Hadraba:14.9.2023 16:09

Na ja. Tak prověřit, zda neleží vrchol na polopřímce a kdyžtak jí udělat jinam.

Nahoru Odpovědět

14.9.2023 16:09

DarkCoder

Člen

DarkCoder:14.9.2023 16:33

To bys samozřejmě mohl. Jen se obávám, že těch pomocných výpočtů je přespříliš a že tak efektivita algoritmu nebude bůhvíjaká. Naštěstí těch algoritmů jsou mraky.. :-)

Nahoru Odpovědět

14.9.2023 16:33

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Michal Hadraba

Člen

Michal Hadraba:14.9.2023 16:37

no a máš nějaký pěknej? Pro mnohoúhelník by mě zajímal. pro ten trojúhelník je to o dost jednodušší, samozřejmě.

Nahoru Odpovědět

14.9.2023 16:37

DarkCoder

Člen

DarkCoder:14.9.2023 16:45

Tak třeba:

Pomocí barymetrických souřadnic
Pomocí srovnání obsahu subtrojúhelníků
Pomocí prusečiků se stranami
Pomocí orientace směrových vektorů

...

Nahoru Odpovědět

14.9.2023 16:45

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Peter Mlich

Člen

Peter Mlich:15.9.2023 7:59

Potrebujes rovnici pro konstrukci primky ze dvou bodu.
Trojuhelnik ABC
Vektor XA, XB, XC, YA, YB, YC
Vektor XY
Pokud je XY rovnobezny s AX a s AY nebo BX, BY nebo CX, CY, tak jde o prusecik s jednim vrcholu, ne?

Nahoru Odpovědět

15.9.2023 7:59

Nejčastěji vyhledáváné

Diskuze: bod v trojúhelníku