[PHP] Bod uvnitř kruhu na mapách

[DarkScarf]

Zdravím,

chtěl bych se zeptat, zda nějakým způsobem jde zjistit, jestli bod na mapě patří do kruhové výseče, či nikoli. Mám databázi, kde se mi ukládají polohy zařízení a parametry okruhu (střed + poloměr).

Používám Google Maps API a potřeboval bych, aby se tato informace vypočítávala na serveru nikoli na konečném zařízení.

Děkuji

[karlos00x]

zkus geophp.

[gandor]

Rovnica krhu je x^2+y^2=r^2... Z toho odvodis ze nieco v kruhu je vtedy, ked: x^2+y^2<=r^2
Samozrejme najskvor musis polozit oba body do rovnakej sustavy zacinajucej v strede toho kruhu (od zaujmoveho bodu odpocitas poziciu stredu kruhu a vysledne suradnice x a y dosadis do rovnice vyssie - r je polomer kruznice). Elementarna matematika (da sa napisat aj ako 1 riadok kodu) bez potreby akejkolvek kniznice.
Mozno nepresna len pri vecsich vzdialenostiach (zakrivenie planety a neviem co je presne kruhovy vysec)...

[Nargon]

Ptáš se na "kruhovou výseč" nebo "kruh"?
To je celkem rozdíl.
Jestli se ptáš jen na to zda nějaký bod leží uvnitř kruhu tak je to velice snadný výpočet. Vzpomeň si na Pythagorovu větu. Tím velice snadno vypočítáš vzdálenost dvou bodů. Pokud vzdálenost bude větší než poloměr tak bod uvnitř kruhu neleží. A jestli bude menší tak uvnitř kruhu leží. A jestli je přímo roven tak leží přesně na kružnici.

Pokud se ptáš na kruhovou výseč, tj takový ten "trojúhelník s jednou stranou zakřivenou do tvaru kruhu" tak je to o něco složitější a hlavně ti k tomu asi budou chybět nějaké údaje jako třeba jak velká výseč toho kruhu je a jakým směrem je otočená. Ale i to by se dalo spočítat. Napadá mě například to, že by museli současně platit tři podmínky. Bod by musel být v kruhu (viz výše) a k tomu další podmínka, že by musel ležet na správné straně od přímek, které ten kruh řežou na výseč. A to jde také spočítat, ale teď se mi nechce hledat jak, když ti k tomu stejně chybí ty údaje o výseči.

[gandor]

To co pisal Nargon s tou vysecou asi nebude ono, lebo k tomu nemas vstupne udaje (ako pisal Nargon, musel by si mat napriklad ze vysec od 3 stupnov po 15 stupnov co su dalsie 2 parametre).

Riesenie tohto problemu nieje jednoduche. Implementacia by bola tazsia, takze tu uz tu kniznicu doporucujem.
Ale ak si sikovny, tak ja osobne by som to spravil tak, ze pre test vyseku kruznice by som si skonvertoval stupnove vysece na rovnicu priamky (tvar y=ax+b [kde b=0 - vysec zacina od stredu kruznice]) a smernicu "a" ziskas cez sinus (sin alpha="a"/1 [kde alpha predstavuje dane stupne vysece]) ). Nasledne dosadis tvoj skumany bod x do rovnice priamky a priamo voci sebe porovnavas y-ky = vysledok rovnice priamky a y-ovu suradnicu bodu (ak sa rovnaju tak je na vysece, inak je pre dany bod nad resp. pod vysecou).
No a potom finalna vec - urcit v ktorom kvadrante je bod v ktorom prva vysec a v ktorom druha vysec. napriklad 0 az 270 stupnove vysece znamenaju, ze ak je bod v 1-om az 3-tom kvadrante, tak je vntry. Dokonca ak je v 2-om kvadrante, tak nemusis ani robit test na poziciu vyseci. Ale ak su vysece 270 az 360, tak beries vysledok len ak je bod v 4-tom kvadrante. A ked nemas stupne pekne podelene na nasobky 90 stupnov, tak vtedy robis presne ten test cez tie moje priamky (a podla kvadrantu vies interpretovat, ci vysledne-y ked je mensie ako y-suradnica skumaneho bodu, ze ci je alebo nieje vnutry v danej vyseci)....

Mozno existuje aj jednoduchsie riesenie, ale toto je urcite spravne a rychle (len komplikovane) riesenie...

[Nargon]

Co se týče výseče, tak jsem si to zkusil trošku rozkreslit a něco dohledat a tohle by mělo fungovat:
Nejdřív nákres ať máme lepší představu: https://ctrlv.cz/149i
Pak trochu vektorové matematiky, operace Cross product (jak je to v češtině nevím): https://en.wikipedia.org/wiki/Cross_product

Kód: Vybrat vše

float Cross(float Ax, float Ay, float Bx, float By, float Cx, float Cy)
{
    return ((Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax));
}

Funkce má jako vstup 3 body A,B,C a jejich pozice x a y. Bod A je střed kružnice, bod B je krajní bod té výseče a bod C je testovaný bod.
Funkce Cross vrátí hodnotu, která může být kladná a nebo záporná. To zda bude kladná/záporná je dáno tím zda bod C je od vektoru AB "vlevo" nebo "vpravo". Vzhledem k tomu že je to vektorový výpočet tak to funguje pro různé otočení stále stejně. Tj když si papír otočíš tak aby šipka vektoru ukazovala nahoru, tak vždy podle toho zda je výsledek + nebo - poznáš zda je bod C vlevo nebo vpravo. Nemusíš se tedy starat o to v jakém kvadrantu jseš. "Vždy" musí platit že bod C musí být od vektoru AB1 napravo a současně od vektoru AB2 musí být nalevo. To vždy mám v uvozovkách protože to není vždy, ale platí to jen v případě že úhel té výseče je menší než 180°.
Pokud je úhel větší než 180° tak to neplatí, protože bod C se může dostat do místa kde by měl být od obou vektorů směrem vlevo/vpravo. viz nákres č.2: https://ctrlv.cz/y897
Ale to se dá vyřešit jednoduchou změnou podmínky. tj: "Vždy" musí platit že bod C musí být od vektoru AB1 napravo NEBO od vektoru AB2 musí být nalevo.
Takže to taky není úplně bezproblémové i zde se musí hlídat zda je úhel výseče menší/větší než 180° (tj polovina kruhu) Ale to zas není až takový problém tam mít ten jeden IF navíc, kde zjišťuješ úhel výseče a v jednom případě použiješ logický AND a ve druhém případě logický OR mezi testami levé/pravé strany vektoru výseče.

Samozřejmě vždy musí platit i to co jsem psal dříve. Bod C musí být uvnitř křužnice viz pythagorova věta.
Body B1 a B2 nemusí ležet na kružnici, slouží jen pro určení směru vektoru, takže mohou mít libovolnou pozici na daném vektoru (pokud ho tedy neotočí na opačnou stranu.

Ale co z toho bude lepší na implementaci nevím. Každé řešení má něco do sebe. A co z toho je lepší by asi záleželo na tom jak budeš mít uloženou/zadanou tu výseč kruhu. Což není vůbec jasné protože to jsi nenapsal takže dost pochybuji že jsi psal o "výseči" ale měl jsi na mysli jen ten jednoduchý kruh.

[gandor]

Tvoje riesenie Nargon je jednoduchsie na implementaciu (kratsie a teda menej chyb) a aj je efektivnejsie (ale oba vypocty su bleskove) - len je IMO zlozitejsie na predstavu/matematiku.
Ak vysec, tak tvoje riesenie by som si zvolil na implementaciu (ale ako som spominal, na to urcena kniznica bude urcite jednoduchsia vec)...
PS. riesenie 180 stupnov by som riesil radsej tak, ze ci nieje vo zvysku a vysledok znegoval (t.z. ak mam zistit, ci je vysec medzi 45 a 330 stupnom, tak radsej spravim test ci je medzi 330 a 45 stupnom a vysledok obratim - plati pre cely vypocet az na cast detekcie ci je bod v strede kruhu).

[DarkScarf]

Zaprvé bych chtěl poděkovat všem za jejich odpovědi. Za druhé jsem to špatně uvedl, zajímá mě pouze na kruh, omlouvám se.

Po chvilce zkoumání mi také došlo, že vlastně jediné co potřebuji je zjistit vzdálenost mezi souřadnicemi středu kruhu a souřadnicemi sledovaného budu, a jejich vzdálenost následně porovnat se zadaným poloměrem. A pak pouze podle výsledku rovnice vzdálenost/poloměr jestli je bod v kruhu ( x>1 není v kruhu, x<1 je v kruhu a x=1 je na hranici kruhu).