Matematické Fórum

Ja teda predpokladam, ze pocitanie obsahu nie je nejaky problem, da sa aj napisat jednoduchy vzorec pre n-uholnik zadany vrcholmi, ale predpokladam, ze ten asi poznas. Problem bude zrejme v tom ako hladat ten prienik, co je vo vseobecnosti pomerne algoritmicky narocna uloha. Tu som nasiel diskusiu okolo toho.

http://stackoverflow.com/questions/2272 … tersection

Je tam aj odkaz na kniznice v Delphi, C++ and C# v ktorej by to uz malo byt predprogramovane uplne vseobecne.

Nech su vrcholy n-uholnika znacene proti smeru hodinovych ruciciek, pricom - ten posledny vrchol je len kvoli jednoduchosti zapisu vzorca. Nech je lubovolny bod. Potom

Ak by si ho znacil v smere hodinovych ruciciek, tak dostanes minus obsah.
Ak by mal samoprieseky, tak casi obehnute v smere HR prispievaju zapornym obsahom a casti obehnute proti smeru HR prispievaju kladnym obsahom.

si zvol tak aby sa ti to co najlahsie pocitalo, napr.: alebo pri ti vypadne prvy a posledny clen tej sumy, lebo budu nulove.

V skutocnosti je to len aplikacia toho co spominal ↑ martisek: - napisana tak aby sa to lahko programovalo.

↑ groover:

Pokud jde o ten průnik, je přece daleko jednodušší spočítat součet obsahů těch čtyřúhelníků (jakoby se nepřekrývaly) a od toho odečíst obsah toho překrývajícího se osmiúhelníka.

↑ martisek:
Nevidim dovod preco by malo byt zjednotenie jednoduchsie ako prienik. Ak su zadane dve stvorice bodov tak aky bude algoritmus na ich zjednotenie. Dokonca to ani nemusi byt n-uholnik. Moze sa jednat napriklad o 12-uholnik, ktory ma vyrezany stvoruholnik zvnutra, napr.:


prienik su dva stvoruholniky.

Konvexnost je skor argument pre pocitanie prieniku, lebo prienik konvexnych polygonov je konvexny polygon, zatial co zjednotenie konvexnych stvoruholnikov moze byt napr. nekonvexny 16-uholnik. Ale to je v podstate dost jedno. Nejaky vseobecny algoritmus aj na jedno aj na druhe bude podla mna rovnako zlozity, sam som si ho nepozeral, ale nevidim dovod preco by malo byt zjednotenie nejak jednoduchsie.

Ak by sa to robilo napr. cez nerovnice, tak konvexny n-uholnik je prienik rieseni n linearnych nerovnic. Teda prienik dvoch n-uholnikov je riesenie 2n linearnych nerovnic a treba najst ktore z nich su nadbytocne. Zatial co zjednotenie by bolo dost komplikovane a v pripade nekonvexneho zjednotenia nam takyto pristup vobec nepomoze.

Tak, problem sa dost zjednodusil. :) Momentalne Labview obsahuje funkciu pocitania obsahu N-uholnikov. Takze momentalne uz potrebujem len najst body, kde sa pretinuaju jednotlive strany oboch stvoruholnikov.

↑ Brano:
Podľa mňa, keď tam má len konvexné útvary, tak skutočne mu stačí nájsť len body, v ktorých sa hrany útvarov pretínajú. A to by nemalo byť ťažké, proste porovnať každú hranu jedného útvaru s každou hranou druhého útvaru, či obsahuje spoločný bod. No a potom vyšetriť len prípad, keď je jeden útvar vložený do druhého. Ako som tak zbežne sa díval na ten odkaz, tak tam je to preto komplikované, lebo sa nejedná o konvexné útvary.

Tak, pekne po poporade. :

1. Vstup a vystup: Na vstupe si vyparsrujem z XML urcitu mnozinu bodov. tie body nie su nahovdne, a kazda stvorica bodov je nejak oznacena a tvori vzdy konvexne teleso. :) A k tejto skupine bodov budem potom hladat inu skupinu bodov, ktora sa plochou zhoduje na vopred stanoveny pocet %. Vystupom bude oznacenie definovaj stvorice bodov, ktora sa plochou zhoduje so zadanou stvoricou na zadany pocet %.

2. Mam moznost overit, ci sa nejaky konkretny bod nachadza mimo, na hrane, alebo vo vnutri definovaneho telesa. funkcia Convex hull tam je. :)

Najskor by som riesil otazku hladania bodov, az potom ich usporiadavanie. :)

↑ groover:
No a keby si tam nahodou funkciu na hľadanie prienikov dvoch úsečiek nemal tak sa to dá spočítať:
Prvá usečka nech je , druhá . 
Potom musí platiť



Keď si to rozpíšeš na jednotlivé súradnice, tak vznikne sústava 2 rovníc o dvoch neznámych.
Tu vyriešiš a overíš, či x,y splňujú podmienku.
Konkrétny bod potom dostaneš dosadením za x alebo y do ľavej alebo pravej strany rovnosti.

Ešte ma napadlo, čo keď 2 útvary majú spoločnú hranu, alebo aspoň čiastočne sa na nejakom úseku
hrany zhodujú. Tam treba vziať do úvahy hraničné body prieniku 2 úsečiek. To tiež pôjde určit z tej
rovnice, len bude treba zistiť hraničné hodnoty prieniku riešení sústavy a podmienky na x,y.

Inak poradie vrcholov, asi najjednoduchsie je urobiť na ne convex hull, no keby bola núdza
tak by sa dalo podľa mňa zistit aj z toho v akom poradí ich budeme nachádzať,  to by bolo ale potřeba si rozmyslet ale to by taky šlo.

Brano napsal(a):

Ved tam mas predprogramovane skoro vsetko :-)

mas tam aj taku funkciu ktora by nasla prienik dvoch useciek?

No, moznosti su sice siroke, ale akonahle tam nieco nie je, tak si to clovek musi doprogramovat, a to nie je celkom prdel niekedy. :)

Keby tam ta funkcia bola, tak by to bolo super, ale nie je, bohuzial...

Dakujem za rady, idem sa na to hned pozriet. :)