| Zobrazit předchozí téma :: Zobrazit následující téma |
| Autor |
Zpráva |
perry
Založen: 28. 07. 2009
Příspěvky: 879
|
 Zaslal: 19. říjen 2012, 19:12:04 Předmět: Problém s polygonem a určením bodu uvnitř |
 |
|
Čau...
nějak jsem se rozjel s tématy... každopádně, celý den řeším kravinu a nemůžu najít chybu.
Mám polygon (trojuhelnik pro jednoduchost) a chci určit bod uvnitř.. úplně stupidním testem - každá hrana vs. bod a všechna znaménka musejí být stejná.
Problém je, že mi to nefunguje a nemůžu najít proč...
polygon si vykreslím - je OK
spočítám se znaménkovou plochu - je OK
projdu všechny hrany a zjistím že koncový bod jedné = počáteční druhé - OK
pak vezmu každý bod uvnitř a udělám sign test... a výsledek je tohle:
Seznam vrcholů polygonu (start index - end index [start vrchol] - [end vrchol], kdyby někdo chtěl vidět: http://www.perry.cz/files/s.txt. Seřazeno by to mělo být CCW
Znaménkový test co mám:
| kód: |
for (všechna [x,y])
{
in = true;
for (uint32 i = 0; i < border.size(); i++)
{
MyMath::Vector2 a = vertices[border[i].v0];
MyMath::Vector2 b = vertices[border[i].v1];
MyMath::Vector2 c = MyMath::Vector2(x, y);
float val = ((b.X - a.X)*(c.Y - a.Y) - (b.Y - a.Y)*(c.X - a.X));
if (val < 0)
{
in = false;
break;
}
}
if (in) drawPoint(x, y);
}
|
Co je ovšem zajímavé, že pokud místo trojúhelníku udělám obdélník, tak vše funguje OK. Pokud udělám třeba kružnici, tak se mi vybarví asi 3/4 a tvar je něco jako 8-úhelník. Koukal jsem, jestli to třeba nedělá float aritmetika, taky jsem nazjistil že by mi výsledky vycházeli okolo 0.
Vážně jsem z toho už blbej  [/url]
_________________
Perry.cz
Naposledy upravil perry dne 19. říjen 2012, 22:50:58, celkově upraveno 1 krát |
|
| Návrat nahoru |
|
 |
manutara
Založen: 02. 01. 2012
Příspěvky: 81
Bydliště: Kosice SVK
|
| Zaslal: 19. říjen 2012, 20:18:41 Předmět: problem |
|
|
zdravim,
ten trojuholnik ma byt akoze cely cerveny?? v poslednom case menej
chapem kym to nedostanem priamo na podnose, hmm...
zatim...
_________________
hadam to OpenGL este par rokov prezije |
|
| Návrat nahoru |
|
|
perry
Založen: 28. 07. 2009
Příspěvky: 879
|
| Zaslal: 19. říjen 2012, 21:37:57 Předmět: |
|
|
Jj.. přesně tak.. ten trojúhelník by měl být celý červený
_________________
Perry.cz |
|
| Návrat nahoru |
|
|
VODA
Založen: 29. 07. 2007
Příspěvky: 1721
Bydliště: Plzeň
|
| Zaslal: 19. říjen 2012, 22:08:37 Předmět: |
|
|
Předpokládám, že řádek s
| kód: |
| float val = ((b.X - a.X)*(c.Y - a.Y) - (b.Y - a.Y)*(c.X - a.X)); |
je něco jako 2D "vektorový" součin...dost se to tak tváří.
Neměl by být bod C vztažen k počátečnímu bodu hrany polygonu namísto k počátku souřadného systému? Když jsem dělal point-in-polygon test já, tak jsem navíc musel projít alespoň dvě hrany, abych zjistil, zda-li se znaménka liší...na druhou stranu, pokud máš hrany orientované jedním směrem (buď CW nebo CCW), tak Ti vlastně stačí najít jen jedno znaménko...což ten tvůj kód vlastně dělá...
A nemusí se při každém testu bodu resetovat proměnná notIn?
Víc mě nenapadá...bych si to musel naimplementovat a zkusit...
_________________
Opravdovost se pojí s trýzní... |
|
| Návrat nahoru |
|
|
Weny Sky
Založen: 28. 07. 2007
Příspěvky: 241
|
| Zaslal: 19. říjen 2012, 22:42:48 Předmět: |
|
|
| kód: |
| float val = (a.X*b.Y + a.Y*c.X + b.X*c.Y) - (b.Y*c.X + a.Y*b.X + a.X*c.Y); |
a proc kreslis bod pri splneni podminky notIn, kdyz rikas, ze chces kreslit body, ktere tam jsou? |
|
| Návrat nahoru |
|
|
perry
Založen: 28. 07. 2009
Příspěvky: 879
|
| Zaslal: 19. říjen 2012, 22:50:17 Předmět: |
|
|
Jo.. to mi v tom postu v kodu vypadlo.. proměnnou notIn resetuju... Proč se to jmenuje notIn.. no protože jsem to blbě pojmenoval  .. Upravil jsem ten kod v prvnim postu
_________________
Perry.cz |
|
| Návrat nahoru |
|
|
Vilem Otte
Založen: 18. 09. 2007
Příspěvky: 462
Bydliště: Znojmo - Sedlesovice, Kravi Hora
|
| Zaslal: 19. říjen 2012, 23:06:02 Předmět: |
|
|
Takže rychle jsem napsal halfspace rasterizaci v C# - kód vypadá cca takto:
| kód: |
// Render single polygon
for(int x = 0; x < rasterizer.Width; x++)
{
for(int y = 0; y < rasterizer.Height; y++)
{
bool inside = true;
for (int i = 0; i < borders.Count(); i++)
{
Vector2 a = borders[i][0];
Vector2 b = borders[i][1];
Vector2 c = new Vector2((float)x, (float)y);
if ((a.X - b.X) * (c.Y - a.Y) - (a.Y - b.Y) * (c.X - a.X) > 0)
{
inside = false;
break;
}
}
if (inside)
{
((Bitmap)rasterizer.Image).SetPixel(x, y, Color.FromArgb(255, 255, 0, 0));
}
}
} |
A funguje úplně bez problému, takže v znaménkovém testu to nebude (takže zbývá zřejmě zkontrolovat hrany).
Zkus hrany def. vertexy (6 verts = 3 edges):
(50, 50); (250, 70); (250, 70); (140, 210); (140, 210); (50, 50);
_________________
Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration. |
|
| Návrat nahoru |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 610
|
|
| Návrat nahoru |
|
|
perry
Založen: 28. 07. 2009
Příspěvky: 879
|
| Zaslal: 20. říjen 2012, 07:47:51 Předmět: |
|
|
Zatím mi nejde o rychlost, ale jenom o jednoduché vyzkoušení principu... hrany mám definované jak psal Vilem Otte (viz. soubor co jsem linkoval).
Hrany se tváří OK
Co mi např. nejde do hlavy, že to funguje pro obdélník úplně OK... nebo pro kružnici že to vyplní střed.. ale pak čím blíž jsem ke hraně, tím víc se to podělá
_________________
Perry.cz |
|
| Návrat nahoru |
|
|
Houp
Založen: 28. 07. 2007
Příspěvky: 672
|
| Zaslal: 20. říjen 2012, 08:26:26 Předmět: |
|
|
| perry napsal: |
| čím blíž jsem ke hraně, tím víc se to podělá |
Zkus double.
_________________
 |
|
| Návrat nahoru |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 610
|
| Zaslal: 20. říjen 2012, 08:35:01 Předmět: |
|
|
| perry napsal: |
Zatím mi nejde o rychlost, ale jenom o jednoduché vyzkoušení principu... hrany mám definované jak psal Vilem Otte (viz. soubor co jsem linkoval).
Hrany se tváří OK
Co mi např. nejde do hlavy, že to funguje pro obdélník úplně OK... nebo pro kružnici že to vyplní střed.. ale pak čím blíž jsem ke hraně, tím víc se to podělá |
Hmm, kód, co jsi psal ty a co psal Vilém je ekvivalentní. Pokud to jemu funguje a tobě ne, tak bude problém asi někde jinde 
EDIT: Teď jsem zkusil tvůj kód a na trojúhelník mi to funguje bez problémů. Floatama to určitě nebude, bude to IMHO nějaká uplná blbost  |
|
| Návrat nahoru |
|
|
perry
Založen: 28. 07. 2009
Příspěvky: 879
|
| Zaslal: 20. říjen 2012, 08:53:55 Předmět: |
|
|
Hm.. tak chyba je v polygonu... ona totiž v tom rastru neni vidět, ale na pár místech vz. nekonvexita... tzn., že ten test selhával. Proto všechno vypadalo OK, ale nebylo OK... a nenapadlo mě tu nekonvexitu hledat...
Všem díky za rady a pomoc
_________________
Perry.cz |
|
| Návrat nahoru |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 610
|
| Zaslal: 20. říjen 2012, 08:55:31 Předmět: |
|
|
| perry napsal: |
Hm.. tak chyba je v polygonu... ona totiž v tom rastru neni vidět, ale na pár místech vz. nekonvexita... tzn., že ten test selhával. Proto všechno vypadalo OK, ale nebylo OK... a nenapadlo mě tu nekonvexitu hledat...
Všem díky za rady a pomoc |
Pokud chceš konkávní polygony, zkus ten test, co jsem ti na něj posílal link. Ten si s tím poradí. |
|
| Návrat nahoru |
|
|
perry
Založen: 28. 07. 2009
Příspěvky: 879
|
| Zaslal: 20. říjen 2012, 09:07:54 Předmět: |
|
|
Jj.. ten jsem právě použil a tim zjistil, že to je konkávní nejspíš
_________________
Perry.cz |
|
| Návrat nahoru |
|
|
|
Hlavní strana
FAQ
Test
Hledat
Seznam uživatelů
Uživatelské skupiny
Registrace
Ke Stažení
Nastavení
Přihlášení
Calendar
