Konstrukcija elipse

O matematiki, številih, množicah in računih...
Medo5
Posts: 26
Joined: 8.2.2007 9:08
Location: Ljubljana
Contact:

Konstrukcija elipse

Post by Medo5 » 1.5.2008 20:55

Elipsa je enolično določena iz štirih točk plus kot, če le te niso prav čudno postavljene. Imam pa problem, kako dobit parametre te elipse, če imam znane 4 točke plus kot, oz upošteval bi še peto točko.
Sam problem je detekcija elipse/kroga na sliki. Delam z vekorji, ki jih zavrtim po kotu za 360°. Vrtišče ni čisto v centru, ker nevem kej je(to je iskan podatek). Tako dobim npr 360 vekotorjev, njihov kot in dolžino.
Sedaj pa bi rad izbral 5 naključnih točk, skozi njih napeljal elipso in s tem dobil radi(oz a,b) in pa center.

Hvala, Lp; Jan

User avatar
Aniviller
Posts: 7263
Joined: 15.11.2004 18:16

Re: Konstrukcija elipse

Post by Aniviller » 1.5.2008 22:06

Tvoj problem je pravzaprav iskanje koeficientov a,b,c,d,f, ce poznas koordinate.
\(a x^2+by^2+cxy+dx+fy-1=0\)
Prosti clen sem postavil na 1 ker lahko vedno delis z njim (razen ce je 0). Sredisca ti ni treba poznat - le-to, parametri elipse in kot so vsi doloceni s koeficienti v enacbi. Ko vstavis vsako od petih tock noter dobis pet linearnih enacb za neznanke a-f. Ker je izgleda problem programerski je resitev dobljena z enim obratom matrike, obstaja cel kup orodij ki to pocnejo (das jim array za matriko, array za vektor in dobis resitev). Lahko pa tudi sam napises gaussovo eliminacijo, samo znas imeti probleme s pivotiranjem (ne vem koliko poznas te stvari, ne se ustrasit).

V praksi je nenatancno vzeti samo 5 tock. Bolj ziher je vzeti vec tock (vsaj se kaksni dve). V tem primeru imas enacb vec kot neznank in isces resitev, ki najbolje zadosti vsem. Problem je ravno tako matricni. Ce te zanima, lahko pojasnim, ceprav bo zadovoljivo delalo tudi brez tega.

Sredisce matrike, parametre in kot dobis pa s pomocjo formul iz prirocnikov (tudi zadevajo matricni racun). Center dobis z resitvijo enacb
\(d+2ax+cy=0\)
\(f+cx+2by=0\)
To lahko resis na papir in vstavis. Zdaj, ce znas delati z lastnimi vektorji (oz. ce se komu na forumu ljubi izpeljati splosne formule), lahko ostalo naredis na podoben nacin. Drugace pa po tem koraku spravi formulo v obliko brez linearnih clenov
\(a' x^2+b' y^2+c' xy-1=0\)
potem (ce sem prav izpeljal) prideta polosi A,B (razlicna predznaka) takole
\(\frac{1}{A^2},\frac{1}{B^2}=\frac{1}{2}\left(a+b\pm \sqrt{(a+b)^2+c^2}\right)\)

Glede na to da pobiras podatke v polarnem sistemu, bi lahko slo se na kak temu primeren nacin (fourierov razvoj), ampak nima smisla doktorirati iz ene same elipse.

Medo5
Posts: 26
Joined: 8.2.2007 9:08
Location: Ljubljana
Contact:

Re: Konstrukcija elipse

Post by Medo5 » 2.5.2008 2:04

Hvala za razlago.
Sem že spisal(pobrskal po spletu in prilagodil mojim potrebam) algoritem, ki si ga navedel.

Tvoja zadnja formula za polosi vrača napačen rezultat. Primer a=1, b=0, c=3. => A=2, B=1. Formula vrne manjše številke.
Iz katere formule se šel izpeljevat?

Hvala, Lp; Jan

Medo5
Posts: 26
Joined: 8.2.2007 9:08
Location: Ljubljana
Contact:

Re: Konstrukcija elipse

Post by Medo5 » 2.5.2008 4:01

Sem še sam izpeljal iz glavne enačbe in rezultat je pravilen. Zanima pa me, kako je s členom "xy", ker se ge na upošteva. Ta člen predstavlja nagib elipse. Kaj če je v resnici nagnjena. Se da potem kako korigirat rezultat?

Lp; Jan

User avatar
Aniviller
Posts: 7263
Joined: 15.11.2004 18:16

Re: Konstrukcija elipse

Post by Aniviller » 2.5.2008 9:26

Jaz sem poiskal lastne vrednosti matrike
\(\begin{bmatrix}
a'&c'/2\\c'/2&b'
\end{bmatrix}\)

in dobim vrednosti, ki sem jih navedel (formula s korenom, pozabil sem pisat crtice). Clen xy je upostevan kot c', brez njega sta a' in b' itak ze polosi elipse. Ker je desna stran enacbe 1, velja \(A^2\lambda=1\) in enako za drugo lastno vrednost. Za smeri teh lastnih osi pa moras dobit lastne vektorje zgornje enacbe.

Meni se zdi se najgrsi del pretvorba iz ''premaknjene'' enacbe v centrirano :)
Aja, a=1 b=0 c=3 ne da elipse ampak hiperbolo.

User avatar
Aniviller
Posts: 7263
Joined: 15.11.2004 18:16

Re: Konstrukcija elipse

Post by Aniviller » 2.5.2008 9:50

Ja, kot pod katerim je elipsa bi moral bit
\(\phi=\arctan\frac{2(a'-B)}{c'}\)
ce sta stevec in imenovalec oba nic, potem je elipsa itak ze poravnana. Pa pazi malo kateri polosi pripada ta kot.

Medo5
Posts: 26
Joined: 8.2.2007 9:08
Location: Ljubljana
Contact:

Re: Konstrukcija elipse

Post by Medo5 » 2.5.2008 14:36

Točke, ki sem jih navedel, res niso na elipsi.
Moj sistem deluje, dokler elipsa ni rotirana. Potem pa odpove, ker polosi pridejo negativne...
Ne razumem pa dejstva, da je toliko različnik enačb, za isto stvar(npr iskanje centra). Dajejo pa različne rezultate. Še ta, ki je prej vračala ustrezen rezultat, pri rotirani elipsi odpove. Enačba je iz sl.wikipedije "Središče elipse" .
Kje grešim?
Če imaš čas, nakaži smer, kako priti do centriranih enačb. Je to edinaustrezna rešitev?

Lp; Jan
Last edited by Medo5 on 2.5.2008 16:16, edited 1 time in total.

User avatar
Aniviller
Posts: 7263
Joined: 15.11.2004 18:16

Re: Konstrukcija elipse

Post by Aniviller » 2.5.2008 16:05

Hm... na to pa nisem pomislil. Ja, pet tock definira poljubno stozernico, zato bos pri malo izmaknjenih tockah dobil lahko tudi kaksno drugo krivuljo. Tako da tale metoda ne bo dobra. Ce bi povecal stevilo tock bi slo ampak bolje da se spomnim kaksno boljso metodo.

Aja, pri premikanju elipse v center sploh ni tak problem kot se mi je zdelo ker vecino problema ze resis z dolocitvijo centra. Spremeni se ti le prosta konstanta:
\(a(x-x_0)^2+b(y-y_0)^2+c(x-x_0)(y-y_0)-ax_0^2-b x_0^2-cx_0y_0=1\)
\(a(x-x_0)^2+b(y-y_0)^2+c(x-x_0)(y-y_0)=1+ax_0^2+b x_0^2+cx_0y_0\)

Bom malo razmislil o drugi metodi pa sporocim.

User avatar
Aniviller
Posts: 7263
Joined: 15.11.2004 18:16

Re: Konstrukcija elipse

Post by Aniviller » 2.5.2008 16:21

Saj ce imas 360 tock, potem lahko dobis center s povprecenjem:
\(S=\frac{1}{2}\sum_i r_i^2 \Delta \varphi\)
\(X=\frac{1}{2}\sum_i \cos \phi_i \;r_i^3 \Delta \varphi\)
\(Y=\frac{1}{2}\sum_i \sin \phi_i \;r_i^3 \Delta \varphi\)
kjer je \(\Delta \varphi\) kot med vektorjema sosednjih tock (lahko so tudi razlicni). Te tri kolicine lahko izracunas v eni potezi. Potem je tezisce v
\(x_0=\frac{X}{S},\quad y_0=\frac{Y}{S}\). Mimogrede si dobil se ploscino elipse. Ko imas tezisce, lahko gres cez celo elipso se enkrat, sproti prestavljas vektorje (to bo treba narest v kartezicnih koordinatah) tako da jim odstevas tezisce in poisces najdaljsi vektor. Njegov kot je kot za katerega je zasukana elipsa, dolzina enaka vecji polosi. Enako za najmanjsi vektor. Saj verjetno imas vektorje ze itak v kartezicnih koordinatah tako da sta zgornji vsoti kar

\(S=\frac{1}{2}\sum_i (x_i^2+y_i^2) \Delta \varphi\)
\(X=\frac{1}{2}\sum_i x_i(x_i^2+y_i^2) \Delta \varphi\)
\(Y=\frac{1}{2}\sum_i y_i(x_i^2+y_i^2)\Delta \varphi\)
Ce gledas po eno stopinjo je \(\Delta\varphi=\frac{\pi}{180}\)

Medo5
Posts: 26
Joined: 8.2.2007 9:08
Location: Ljubljana
Contact:

Re: Konstrukcija elipse

Post by Medo5 » 2.5.2008 16:24

Sedaj pa mi ni nič več jasno. Navajam kar konkretne številke, s katerimi delam. Zaenkrat sem še v Mathematici, tako da bug v programu odpade.
Torej delam na elipsi s strani:http://math.fullerton.edu/mathews/n2003 ... nk_10.html
Trenutna enačba za center je s strani:http://mathworld.wolfram.com/Ellipse.html odstavek 19/20.
Enačba vrne rezultat 6,6, ki je pravilen.
Zatakne pa se pri kotu oz a',b'.
Iz prvega linka je razvidno, da sta člena a in c enaka ->17x^2; 17y^2.
V enačbah za kot in polosi pa se pojavi člen (a-c) oz (c-a), ki je po izračunu enak nič. Posledica: "devide by zero".
Čudna je ta matematika :cry: .

Lp; Jan

Medo5
Posts: 26
Joined: 8.2.2007 9:08
Location: Ljubljana
Contact:

Re: Konstrukcija elipse

Post by Medo5 » 2.5.2008 16:35

Center elipse bi lahko našel tudi na bolj primitiven način, tako da vzameš vekotrja 0/180 in izračunaš (a+b)/2. Potem vzameš vektorja 90/270 in ponovno izračunaš enako->dobiš nov center, ki je bljižji pravemu. Po nekaj iteracijah prideš v pravi center. Ampak med tem pa vsakič znova računaš vektorje, kar mi ni včeš. Lahko bi računal samo te štiri, ampak zaradi šuma in napak na sliki je to premalo.
Sedaj preko vseh 360 točk povlečem polinom 10stopnje in iz njega bom računal radije oz točke. S tem se znebim motenj. To imam tudi že spisano in deluje super. Rad bi samo še dobil elipso iz petih točk in je problem skorajda rešen.

Drgače pa hvala za idejo, ki nikoli ne škodi :).

Lp; Jan

User avatar
Aniviller
Posts: 7263
Joined: 15.11.2004 18:16

Re: Konstrukcija elipse

Post by Aniviller » 2.5.2008 17:02

Ja opravka imas ravno z elipso pod kotom 45 stopinj. Pri kotu lahko uporabis namesto ArcTan[y/x] raje ArcTan[x,y] ki obravnava vse posebne primere. Mislim tudi da sva uporabila razlicne oznake za koeficient pri xy.
No, povprecenje je vedno bolj smiselno od iteracije.

Drugace, glede na to, da delas z mathematico lahko racunas z vec kot 5 tockami. Naredi matriko oblike
\(A=\begin{bmatrix}
x_1^2&x_1y_1&y_1^2&x_1&y_1\\
x_2^2&x_2y_2&y_2^2&x_2&y_2\\
x_3^2&x_3y_3&y_3^2&x_3&y_3\\
\vdots&&&&
\end{bmatrix}\)

s poljubno tockami v visino. Potem uporabi funkcijo PseudoInverse[A] in z dobljeno matriko pomnozi vektor s toliko komponentami, kolikor je tock (vse komponente so 1, lahko uporabis Table[1, {n}]). dobis vektor \(a,b,c,d,f\) (oz. kakrsnekoli oznake ze imas). Ta metoda bo bolj ziher dala elipso. Potem dobis sredisce (tudi bolje , da sistem dveh enacb, ki sem ti jih napisal, napises z matriko ker ti bo mathematica resila tudi za posebne primere), naredis matriko
\(B=\begin{bmatrix}
a&c/2\\
c/2&b
\end{bmatrix}\)

ce je a clen pri x^2, b pri y^2, c pri xy.
Imas se
\(F=1+a x_0^2+by_0^2+cx_0y_0\)
Potem naredis
Eigensystem in dobis lastne vrednosti, ki sta
\(\lambda_{1,2}=\frac{F}{r^2_{1,2}}\)
ce sem zdaj z \(r_{1,2}\) oznacil obe polosi. Lastna vektorja sta pa smeri glavnih osi elipse.

Medo5
Posts: 26
Joined: 8.2.2007 9:08
Location: Ljubljana
Contact:

Re: Konstrukcija elipse

Post by Medo5 » 2.5.2008 17:41

Hvala za razlago. Mogoče veš, kje je hakelj pri enačbah iz wikipedie?

Mathematico uporabljam samo sedaj, ko preizkušam in raziskujem vse skupaj. Potem je nebo več, zato se na to ne morem zanašati.

Lp; Jan

Medo5
Posts: 26
Joined: 8.2.2007 9:08
Location: Ljubljana
Contact:

Re: Konstrukcija elipse

Post by Medo5 » 3.5.2008 2:02

Poizkušam tvoj primer s psevdoinverzno matriko, ampak negre. Javi mi napako že pri množenju matrike z vektorjem. V matriki A imam npr 10 točk(10x5), množim pa jo z {1,1,1,1,1,1,1,1,1,1}.
Žal ne razumem, kaj bi sploh dobil s tem, če jo pomnožiš z ena? Kako dobiti vrednosti parametrov a,b,... ?

Sem prišel na idejo, če uspem vse narediti v mathematici, lahko kasenje vse to napišem v svoj program. Ampak zaenkrat mi še v matemathici ne deluje.

Šenkrat hvala za pomoč :) .

Lp; Jan

User avatar
Aniviller
Posts: 7263
Joined: 15.11.2004 18:16

Re: Konstrukcija elipse

Post by Aniviller » 3.5.2008 8:29

Dimenzije matrike morajo biti prave. Tvoja matrika ponazarja koeficiente leve strani enacbe, vektor enk pa desne strani - ta je vedno 1:
\(a x^2+b xy+ cy^2+dx +fy=1\)
Vsaka vrstica je svoja enacba (za eno izmed tock). Tvoja matrika mora imeti 5 stolpcev in 10 vrstic. Psevdoinverz pa ravno obratno. Matriko z vektorjem mnozis s piko:

primer:

Code: Select all

{{1, 0, 4}, {0, 1, 2}}.{1, 1, 1}
Matriko si ogledas takole

Code: Select all

A//MatrixForm

Post Reply