[es] - Centar poligona, nepravilnog

Boris B.
Ljubljana

Član broj: 213615
Poruke: 286
*.dial-up.dsl.siol.net.

+14 Profil

^{19.08.2010. u 00:19 - pre 166 meseci}

Nisam matematicar a imam problem kako da odredim vizuelni centar nepravilnog 2D poligona koji je predstavljen kao niz tačaka, ali tako da je taj centar 100% unutar poligona?

Moje resenje bi bilo da nadjem centar najveceg krug koji se moze upisati u poligon, i to tako da krug ne mora da dodiruje sve stranice poligona. Sav materijal sto nalazim po netu se odnosi na najveci krug koji dodiruje SVE stranice, ali to ne radi za nepravilne poligone (npr. nesto kao potkovica), jer oni ni nemaju takav krug. Sa druge strane, svaki poligon bez obzira na pravilnost, ima najveci upisani krug koji ne mora da dodiruje sve stranice, ali za to ne mogu da nadjem resenje.

Drugo, slicno resenje je da nadjem najveci pravougaonik (bez rotiranja, znaci orijentisan na X i Y osu) koji moze da se upise u poligon, mada tek to ne mogu da nadjem.

Ima li neko ideju / resenje?

if it walks like a duck and quacks like a duck, it could be a dragon doing a duck
impersonation.

Odgovor na temu

miki069

Član broj: 161528
Poruke: 1951
*.vs.rs.

+370 Profil

Re: Centar poligona, nepravilnog

^{19.08.2010. u 01:33 - pre 166 meseci}

Pretpostavljam da pod poligon misliš na mnogougao i
da imaš date koordinate temena mnogougla u nekom 2D ili 3D koordinatnom sistemu.
Ako imaš samo dužine stranica mislim da je problem nemoguć i onda ne čitaj dalje.

1. Odredi svim stranicama koordinate središta stranica.
2. Formiraj jednačine pravih koje sadrže temena stranica.
3. Formiraj jednačine pravih simetrala svih stranica mnogougla. Sadrže središnje tačke i normalne su na stranicu.
4. Nađi sve međusobne presečne tačke svih simetrala - njihove koordinate. Ima ih maximalno n*(n-1)/2, ako ni jedne 3 ne prođu kroz istu tačku.
5. Formiraj zbirove (ili zbirove kvadrata) udaljenosti svake tačke od svih preostalih tačaka iz koraka 4. Čuvaj i koordinate tačaka, trebaće.
6. Sortiraj niz zbirova udaljenosti u rastućem poretku.
7. Uzmi prvih n tačaka iz sortiranog niza i proglasi za temena novog mnogougla.

Rekurzivno ponavljaj korake 1 do 7 dok ne dođeš do tačke čiji je zbir udaljenosti blizak nuli
ili jednak zadatoj tačnosti recimo epsilon = 0.0000000001.
Ta tačka je aproksimativno centar "opisanog" kruga oko mnogougla, koga on stvarno nema.
Ujedno "centar" poligona.

Pisao sam ti više programerski.
Potrebna su i znanja nekih prostih stvari iz analitičke geometrije da bi se isprogramiralo:
- koordinate središta duži
- jednačina prave kroz 2 tačke
- jednačina prave kroz jednu tačku a normalna je na drugu pravu
- udaljenost između 2 tačke
- presek 2 prave....

Ako nešta škripi, pitaj.

Ako baš mora centar "upisanog" kruga onda onda se koriste prave simetrale uglova i
menjaju se koraci 1, 2 i 3 u kojima se formiraju njihove jednačine.

Nije mi baš najjasnije da li da se ganja centar "opisanog" ili "upisanog" kruga?
Centar upisanog kruga je podjednako udaljen od svake stranice.
Centar opisanog kruga je podjednako udaljen od svakog temena.
Zavisi od problema u sklopu koga rešavaš "centar".

_{[Ovu poruku je menjao miki069 dana 19.08.2010. u 03:21 GMT+1]}

Odgovor na temu