[Python] Točke unutar romba (poligona) • MATEMANIJA
Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI MATEMATIKA U INFORMATICI MATEMATIKA U PROGRAMIRANJU

[Python] Točke unutar romba (poligona)

[Python] Točke unutar romba (poligona)

Postod zagi92 » Nedelja, 16. April 2017, 00:34

* MOD EDIT * Zadatak izdvojen iz ove teme

Trebam savjete kako da riješim sljedeći problem.

romb.png
romb.png (6.4 KiB) Pogledano 226 puta

[dispmath]\begin{array}{|c|c|c|} \hline
& X & Y\\ \hline
T_1 & 2 & 3\\ \hline
T_2 & 5 & 2\\ \hline
\end{array}[/dispmath]
Romb obuhvaća sljedeće točke:
[dispmath]\begin{array}{|c|c|c|c|c|} \hline
1,3 & & & & \\ \hline
2,2 & 2,3 & 2,4 & & \\ \hline
3,1 & 3,2 & 3,3 & 3,4 & 3,5\\ \hline
4,2 & 4,3 & 4,4 & & \\ \hline
5,3 & & & & \\ \hline
\end{array}[/dispmath]
Zadatak:

1) Kako da iz kontrolnih točaka (označene crnom bojom [inlmath]3,1|4,2|5,3[/inlmath] itd...) dobijem popis svih točaka unutar romba (poligona)? Da li uz pomoć matrica ili?

2) Kako bi trebao izgledati uvjet (algoritam) da računalo jedino točku [inlmath]T_1[/inlmath] označi kao ispravnu (zato što se nalazi unutar romba) a točku [inlmath]T_2[/inlmath] označi kao neispravnu.


(Slika s originalnim tekstom zadatka)
Poslednji put menjao Daniel dana Nedelja, 16. April 2017, 18:49, izmenjena 2 puta
Razlog: Prekucavanje teksta zadatka sa slike, uz kropovanje slike (tačke 13. i 14. Pravilnika)
zagi92  OFFLINE
 
Postovi: 3
Zahvalio se: 3 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +1

Re: [Python] Točke unutar romba (poligona)

Postod Daniel » Nedelja, 16. April 2017, 11:48

Pozdrav i dobro došao na forum. Kao što vidiš, korigovao sam tvoj post da bude u skladu s tačkama 13. i 14. forumskog Pravilnika. A i složićeš se da ovako lepše i preglednije izgleda.
Naravno, zamoliću te da se upoznaš i s ostalim tačkama Pravilnika.
Imao bih pitanje – iz kog predmeta je ovaj zadatak? Da bih znao da l' da ga prebacim u „Analitičku geometriju“, u „Matematiku u programiranju“, il' možda u neku treću rubriku. I inače, nov zadatak uvek ide u zasebnu temu, kao što to kaže tačka 10. pomenutog Pravilnika.

zagi92 je napisao:1) Kako da iz kontrolnih točaka (označene crnom bojom [inlmath]3,1|4,2|5,3[/inlmath] itd...) dobijem popis svih točaka unutar romba (poligona)? Da li uz pomoć matrica ili?

Popis svih tačaka unutar romba ne možeš nikako dobiti, budući da tačaka unutar romba ima beskonačno (neprebrojivo) mnogo. Da li si možda mislio na tačke s celobrojnim koordinatama? U tom slučaju bi se na to pitanje već moglo odgovoriti.

zagi92 je napisao:2) Kako bi trebao izgledati uvjet (algoritam) da računalo jedino točku [inlmath]T_1[/inlmath] označi kao ispravnu (zato što se nalazi unutar romba) a točku [inlmath]T_2[/inlmath] označi kao neispravnu.

Pre svega, treba videti da li [inlmath]x[/inlmath]-koordinata ispitivane tačke pripada intervalu [inlmath][1,5][/inlmath]. Ukoliko ne pripada tom intervalu, jasno je sa slike da ta tačka ne pripada rombu. Ukoliko pripada tom intervalu, potrebno je onda taj interval podeliti na podintervale [inlmath][1,3][/inlmath] i [inlmath][3,5][/inlmath], jer na [inlmath]x=3[/inlmath] imamo prelome pravih. Zatim se posmatra onaj podinterval kojem pripada [inlmath]x[/inlmath]-koordinata ispitivane tačke.

U intervalu [inlmath][1,3][/inlmath] posmatrati donju i gornju duž, tj. duž koja sadrži tačke [inlmath](1,3)[/inlmath] i [inlmath](3,1)[/inlmath] i duž koja sadrži tačke [inlmath](1,3)[/inlmath] i [inlmath](3,5)[/inlmath]. Napisati eksplicitni oblik jednačine prave kojoj pripada svaka od te dve duži. U opštem slučaju eskplicitni oblik jednačine prave koja sadrži tačke [inlmath]A(x_A,y_A)[/inlmath] i [inlmath]B(x_B,y_B)[/inlmath] glasi [inlmath]\displaystyle y=\frac{y_B-y_A}{x_B-x_A}(x-x_A)+y_A[/inlmath]. Konkretno, za gornju duž, koja sadrži tačke [inlmath](1,3)[/inlmath] i [inlmath](3,5)[/inlmath] dobićeš, uvrštavanjem, [inlmath]\displaystyle y=\frac{5-3}{3-1}(x-1)+3[/inlmath], tj [inlmath]y=x+2[/inlmath]. Slično uradiš i za donju duž. Zatim u dobijene jednačine umesto [inlmath]x[/inlmath] uvrstiš [inlmath]x[/inlmath]-koordinatu ispitivane tačke i posmatraš koje vrednosti [inlmath]y[/inlmath] ćeš dobiti u jednoj i u drugoj jednačini. Ukoliko se [inlmath]y[/inlmath]-koordinata ispitivane tačke nalazi između ovako dobijenih vrednosti [inlmath]y[/inlmath], onda ta tačka pripada rombu. U suprotnom, ne pripada rombu.

Sličan je postupak i ukoliko [inlmath]x[/inlmath]-koordinata ispitivane tačke pripada onom drugom podintervalu, [inlmath][3,5][/inlmath].
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7238
Lokacija: Beograd
Zahvalio se: 3756 puta
Pohvaljen: 3928 puta

Re: [Python] Točke unutar romba (poligona)

Postod zagi92 » Nedelja, 16. April 2017, 17:04

Hvala, zahvaljujem na korigiranju posta i slažem se da izgleda preglednije. Svakako budem pogledao i proučio pravilnik foruma. Ovaj zadatak je iz područja GIS-a (Geografski informacijski sustav) i na kraju bi trebao napisati program u Python-u.
Ovako glasi cijeli zadatak.

Imam zadatak da u GIS-u nađem koordinate lokacija uz pomoć adresa (Geokodiranje). Koordinate koje dobijem iz tražilica (Google maps / BING maps / OSM ) za jednu lokaciju ne poklapaju se svaki put. Primjer: BING mi je iz adrese M. Tita 80 Opatija ispiše koordinate u blizini Zagreba dok je GOOGLE izbaci pravu lokaciju u Opatiji.
Da bi eliminirao pogrešnu koordinatu koristio sam formulu za udaljenost dviju točaka
[dispmath]d_{1,2}=\sqrt{(T_{x1}-T_{x2})^2+(T_{y1}-T_{y2})^2}\\
d_{1,2}=d(T_1,T_2)\\
d_{2,3}=d(T_2,T_3)\\
d_{1,3}=d(T_1,T_3)[/dispmath] i onaj rezultat koji bi imao najveću udaljenost između točaka ta koordinata bi bila najvjerojatnije pogrešna. No postoji kvaka ako dvije koordinate imaju pogrešnu lokaciju a imaju malu udaljenost jedna od druge a treća koordinata točnu lokaciju i ima veliku udaljenost u odnosu na dviju pogrešnih tada bi mi program eliminirao točnu koordinatu odnosno lokaciju. Zato sam odbacio takvo rješenje za moj problem.

Što me dovodi to trenutnog problema. Romb predstavlja jednostavni prikaz poligona općine. Crne točke predstavljaju granične vrijednosti koordinata do kuda se općina proteže. Da je općina pravilnog oblika npr. ''Kvadrat'' (vidi sliku) onda bi uzeo 4 kontrolne točke najsjeverniju([inlmath]Y_2[/inlmath]), najzapadniju([inlmath]X_1[/inlmath]), najjužniju([inlmath]Y_1[/inlmath]) i najistočniju ([inlmath]X_2[/inlmath]) i za točku [inlmath]T_A[/inlmath] uvrstio formulu
[dispmath]T_A=x_A>x_1\land x_A<x_2\\
T_A=y_A>y_1\land y_A<y_2[/dispmath] I ako se koordinata (tražena lokacija) nalazi unutar zadanih parametara tražene općine program bi ju trebao prikazati kao ispravnu. Ali pošto su općine nepravilnog oblika gornja formula ne daje točne rezultate.

Slika

Raspolažem s koordinatama graničnih točaka općina i koordinata lokacija.
Daniel znači li to što si napisao bi to trebalo biti rješenje za moj problem ?
zagi92  OFFLINE
 
Postovi: 3
Zahvalio se: 3 puta
Pohvaljen: 0 puta

  • +2

Re: [Python] Točke unutar romba (poligona)

Postod ubavic » Nedelja, 16. April 2017, 18:18

Koliko vidim ti imaš problema sa dobijanjem ispravnih koordinata.
Pošto je iz tvog prvobitnog posta delovalo kao da se u problemu pojavljuju samo celobrojne vrednosti i četvorouglovi, odgovoriću šta bih ja uradio u tom slučaju:
Od temena konveksnog poligona i tačke [inlmath]T[/inlmath] za koju se pitam da li se nalazi u njemu, formirao bih trouglove, takve da je jedno teme trougla baš [inlmath]T[/inlmath], a druga dva temena su zapravo susedna temena poligona. Zatim bih za svaki od tih trouglova izračunao determinantu (onu koja se nalazi u opštepoznatoj formuli za površinu trougla), pazeći pritom veoma na orijentaciju tih trouglova. Ako su sve determinante pozitivne, tada se [inlmath]T[/inlmath] nalazi u poligonu. Mislim da se ovakav algoritam često koristi za konveksne poligone, jer je dosta brz (ako su još i celobrojne vrednosti u pitanju, onda bi trebalo da leti).

Ako vam je dat ovakav zadatak, da li ste radili pre toga neke složenije algoritme koji određuju da li se tačka nalazi u poligonu?
Korisnikov avatar
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 498
Lokacija: Zrenjanin
Zahvalio se: 332 puta
Pohvaljen: 482 puta

Re: [Python] Točke unutar romba (poligona)

Postod zagi92 » Nedelja, 16. April 2017, 19:31

ubavic je napisao:Ako vam je dat ovakav zadatak, da li ste radili pre toga neke složenije algoritme koji određuju da li se tačka nalazi u poligonu?

Na faksu uopće nemamo programiranje, matematiku ili takve kompleksne probleme iz gisa. Zanima me gis i python te sam pokušavam proširiti znanje na nekim primjerima iz konkretne stvarnosti.
zagi92  OFFLINE
 
Postovi: 3
Zahvalio se: 3 puta
Pohvaljen: 0 puta

  • +1

Re: [Python] Točke unutar romba (poligona)

Postod Daniel » Nedelja, 16. April 2017, 20:27

zagi92 je napisao:Daniel znači li to što si napisao bi to trebalo biti rješenje za moj problem ?

Ukoliko se oblik posmatrane opštine može sa zadovoljavajućom preciznošću aproksimirati rombom koji si prikazao, onda da.
U suprotnom, ako je oblik opštine potrebno posmatrati kao neki složeniji konveksan poligon, onda najbolje da radiš metodom koju je Ubavic predložio.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7238
Lokacija: Beograd
Zahvalio se: 3756 puta
Pohvaljen: 3928 puta

  • +1

Re: [Python] Točke unutar romba (poligona)

Postod ubavic » Sreda, 07. Februar 2018, 01:29

Ovde bi trebalo da se malo dopunim, pošto nisam pazio na neke detalje u svom odgovoru.

Pošto se ovaj problem odnosi na koordinate geografskih lokacija, ovde ne bi trebalo koristiti euklidsku geometriju, već sfernu, iako bi euklidska geometrija možda bila dovoljno dobra za ovakav problem (dakle za rastojanja reda prosečne opštine na geografskoj širini Balkana (na ekvatoru bi greška bila minimalna)). Ipak za neka preciznija merenja bila bi neophodna znanja iz pomenute sferne geometrije. Ja sam ovih dana na brzinu smislio nekakav algoritam koji bi mogao da dâ odgovor da li neka tačka pripada sferi (prevedemo sferne koordinate temena trougla i tačke u dekartovske koordinate. Time dobijamo četiri prostorna vektora. Sada posmatranjem projekcija vektora tačke na vektorske proizvode vektora temena možemo dobiti traženi odgovor....) Ipak mislim da je moja ideja izmišljanje tople vode. Ljudi koji su se bavili sfernom geometrijom sigurno su smislili nekakve pametnije/efikasnije metode za određivanje pripadnosti tačke nekom poligonu. Koga ovo interesuje, siguran sam da može lako da izgugla....

Inače, u međuvremenu sam saznao za jedan metod određivanja pripadnosti tačke unutrašnjosti poligona u euklidskoj ravni. Iz date tačke povučemo polupravu koja ne sadrži nijedno teme poligona (poligoni imaju konačno mnogo temena, pa ovakva poluprava uvek postoji). Ako poluprava seče poligon u neparno mnogo tačaka, tada tačka pripada unutrašnjosti poligona. U suprotnom tačka pripada spoljašnjosti poligona (ovde bi trebalo ispitati i slučaj kada tačka pripada samom poligonu (ivici), ali da ne davim sad...). Ovaj metod ima i teorijski i praktičan značaj.
Korisnikov avatar
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 498
Lokacija: Zrenjanin
Zahvalio se: 332 puta
Pohvaljen: 482 puta


Povratak na MATEMATIKA U PROGRAMIRANJU

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 1 gost


Index stranicaTimObriši sve kolačiće boarda
Danas je Utorak, 21. Avgust 2018, 00:53 • Sva vremena su u UTC + 1 sat [ DST ]
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs