Da li je tacka u poligonu?

[Peruzzi]

Kako proveriti da li je tacka A(x,y) u proizvoljnom n-tostranom poligonu zadatom sa n temena A1(x,y), A2(x,y) , ..., An(x,y) ? (slika 1)

Za konveksne poligone resenje je (manje-vise) lako: nadju se jednacine pravih kojima su odredjene stranice poligona, pa se postavi sistem nejednacina od njih. Ako je tacka A u skupu resenja sistema nejednacina onda se nalazi u poligonu. (slika 2)

Problem je za nekonveksne.

Ideja koja mi prvo pada na pamet (primenjiva za svaki poligon) je da se pocepa na vise trouglova, tj. manjih poligona, pa da se proveri da li je tacka u nekom od njih. Medjutim, za nekonveksne problem je odabrati te delove tako da neki od njih ne bude van. (slika 3)


Ajd sad.

 

[Pjer_Nis]

Ako neces da brines o resursima i eleganciji, a hoces da radi za bukvalno svaku figuru, mozes da uradis ovako:

Kreiras bitmapu, iscrtas poligon, filujes ga i pogledas koje je boje zadata tacka. Nije elegantno, ali ako si u tesncu s vremnom i ne moras da stedis memoriju, zavrsice ti posao.

 

[Peruzzi]

pametno...
a ako je poligon mnooogo veliki ili ako nije dovoljno veliki pa tacka umesto da bude pored stranice sa spoljne strane padne na stranicu onda bude malo nezgodno.

evo sta mi reko kolega takmicar - postavim vektore od tacke ka svakom temenu i sabiram uglove svaka dva susedna vektora, tj vektora koji idu od tacke do susednih temena. ako je zbir uglova 360 stepeni onda je tacka u vektoru, ako nije onda je van. primetiti da postoje i negativni uglovi

 

[Pjer_Nis]

A sta biva sa nekonveksnim figurama?

 

[pater.familias]

A šta ćemo sa ovakvim slučajem?
Ako nema mogućnosti da dođe do ovog slučaja sa slike,
poslušaj druga i radi preko uglova. Ako ima šanse da dođe do
ovoga, javi da potražimo univerzalnije rešenje.

P.S. Ovo nije baš poly, ali je zato moguće da jedan deo face-a moraš da isključiš
iz provere, kao na slici.

 

[Peruzzi]

za konveksne i nekonveksne je isti princip, jer postoje negativni uglovi, pa se to sve lepo slozi

a ove forme se nisam setio, mada u stvari i nije poligon nego u neku ruku poligon \ poligon.
resenje bi bilo da se proveri da li je tacka u celom poligonu (i osenceno i ovaj beli romb), pa ako jeste unutra onda se proveri da li je tacka van tog belog romba. ako jeste onda je u osencenom.

odnosno - razbije se na dva poligona. e problem je opet - kako znati da treba ovako da se radi?

mada i to verovatno lako moze da se resi, jer ovakav poligon mora da se definise ipak kao dva poligona u odredjenom odnosu (razlika u ovom slucaju), jer se crtaju sa dva poteza olovke

 

[pater.familias]

@Peruzzi: Da, to zavisi od toga kako je nastao beli romb, neka vrsta npr. kolizije,
koja je u presečnim tačkama napravila romb ili šta drugo. Uglavnom, to sada zavisi
od toga kako je došlo do slike, mislim da je specifično za većinu slučajeva. Ako npr
uzmemo koliziju u igri, u jedan array se mogu čuvati oštećenja određenog objekta i
kasnije iz njega pozivati na test kada zatrebaju (uz test za 'neoštećenu' geometriju).
Mislim da je idejno problem već rešen, a ako želiš da se reši i u konkretnom slučaju
moraš da daš više informacija.
Inače ovo mi je zanimljiva tematika, pa nadogradnja teme nije na odmet u svakom slučaju.

edit: Eh, da. Video sam da je mali problem u rešavanju sa uglovima ako je tačka na nekoj od
tačaka koje definišu poligon. Npr. na tvojoj slici A1, A2... Tada bi se samo trebalo pre provere putem
uglova, trebalo proveriti da li je tražena tačka recimo S(x,y,z) na istoj poziciji kao i neka od tačaka
koje formiraju face npr. A1(x1,y1,z1),A2(x2,y2,z2)...

 

[codemaker]

Svaka cast momci, volim da citam diskusije ove vrste. Fascinira me taj deo matematike, u kojem sam veoma, veoma slab a volim da citam o tome.
Najdalje sto sma dogurao je cisto "seljacka" (bez namere da vredjam ljude sa sela) metoda, cekiram svaki pixel poligona pa ako nije iste boje kao poligon - izvan sam.. Uslov je da je ivica poligona neke druge boje od poligona, da je poligon jednobojan i da se ja petljam u ono o cemu nemam pojma

Ponekad vam zavidim na znanju koje posedujete.

 

[Peruzzi]

e moj ti...nadji negde matematike za gimanziju i prouci. videces da mnogo toga moze prostije kad znas vektore (ponekad i mi tebi zavidimo na znanju koje posedujes)

a za coskove si u pravu. i za stranice mi izgleda da ne radi, tako da bi i to trebalo u test, ali to nista nije problem, par formula se ispita, cas posla.

A problem je nastao kao proizvod moje dosade: sta bi bilo ako bi se desilo... .. tako da nema konkretnog slucaja na koji sam mislio.

Verujem da slicno vazi i za 3d objekat, samo sto je onda malo nezgodno racunati, tu je vec potrebno uplesti malo visu matematiku.

 

[codemaker]

Neka, ne moze svako znati sve...
U gimnaziji sam mrzeo matematiku i francuski.
Matematiku jer smo imali profesora koji je smatrao da Bog zna za 5, on za 4 a ostali da se cupaju za dvojku ako on dozvoli. Francuski jer sam u prvoj godini stavio petardu u kaljevu pec za vreme njenog casa i od onda sam imao popravni sve cetiri godine...

Kad meni pritreba nesto specificno iz matematike, znam da im a drugara ovde koji "razbijaju" Sa druge strane, ja cu pomoci koliko mogu sa onoliko znanja koliko imam i eto simbioze

 

[Peruzzi]

fino...

eto sad imas jos jednog za simbiozu

 

[toxi]

Хахаха....

Ово са математиком је мени тотално страно и, одма да кажем, досадно. Кад сам правио неку једноставну игрицу математичарка ми објашњавала сто неких чуда, која су ми помутила памет. Урадих ја то, али више се неупуштам у такве "авантуре"...

Перуци, си успео то што си хтео да урадиш? Јел можемо да видимо програмче?

 

[Peruzzi]

ma nisam ni radio program. ovo je cisto iz hobija

 

[Login Killer]

Trebao si probati al ajd.

Nisam neki matematicar, ali pokusacu da resim zadatak, iako zadatak nije naivan kao sto izgleda.
Resenje bi trebalo da bude ovako za ovaj primer sto je naveo Tsutomu, a ujedno je i resenje Peruzzi-og zadatka bez "farbanja" poligona.

Nacin na koji sam smislio ide nekako ovako:
1. Pribelezi se svi podaci o duzima
2. Utvrdi se koja duz kojoj slici pripada
3. Proveri se koja slika je u kojoj
4. U slici u kojoj se nalazi slika treba da se proveri tacka da li se u njoj nalazi, ako se nalazi onda ne pripada poligonu, ako ne onda idemo dalje
5. Proveriti da li se tacka nalazi u prvoj slici, ako da ona pripada poligonu ako ne onda ne pripada.

Svaka stranica je duz koja je ogranicena sa dve tacke. Znaci povucena linija koja spaja te dve tacke je ustvari stranica mnogougla.
Svaka od tih tacaka ima X i Y koordinatu. Znaci cetiri parametra sluze za definisanje stranice (X1,Y1) i (X2,Y2), koje je neophodno da
se sacuvaju u memoriji( radi kasnijeg ispitivanja),najbolje bi bilo da se smesti u neku bazu podataka.
Kada se nacrta trougao to ispada ovako nekako u memoriji: ( moze i mnogougao samo me mrzi da ispisujem neku drugu, ima mnogo koordinata)
Utvrdi se koja duz kojoj slici pripada, a to se radi pomocu tacaka koje se poklapaju od dve razlicite duzi i tako se dobija slika.
____________________________
| X1 | Y1 | X2 | Y2 |
|___________________________|
| 120 | 200 | 150 | 100 | - Prva Linija
|___________________________|
| 150 | 100 | 200 | 250 | - Druga linija
|___________________________|
| 200 | 250 | 120 | 200 | - Treca linija
|___________________________|

U njemu se nalazi jos jedan trougao: ( moze i mnogougao samo me mrzi da ispisujem neku drugu, ima mnogo koordinata)
____________________________
| X1 | Y1 | X2 | Y2 |
|___________________________|
| 150 | 150 | 160 | 120 | - Prva Linija
|___________________________|
| 160 | 120 | 160 | 100 | - Druga linija
|___________________________|
| 160 | 100 | 150 | 150 | - Treca linija
|___________________________|

Zatim je potrebno ispitati koja se slika nalazi u kojoj( ako ima vise od jednog mnogougla). To nije neki veliki problem.

Sad treba proveriti da li se tacka nalazi prvo u slici koja se nalazi unutar druge slike.( Lakse je i brze odredjivanje prema ovom principu).

KAKO IDE OVO SA UGLOVIMA, nije mi bas skroz jasno. To bi moglo da posluzi za resavanje skroz zadatka.
Ako nemoze da se upotrebi onda ide trigonometrija.

Uzecu jednu sjajnu staru zbirku zadataka iz matematike(stampana je u Martu 1988 ) da se malo podsetim, i da vidim postoji li drugi nacin za resavanje zadatka.

Ova tema je zanimljiva i voleo bi da ih je vise. Jer ti probude zelju za necim sto nisi radio, i interesuje te da li ti je mozak za staro gvozdje ili ne. Ako nemogu da resim zadatak onda cu da batalim programiranje i idem negde da mesam malter po citav dan, usput i da smrsam . Doduse moram cekati prolece.

 

[Garwor]

ucite matematiku, to je prava stvar. Znate da najvece svetske programerske firme na konkursima za nova radna mesta uglavnom daju zadatke poput ovog gore. A ko hoce da radi informacione sisteme i ceo zivot racuna porez, preracunatu stopu i preostali iznos fakture, taj moze i bez matematike.

 

[pater.familias]

Verujem da slicno vazi i za 3d objekat, samo sto je onda malo nezgodno racunati, tu je vec potrebno uplesti malo visu matematiku.

Važi i za 3d.
Evo kako Niko Gebhardt to (i još ponešto) odrađuje na relativno 'jeftin-brz' način.

// Copyright (C) 2002-2006 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in irrlicht.h

#ifndef __IRR_TRIANGLE_3D_H_INCLUDED__
#define __IRR_TRIANGLE_3D_H_INCLUDED__

#include "vector3d.h"
#include "line3d.h"
#include "plane3d.h"
#include "aabbox3d.h"

namespace irr
{
namespace core
{

//! 3d triangle template class for doing collision detection and other things.
template <class T>
class triangle3d
{
public:

//! Determinates if the triangle is totally inside a bounding box.
//! \param box: Box to check.
//! \return Returns true if the triangle is withing the box,
//! and false if it is not.
bool isTotalInsideBox(const aabbox3d<T>& box) const
{
return (box.isPointInside(pointA) &&
box.isPointInside(pointB) &&
box.isPointInside(pointC));
}

bool operator==(const triangle3d<T>& other) const { return other.pointA==pointA && other.pointB==pointB && other.pointC==pointC; }
bool operator!=(const triangle3d<T>& other) const { return other.pointA!=pointA || other.pointB!=pointB || other.pointC!=pointC; }

//! Returns the closest point on a triangle to a point on the same plane.
//! \param p: Point which must be on the same plane as the triangle.
core::vector3d<T> closestPointOnTriangle(const core::vector3d<T>& p) const
{
core::vector3d<T> rab = line3d<T>(pointA, pointB).getClosestPoint(p);
core::vector3d<T> rbc = line3d<T>(pointB, pointC).getClosestPoint(p);
core::vector3d<T> rca = line3d<T>(pointC, pointA).getClosestPoint(p);

T d1 = rab.getDistanceFrom(p);
T d2 = rbc.getDistanceFrom(p);
T d3 = rca.getDistanceFrom(p);

if (d1 < d2)
return d1 < d3 ? rab : rca;

return d2 < d3 ? rbc : rca;
}

//! Returns if a point is inside the triangle
//! \param p: Point to test. Assumes that this point is already on the plane
//! of the triangle.
//! \return Returns true if the point is inside the triangle, otherwise false.
bool isPointInside(const vector3d<T>& p) const
{
return (isOnSameSide(p, pointA, pointB, pointC) &&
isOnSameSide(p, pointB, pointA, pointC) &&
isOnSameSide(p, pointC, pointA, pointB));
}
//! Returns if a point is inside the triangle. This method is an implementation
//! of the example used in a paper by Kasper Fauerby original written
//! by Keidy from Mr-Gamemaker.
//! \param p: Point to test. Assumes that this point is already on the plane
//! of the triangle.
//! \return Returns true if the point is inside the triangle, otherwise false.
bool isPointInsideFast(const vector3d<T>& p) const
{
vector3d<T> f = pointB - pointA;
vector3d<T> g = pointC - pointA;

f32 a = f.dotProduct(f);
f32 b = f.dotProduct(g);
f32 c = g.dotProduct(g);

f32 ac_bb = (a*c)-(b*b);
vector3d<T> vp = p - pointA;

f32 d = vp.dotProduct(f);
f32 e = vp.dotProduct(g);
f32 x = (d*c)-(e*b);
f32 y = (e*a)-(d*b);
f32 z = x+y-ac_bb;

return (( ((u32&)z)& ~(((u32&)x)|((u32&)y))) & 0x80000000)!=0;
}

bool isOnSameSide(const vector3d<T>& p1, const vector3d<T>& p2,
const vector3d<T>& a, const vector3d<T>& b) const
{
vector3d<T> bminusa = b - a;
vector3d<T> cp1 = bminusa.crossProduct(p1 - a);
vector3d<T> cp2 = bminusa.crossProduct(p2 - a);
return (cp1.dotProduct(cp2) >= 0.0f);
}


//! Returns an intersection with a 3d line.
//! \param line: Line to intersect with.
//! \param outIntersection: Place to store the intersection point, if there is one.
//! \return Returns true if there was an intersection, false if there was not.
bool getIntersectionWithLimitedLine(const line3d<T>& line,
vector3d<T>& outIntersection) const
{
return getIntersectionWithLine(line.start,
line.getVector(), outIntersection) &&
outIntersection.isBetweenPoints(line.start, line.end);
}


//! Returns an intersection with a 3d line.
//! Please note that also points are returned as intersection, which
//! are on the line, but not between the start and end point of the line.
//! If you want the returned point be between start and end, please
//! use getIntersectionWithLimitedLine().
//! \param lineVect: Vector of the line to intersect with.
//! \param linePoint: Point of the line to intersect with.
//! \param outIntersection: Place to store the intersection point, if there is one.
//! \return Returns true if there was an intersection, false if there was not.
bool getIntersectionWithLine(const vector3d<T>& linePoint,
const vector3d<T>& lineVect, vector3d<T>& outIntersection) const
{
if (getIntersectionOfPlaneWithLine(linePoint, lineVect, outIntersection))
return isPointInside(outIntersection);

return false;
}


//! Calculates the intersection between a 3d line and
//! the plane the triangle is on.
//! \param lineVect: Vector of the line to intersect with.
//! \param linePoint: Point of the line to intersect with.
//! \param outIntersection: Place to store the intersection point, if there is one.
//! \return Returns true if there was an intersection, false if there was not.
bool getIntersectionOfPlaneWithLine(const vector3d<T>& linePoint,
const vector3d<T>& lineVect, vector3d<T>& outIntersection) const
{
vector3d<T> normal = getNormal().normalize();
T t2 = normal.dotProduct(lineVect);

if (t2 == 0.0f)
return false;

T d = pointA.dotProduct(normal);
T t = -(normal.dotProduct(linePoint) - d) / t2;
outIntersection = linePoint + (lineVect * t);
return true;
}


//! Returns the normal of the triangle.
//! Please note: The normal is not normalized.
vector3d<T> getNormal() const
{
return (pointB - pointA).crossProduct(pointC - pointA);
}

//! Returns if the triangle is front of backfacing.
//! \param lookDirection: Look direction.
//! \return Returns true if the plane is front facing, which mean it would
//! be visible, and false if it is backfacing.
bool isFrontFacing(const vector3d<T>& lookDirection) const
{
vector3d<T> n = getNormal();
n.normalize();
return n.dotProduct(lookDirection) <= 0.0f;
}

//! Returns the plane of this triangle.
plane3d<T> getPlane() const
{
return plane3d<T>(pointA, pointB, pointC);
}

void set(const core::vector3d<T>& a, const core::vector3d<T>& b, const core::vector3d<T>& c)
{
pointA = a;
pointB = b;
pointC = c;
}

//! the three points of the triangle
vector3d<T> pointA;
vector3d<T> pointB;
vector3d<T> pointC;
};


//! Typedef for a f32 3d triangle.
typedef triangle3d<f32> triangle3df;

//! Typedef for an integer 3d triangle.
typedef triangle3d<s32> triangle3di;

} // end namespace core
} // end namespace irr

#endif

E' da, sad' bih trebao da postavim i code za neke funkcije korišćene zdravo za gotovo, npr.
IsPointOnSameSide(...), ali malo razmišljanja i researcha nije na odmet. Ko ima vremena naravno.
Evo i jedne zanimljive adrese, http://www.blackpawn.com/texts/pointinpoly/default.html .

 

[Garwor]

@Login, uz sav napor, nisa uspeo da shvatim tvoje resenje
jel to za 2D ili 3D?

Za 3D bi moglo kao za 2D, samo sa prostornim uglovima, samo treba jasno definisati nacin zadavanja temena prostorne figure, i onda za svaku stranu racunati prostorni ugao.

 

[Login Killer]

Mi valjda ovde pricamo o 2D.

Mene je tesko razumeti, jer neznam da objasnim, zato kad neko dodje kod mene da mu neki deo koda objasnim (i poredsto se trudim da pisem sto vise komentara po kodu), najcesce ne uspevam, i pored dobre volje. Navedi sta ti tacno nije jasno, pa da resimo.

Jedini problem kod moje metode je to sto neki postojeci fajlovi nemogu da se provere a to su fajlovi koji nisu vektorski. Format koji je vektorski mogao bi da se iskoristi.

 

[Login Killer]

Ma kako se nisam setio mog starog prijatelja googla. Evo sta je nasao na ES-u.
http://www.elitesecurity.org/t23457-Da-li-je-tacka-poligonu-stranicnom

 

[codemaker]

Uff deco, zabole me glava....
'el imate vi neki problem da se resi a da se svodi na a+b = c ( i to mozda)
Ovo sto tu pisete samo sluzi da ce vas prijatelj codemaker, pola noci buljiti u plafon i izracunavati neke tupe uglove!
Eh, derani....

 

[Peruzzi]

evo jedno zadace...cisto razgibavanja radi

koliko linija c koda vam je potrebno za funkciju koja pretvara string u float?

broj moze biti zapisan na sledeci nacin +-0000.000000e+-000
broj cifara je proizvoljan, a jedino je ceo deo obavezan (uvek postoji), ostalo ne mora (korektan je i ulaz 213, ali i +2.115e-1)

ajde, dajte se na posao da vidimo da li ste bolji od mene