Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: bod v trojúhelníku

V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity
Avatar
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.
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Zdeněk Pavlátka
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
Avatar
expoox
Tvůrce
Avatar
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
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Zdeněk Pavlátka
David Hartinger:30.3.2013 7:21

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
New kid back on the block with a R.I.P
Avatar
expoox
Tvůrce
Avatar
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
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Zdeněk Pavlátka
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
Avatar
Lukáš Hruda
Tvůrce
Avatar
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
Avatar
Petr M
Člen
Avatar
Odpovídá na David Hartinger
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
Avatar
JerryM
Člen
Avatar
Odpovídá na Zdeněk Pavlátka
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
Avatar
Odpovídá na Zdeněk Pavlátka
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
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Michal Hadraba
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
Avatar
Odpovídá na DarkCoder
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
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Michal Hadraba
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
Avatar
Odpovídá na DarkCoder
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
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Michal Hadraba
DarkCoder:14.9.2023 16:45

Tak třeba:

  1. Pomocí barymetrických souřadnic
  2. Pomocí srovnání obsahu subtrojúhelníků
  3. Pomocí prusečiků se stranami
  4. 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
Avatar
Peter Mlich
Člen
Avatar
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
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 16 zpráv z 16.