Forum » Programiranje » Ali je točka znotraj območja?
Ali je točka znotraj območja?
madonch ::
Imam en praktičen problem.
Z definiranjem množice točk (x,y) določim omejeno območje na ekranu - npr. pravokotnik, šestkotnik, zvezdo ali karkoli drugega.
S kakšnim algoritmom bi najučinkoviteje ugotovil ali je neka naključno izbrana točka (X0,Y0) znotraj tega območja ali ne.
Pozor! Delati mora tudi za območja tipa zvezda.
Najlepša hvala za odgovore.
Z definiranjem množice točk (x,y) določim omejeno območje na ekranu - npr. pravokotnik, šestkotnik, zvezdo ali karkoli drugega.
S kakšnim algoritmom bi najučinkoviteje ugotovil ali je neka naključno izbrana točka (X0,Y0) znotraj tega območja ali ne.
Pozor! Delati mora tudi za območja tipa zvezda.
Najlepša hvala za odgovore.
Vesoljc ::
prvi nacin je itaq brute force: pixel by pixel :)
drugi nacin pa nekak tkole: kompleksnejse like (zvezde itd..) je pomoje najboljs nekak razbit na bolj preproste (recimo trikotnike) in pregledat le-te.
kako prevers ce je pika v trikotniku ne bi vedu tocno iz glave... ksn srednjesolski matematicni zvezek ne bi skodil... vektorji itd...
drugi nacin pa nekak tkole: kompleksnejse like (zvezde itd..) je pomoje najboljs nekak razbit na bolj preproste (recimo trikotnike) in pregledat le-te.
kako prevers ce je pika v trikotniku ne bi vedu tocno iz glave... ksn srednjesolski matematicni zvezek ne bi skodil... vektorji itd...
Abnormal behavior of abnormal brain makes me normal...
MV ::
Obstaja vač algoritmov:
- algoritem s poltrakom,
- algoritem vsote kotov,
- algoritem enakih predznakov ...
Algoritem s poltrakom je najbolj znan in uporabljan. Uporaben je za konkavne mnogokotnike (lahko z vgnezdenimi luknjami).
Ideja: Iz poljubne točke (x0, y0) potegnemo poltrak v poljubni smeri, nato pa preštejemo število presečišč. Če je število presečišč liho, je točka znotraj mnogokotnika, sicer pa zunaj.
Če želiš ti lahko pošljem opise algoritmov na email (pdf 500 kB).
- algoritem s poltrakom,
- algoritem vsote kotov,
- algoritem enakih predznakov ...
Algoritem s poltrakom je najbolj znan in uporabljan. Uporaben je za konkavne mnogokotnike (lahko z vgnezdenimi luknjami).
Ideja: Iz poljubne točke (x0, y0) potegnemo poltrak v poljubni smeri, nato pa preštejemo število presečišč. Če je število presečišč liho, je točka znotraj mnogokotnika, sicer pa zunaj.
Če želiš ti lahko pošljem opise algoritmov na email (pdf 500 kB).
Zgodovina sprememb…
- spremenil: MV ()
StratOS ::
matematika, linearna funkcija in neenačbe, ful simpl.
Za kvadrat, kvader, trikotnik ni problema, mislim da je to fuul easy.
mas 3 ali 4 točke, linearne enačbe stranic tko al tko veš, ugotoviti moreš prvo, če je nad območjem stranic ali pod ( se pravi eno po eno stranico) z logičnim sklepanjem o diferenci in razdalji ( minimalni ) premice od točke - glej matematični zvezek/priročnik
lahko sklepaš ali je ta točka v liku ( sedaj ne glede na kakšen lik oz. kotnik - najlažje seveda za n=3,4).
Torej za preprost n-kotnik T, ki tvori nek n-koten lik
te zanima če je točka X(x,y) v tej množici definirani z enačbami stranic tega n-kotnika oz. množico točk T.
Najprej iz podatkov ogljišč tega n-kotnika (T) dobiš vse možne pare enačb stranic, torej n linearnih enačb stranic tega n-kotnika.
Z logičnim razmišljanjem in obliko lika (n-kotnika) sklepaš ali se točka X(x,y) nahaja v notranjosti lika T oz. pod ali nad našo stranico n-kotnika. Unija neenačb ti da potem rešitev če se nahaja v liku ali ne.
Za kvadrat, kvader, trikotnik ni problema, mislim da je to fuul easy.
mas 3 ali 4 točke, linearne enačbe stranic tko al tko veš, ugotoviti moreš prvo, če je nad območjem stranic ali pod ( se pravi eno po eno stranico) z logičnim sklepanjem o diferenci in razdalji ( minimalni ) premice od točke - glej matematični zvezek/priročnik
lahko sklepaš ali je ta točka v liku ( sedaj ne glede na kakšen lik oz. kotnik - najlažje seveda za n=3,4).
Torej za preprost n-kotnik T, ki tvori nek n-koten lik
te zanima če je točka X(x,y) v tej množici definirani z enačbami stranic tega n-kotnika oz. množico točk T.
Najprej iz podatkov ogljišč tega n-kotnika (T) dobiš vse možne pare enačb stranic, torej n linearnih enačb stranic tega n-kotnika.
Z logičnim razmišljanjem in obliko lika (n-kotnika) sklepaš ali se točka X(x,y) nahaja v notranjosti lika T oz. pod ali nad našo stranico n-kotnika. Unija neenačb ti da potem rešitev če se nahaja v liku ali ne.
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."
Thomas ::
Jest bi se poslužil tegale algoritma:
Greš iz te točke T(xx,yy) po x (ali po y) osi ven, dokler ne prideš čez vsak x (ali y), ki ga imajo točke.
Če si sekal kakšen robove lihokrat, si bil not.
Če sodokrat - si bil (je točka) zunaj lika.
Samo še umazane podrobnosti podelaj - pa je.
Greš iz te točke T(xx,yy) po x (ali po y) osi ven, dokler ne prideš čez vsak x (ali y), ki ga imajo točke.
Če si sekal kakšen robove lihokrat, si bil not.
Če sodokrat - si bil (je točka) zunaj lika.
Samo še umazane podrobnosti podelaj - pa je.
Man muss immer generalisieren - Carl Jacobi
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Python, prosim za pomoc pri programiranju (strani: 1 2 3 )Oddelek: Programiranje | 13276 (9378) | lenika |
| » | Algoritem za izračun težišča poljubnega 2D likaOddelek: Programiranje | 2678 (2575) | Gundolf |
| » | [delphi]seminarska - ploščina in obseg likovOddelek: Programiranje | 3192 (2900) | Gundolf |
| » | Tocka in trikotnik + 3DOddelek: Programiranje | 1582 (1427) | tomblord |
| » | poligonOddelek: Programiranje | 1876 (1578) | Thomas |