Diskuze: Body v SVG polygonu

PHP PHP Body v SVG polygonu American English version English version

Avatar
Panther
Člen
Avatar
Panther:

Ahoj,
chtěl bych se zeptat, zda neexistuje nějaká funkce, princip, který by mi pomohl s následujícím příkladem. Mám polygon vytvořený pomocí několika bodů

 <svg height="250" width="500">
  <polygon points="220,10 300,210 170,250 123,234" />
</svg>

a potom mám další bod např. [200;150] a potřebuji zjistit, zda je uvnitř, venku, popř. na hranici.
Napadlo mě řešení pomocí vektorů, ale než se do toho pustím, chtěl bych vědět zda už neexistuje něco jednoduššího. Díky

 
Odpovědět 27. února 14:14
Avatar
Fredep
Redaktor
Avatar
Odpovídá na Panther
Fredep:

Ahoj, pokud to chceš udělat v PHP, tak jsem našel stránku, kde se tento problém řeší. http://assemblysys.com/…n-algorithm/

Nahoru Odpovědět 27. února 18:52
Týmová práce je důležitá proto, aby bylo možno obvinit z neúspěchu někoho jiného.
Avatar
Drahomír Hanák
Tým ITnetwork
Avatar
Odpovídá na Panther
Drahomír Hanák:

V PHP nejspíš žádná standardní funkce není. Platí ale, že bod P je v polygonu jedině když polopřímka vycházející z P protne polygon v lichém počtu bodů (až na tečné body).

Pokud by tě to zajímalo, tak to plyne z Jordanovy věty o kružnici: "Každá topologická kružnice dělí rovinu na 2 obloukově souvislé množiny, jednu omezenou a jednu neomezenou." Každý bod může být jen v jedné obloukově souvislé množině (nebo na samotné kružnici). Při každém protnutí hrany polygonu se tak polopřímka dostane z vnější (neomezené) množiny do vnitřní (omezené) nebo naopak. Pokud je P v omezené množině, polopřímka musí protnout hrany polygonu v lichém počtu bodů (polopřímka se z omezené množiny musí vždy dostat do neomezené, protože není v jednom směru omezena, ale průnik omezené množiny s polopřímkou už omezený je). Tohle samozřejmě není důkaz, spíš jen takové vysvětlení, proč by to mohla být pravda.

Akceptované řešení
+20 Zkušeností
+1 bodů
Řešení problému
 
Nahoru Odpovědět 27. února 19:41
Avatar
Panther
Člen
Avatar
Panther:

Podobné řešení mě taky napadlo, ale nevěděl jsem jestli platí všude a jak přesně to v php definovat. Takže díky za vysvětlení, teď to už snad nějak dohromady dám. :-)

 
Nahoru Odpovědět 27. února 21:26
Avatar
coells
Redaktor
Avatar
Odpovídá na Drahomír Hanák
coells:

Jenže polygon není topologická kružnice, a platí, že:

  1. buď nedělí rovinu na dvě souvislé množiny v případě exklusivního průniku
  2. nebo nelze použít test polopřímkou v případě inklusivního průniku
 
Nahoru Odpovědět 27. února 21:35
Avatar
Drahomír Hanák
Tým ITnetwork
Avatar
Odpovídá na coells
Drahomír Hanák:

Měl jsem tam ještě dodat, že se jeho hrany nesmí protínat. Věděl by si, jak by se tedy dalo ukázat, že dané tvrzení platí, když teda přidáme ještě tenhle předpoklad (třeba jen zhruba)? Docela by mě to zajímalo (výpočetní geometrii apod. předměty, kde se tohle nejspíš probírá, jsem zatím viděl jen z dálky ve skriptech nebo jen úvod v diskrétní matematice). Příp. jak by se dal použít jiný test, pokud existuje nějaký vhodnější.

Jinak, pokud dobře chápu definici topologické kružnice (obraz prosté uzavřené křivky - tedy spojité funkce F z [0, 1] do roviny t.ž.F(0) = F(1) a F je prostá na intervalu [0, 1)), pak by ji měl jednoduchý polygon (polygon, který se neprotíná ani ve vrcholech) splňovat, ne?

 
Nahoru Odpovědět 27. února 22:49
Avatar
coells
Redaktor
Avatar
Odpovídá na Drahomír Hanák
coells:

Topologie je o třídu složitější než diskrétka, kde se berou jen takové jemné základy. Pamatuju si, že jsem na zápočet dokazoval neexistenci planárního grafu na válci a můj "neprůstřelný" důkaz měl problém s něčím, co jsem ani nepochopil, ani se to nevysvětluje. Prostě pokud to nebude tvoje specializace, tak se k tomu nedostaneš.

V praxi je obvyklé, že polygony degenerují už jen kvůli nepřesnostem v plovoucí čárce, takže tyhle školní algoritmy skoro nikdy nefungují a musí se upravovat pro krajní případy.

Ray-casting (rovnoběžný s osou) je v pohodě, jen se musí kontrolovat rovnoběžnost s hranami. Pokud je polygon konvexní, dá se kontrolovat výskyt bodu na stejné polorovině, to je buď trocha lineární algebry nebo komplexní čísla. Jsou ještě další způsoby, ale pro pidi-polygony je lepší něco jednoduchého.

 
Nahoru Odpovědět  +1 27. února 23:59
Avatar
coells
Redaktor
Avatar
coells:

Jinak nejlepší zdroj pro grafické algoritmy jsou Graphics Gems I-V, jsou tam všechny myslitelné i nemyslitelné algoritmy - fungující v praxi - a pracují na tom minimálně 20 let (tehdy se dostaly do ruky mně).

Editováno 28. února 0:03
 
Nahoru Odpovědět  +1 28. února 0:03
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 8 zpráv z 8.