Zdravím všechny - existuje nějaký jednoduchý algoritmus kterým se dá zjistit jestli je nějaký bod součástí polygonu nebo ne?
1. Znám souřadnice bodu jehož polohu ověřuji
2. Znám souřadnice vrcholů polygonu
3. polygon může mít 3 až n vrcholů
4. polygon může být nekonvexní a často se stává že některé jeho vnitřní úhly jsou větší jak 180°
Neexistuje nějaké modelové řešení takovýchto úloh?
Záleží mi i na rychlosti algoritmu protože tento problém ve skutečnosti řeším v jazyce PHP a tam si nemohu dovolit žádné rozsáhlé matematické operace, cykly apod. Rozumím i VB a Pascalu takže řešení si jsem schopen případně předělat ...
Můžete prosím někdo poradit? Díky
jak zjistit jestli je bod součástí polygonu nebo ne
- Dynalon
- Začátečník
-
- Registrován: 27. črc 2005
- Kontaktovat uživatele:
- €agle
- Středně pokročilý
-
- Registrován: 13. lis 2003
- Bydliště: Vlastní 3D svět :)
- Kontaktovat uživatele:
A ten polygon je dvou nebo trojrozmerny? Jestli dvou, tak koukni sem, je to tam docela dopodrobna popsany.
Eagle3D Engine under developement
Hledáme do firmy schopného ASP/VB.NET/C# programátora, více po SZ
Hledáme do firmy schopného ASP/VB.NET/C# programátora, více po SZ
- Dynalon
- Začátečník
-
- Registrován: 27. črc 2005
- Kontaktovat uživatele:
ten polygon je dvourozměrný, na ten PDF se podívám ale nejsem si jistý jestli to budu schopen pochopit - mám za sebou teprve třeťák gymplu, navíc je to ještě anglicky ale zkusím to díky ...
Jinak vymyslel jsem vlastní algoritmus řešení ale nevím jestli bude fungovat na 100% - napsal sem v PHP funkci co ověřuje jestli je bod uvnitř trojúhelníku a pak jsem rozdělil polygon na trojúhelníky. Jediný problém je s vnitřními úhly většími jak 180° - vznikají tak trojúhelníky které leží ve vnější oblasti polygonu - abych tento jev eliminoval tak např. u devítiúhelníku si vyberu jeden vrchol a spojuji ho s ostatními vrcholy kromě dvou sousedních a tím mi vznikne 7 trojúhelníků, tento postup zopakuju pro všech 9 vrcholů a pokud zjistím že ve všech devíti cyklech (1 cyklus pro každý vrchol) se vyskytl jeden trojúhelník ve kterém se nacházel testovaný bod pak se bod nachází v polygonu, pokud bod alespoň v jednom cyklu chybí pak se pravděpodobně nachází mimo. U jednodušších polygonů by to mělo fungovat ale mám obavy aby u těch složitějších že vzniknou jakási hluchá místa a hlavně by mi vadilo kdyby nějaký bod co leží ve vnější oblasti označil za vnitřní.
Co se týká množství cyklů tak to moc nehraje roli - největší polygon se kterým se to potká bude mít 16 vrcholů což znamená 14*16=224 cyklů a ta funkce pro ty trojúhelníky je poměrně krátká a rychlá ...
Jinak vymyslel jsem vlastní algoritmus řešení ale nevím jestli bude fungovat na 100% - napsal sem v PHP funkci co ověřuje jestli je bod uvnitř trojúhelníku a pak jsem rozdělil polygon na trojúhelníky. Jediný problém je s vnitřními úhly většími jak 180° - vznikají tak trojúhelníky které leží ve vnější oblasti polygonu - abych tento jev eliminoval tak např. u devítiúhelníku si vyberu jeden vrchol a spojuji ho s ostatními vrcholy kromě dvou sousedních a tím mi vznikne 7 trojúhelníků, tento postup zopakuju pro všech 9 vrcholů a pokud zjistím že ve všech devíti cyklech (1 cyklus pro každý vrchol) se vyskytl jeden trojúhelník ve kterém se nacházel testovaný bod pak se bod nachází v polygonu, pokud bod alespoň v jednom cyklu chybí pak se pravděpodobně nachází mimo. U jednodušších polygonů by to mělo fungovat ale mám obavy aby u těch složitějších že vzniknou jakási hluchá místa a hlavně by mi vadilo kdyby nějaký bod co leží ve vnější oblasti označil za vnitřní.
Co se týká množství cyklů tak to moc nehraje roli - největší polygon se kterým se to potká bude mít 16 vrcholů což znamená 14*16=224 cyklů a ta funkce pro ty trojúhelníky je poměrně krátká a rychlá ...