Proracun pokrivenosti povrsine poligona krugovima

Kolegice/kolege,

Imam interesantan problem na kojem lomim zube. Radi se o slijedecem:

Imam poligon koji dobijam zadavanjem 4 tacke u vidu geografskih koordinata. Potom metodom slucajno generisanih koordinata postavljam tacke u poligon ( senzore ) koji imaju svoj opseg rada. Potrebno je da proracunam procentualnu pokrivenost povrsine poligona postavljenim senzorima. Na prvu, problem nije tezak, imamo povrsinu poligona, zbir povrsina krugova koji predstavljaju opseg pokrivenosti svakog od senzora i eto procentualne prekivenosti. Medjutim, senzori mogu biti na rubnim dijelovima poligona tako da jedan dio kruga ispada vani i mogu se preklapati unutar poligona sto predstavlja glavni problem pri proracunu.

Neizmjerno bi bio zahvalan ako iko ima neku ideju kako da rijesim problem.

HVALA!

Zanimljivo. Pitanje je da li postoji neka granica do koje se situacija komplikuje, tj. da li se može javiti situacija gde neki signal pokriva dva temena poligona, koliko se signala može preklapati... U situaciji na slici, od ukupne površine krugova treba oduzeti plave, što je lako, odsečci krugova, zelene (tetiva ih deli na dva odsečka, a zamisli da je zeleno i ispod ljubičastog, tj. oduzimaš preseke svaka dva signala), crvene (i dalje je to račun sa isečcima i odsečcima kruga i trouglovima). E, onda treba DODATI ljubičaste, tj. dodaješ preseke tri signala, i tu je pitanje koliko preklapanja ima, jer se preseci naizmenično dodaju i oduzimaju - princip uključenja i isključenja.

Možda neki program tipa Geogebra može da pomogne.

Potpis

"We are mathematicians, we are happy when we have a problem!"

Proverila sam, Geogebra može da ti da i površine poligona i isečaka kruga, što ti je dovoljno. Na slici sa leve strane vidiš površinu kružnog isečka f, površinu trougla EGH, znači sve možeš da dobiješ preko koordinata temena poligona, centara kružnica i presečnih tačaka (presečne tačke ti takođe daje program).



Proračun komplikuju i preseci koji delom izlaze iz poligona... Bez ikakvih ograničenja, teško se može dati dobar recept. Možda bi jednostavnije bilo posmatranje nepokrivene površine - idealno bi bilo kad bi se kao u Paintu obojila nepokrivena površina i onda kad bi neki program mogao da prepozna kolika je ona.

Za svaki odsečak na drugoj slici treba formirati isečak i trougao, pa oduzeti površine koje daje Geogebra.

Potpis

"We are mathematicians, we are happy when we have a problem!"

Moglo bi ovako. Prvo se uvede predstava „lučnog poligona“, sa stranicama koje mogu biti bilo duži bilo kružni lukovi. Krugovi tada postaju lučni poligoni sa jednog stranicom. Zatim se izvede funkcija koja prima dva lučna poligona i vraća lučni poligon koji je njihova razlika, i funkcija koja računa površinu jednog lučnog poligona. Trenutni poligon se postavi na početni poligon. Petljom kroz krugove, oduzimaju se jedan po jedan od trenutnog poligona. Izračuna se površina krajnjeg trenutnog poligona i površina početnog poligona, i njihov količnik predstavlja odnos (ne)pokrivenosti.

Dalje, deluje mi da u rešenju problema nije neophodna puna tačnost (do na greške zaokruživanja). U tom slučaju, značajno uprošćenje bilo bi da se krugovi prethodno aproksimiraju poligonima, recimo 10-stranim do 20-stranim. Tada sve gorepomenute operacije postaju operacije između običnih poligona, za šta se sigurno mogu naći gotovi algoritmi i izvedbe.

Treba paziti i na to koliko su udaljene geografske koordinate. Što su udaljenije, to tačnost više opada ako se poligoni posmatraju kao ravanski. Opet zavisi od željene tačnosti, ali recimo da je do nekoliko stotina kilometara verovatno u redu. Inače mora da se pređe na sferne poligone, gde su stranice kružni lukovi na istoj sferi (planete).

Platio bih vam pivo ili kafu za ove prijedloge :)

Nisam bio dovoljno precizan:
- Poligon je cetverougaoni
- Opseg senzora je jedinstven za sve senzore
- Potreban mi je algoritam koji bih implementirao u Visual Studio c# aplikaciji.

Ako ista uspijem konkretizirati podijelit cu ovdje.

HVALA!

Da li se zna broj senzora i njihov precnik ili poluprecnik opsega delovanja?
Da li je cetvorougao pravilan ili proizvoljan?

Ja bih uradio sledece:
- prvo se utvrde jednacine strana cetvorougla na osnovu 4 koordinate
- za svaku koordinatu senzora prvo utvrditi da li pripada cetvorouglu ili je van njega
- za senzore koji su u cetvorouglu izracunati udaljenost centra od svake strane cetvorougla
- ako je udaljenost centra senzora od svake strane cetvorougla veca od polurecnika delovanja onda imamo punu povrsinu kruga, ako je manje onda deo kruga izlazi iz cetvorougla i trebamo izracunati deo odsecka koji se odbija
- ako je vise senzora u cetvorouglu treba ispitati njihove medjusobne udaljenosti i utvrditi preklapanja ako postoje

Ja bih poceo da resavam problem prvo sa jednim senzorom i analizirao sve mogucnosti.
Zatim resavamo problem sa 2 senzora.
A ako je potrebno uvodimo analizu resavanja problema sa vise senzora, ali se onda resenje eksponencijalno komplikuje.

Problem nije trivijalan, ali moze se resiti uz malo vise truda.

Problem nema svrhe resavati graficki vec se mora resavati analiticki, i algoritam mora da predvidi sve moguce kombinacije i slucajeve, i moze se javiti tu dosta komplikacija, osim ako problem nije postavkom uproscen (sto se iz izlozene postavke ne vidi, ali ... mozda nisi sve napisao).

U svakom slucaju moramo uzeti u obzir da li radimo samo u ravni ili u sfernoj ravni, a i to se moze ugraditi u algoritam pa ako je duzina izmedju 2 koorditate cetvorougla veca od XX kilometara onda radimo sferno a ako je manja onda radimo u ravni.

Moj je savet da krenes sa analizom problema od najjednostavnijeg slucaja i resavas ga algoritamski pa da onda komplikujes i slucaj i algoritam.

Veliki cetverougao mozes da podjelis na niz manjih pa da provjeris za svaki od tih manjih cetverouglova da li pripada nekom od krugova. Naravno sto je sitnija podjela tacniji je rezultat