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.

Tvůrce

Zobrazeno 16 zpráv z 16.
//= Settings::TRACKING_CODE_B ?> //= Settings::TRACKING_CODE ?>
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
Tohle je na mě moc matematika, ale dělal bych to asi pomocí odchylek vektorů.
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;
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
#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.
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;
}
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ů.
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.
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.
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.
Na ja. Tak prověřit, zda neleží vrchol na polopřímce a kdyžtak jí udělat jinam.
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..
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ě.
Tak třeba:
...
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?
Zobrazeno 16 zpráv z 16.