Diskuze: Body v SVG polygonu

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

Aktivity

Vojtěch Wawreczka

Člen

Vojtěch Wawreczka:27.2.2016 14:14

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.2.2016 14:14

Neaktivní uživatel

Tvůrce

Neaktivní uživatel:27.2.2016 18:52

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.2.2016 18:52

Neaktivní uživatelský účet

Drahomír Hanák

Tvůrce

Drahomír Hanák:27.2.2016 19:41

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í
+2,50 Kč

Nahoru Odpovědět

27.2.2016 19:41

Vojtěch Wawreczka

Člen

Vojtěch Wawreczka:27.2.2016 21:26

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.2.2016 21:26

coells

Tvůrce

coells:27.2.2016 21:35

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

buď nedělí rovinu na dvě souvislé množiny v případě exklusivního průniku
nebo nelze použít test polopřímkou v případě inklusivního průniku

Nahoru Odpovědět

27.2.2016 21:35

Drahomír Hanák

Tvůrce

Drahomír Hanák:27.2.2016 22:49

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.2.2016 22:49

coells

Tvůrce

coells:27.2.2016 23:59

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

27.2.2016 23:59

coells

Tvůrce

coells:28.2.2016 0:03

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.2.2016 0:03

Nahoru Odpovědět

28.2.2016 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.

Nejčastěji vyhledáváné

Diskuze: Body v SVG polygonu