Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Avatar
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
Avatar
Odpovídá na Vojtěch Wawreczka
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
Avatar
Odpovídá na Vojtěch Wawreczka
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č
Řešení problému
 
Nahoru Odpovědět
27.2.2016 19:41
Avatar
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
Avatar
coells
Tvůrce
Avatar
Odpovídá na Drahomír Hanák
coells:27.2.2016 21:35

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.2.2016 21:35
Avatar
Odpovídá na coells
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
Avatar
coells
Tvůrce
Avatar
Odpovídá na Drahomír Hanák
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
Avatar
coells
Tvůrce
Avatar
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.