TSP - TRANSFORMATION SPHERE POINTS TO 2D PLANAR DIAGRAM
Firstly let's analyze something about SPHERE properties...
Let's say that we know area of sphere which is derived from integral calculus - it goes something if I can recall 2*2R*pi*int(cos x)|0->(pi/2)... When we compute we get 4*R^2*pi...
Now let's analyze something more visual about how equatorial distance shrinks from 2*r*pi to 0 all the way to the poles...
What would you say - it looks familiar to something like when r=R*cos(beta) goes from R to 0 => beta goes from 0 to pi/2; in the same time equatorial distance changes from 2*R*pi to 0, with the same relation as we wrote 2*r*pi...
So we can say it clearly that area of hemisphere is similar to half of ellipse with a=R*pi and b=R*4/pi... Can we assume that area of sphere is 2 areas of those half ellipses representing hemispheres, or just single ellipse area = a*b*pi = R*pi*R*4/pi*pi = 4*R^2*pi...
But can we see from that ellipse real longitude and latitude 2D diagram of points that are graphically identical to 3D sphere body... I don't really know, but it looks that that representation don't fulfill real spherical geometrical properties... Then what picture should be more appropriate... I am guessing something like circle, but with what radius? Let's see : area of circle = R^2*pi and area of sphere = 4*R^2*pi... Let's now say R of sphere is r... So we get R^2*pi=4*r^2*pi... From here we can say 4*r^2=R^2 and we have here R=2*r, so radius of circle is actually diameter of sphere... And that's it... That's the most appropriate picture... But now what? If we randomly place points on sphere what can we say about their transformation to diagram... Firstly for RND points on sphere we can say that the most appropriate representation of adequate coordinate system is not cartezian, but spherical, so we have angle in plane (along Z axis) - alpha and angle in vertical plane of sphere origin and first projection of 3D point - beta, last figure important and constant in relation of sphere origin and 3D point is their distance - R (radius)...
So we can say : pt=R*cos(beta)*cos(alpha),R*cos(beta)*sin(alpha),R*sin(beta)...
And on the 2D diagram we analyzed (r of diagram = 2R), so pt=r/2*cos(beta)*cos(alpha),r/2*cos(beta)*sin(alpha),r/2*sin(beta)...
Now let's analyze 2 RND points on 2D diagram : pt1 and pt2; we can see that :
delta X = abs(r/2*cos(beta1-beta2)*cos(alpha1-alpha2));
delta Y = abs(r/2*cos(beta1-beta2)*sin(alpha1-alpha2));
delta Z = abs(r/2*sin(beta1-beta2));
If we assume that in 2D diagram points represent spherical 3D points, we can say that if we solve TSP in 2D diagram it's not really fulfilling all relations that are correct in terms of areal relation... We can assume that if X axis of 2D diagram represent equatorial circular length, we should say that -X=>+X = 2*R*pi and in 2D diagram -X=>+X = 2*r = (4*R)!... So real 2D representation that is adequate for representing relations are not static, but dynamic; it references rotation along Y axis of 2D diagram in which all points rotate and change their positions assuming that rotational angle is something dynamic and goes from 0 to 2*pi radians... So if we say that 0 rotation is = +X axis, X=R*cos(beta)*cos(0) on sphere and it would be X=r/2*cos(beta)*cos(0) on diagram and if rotation angle is pi/2 then X=(R or r/2)*cos(beta)*cos(pi/2) = 0 [cos(pi/2)=0], meaning somewhere on Y axis points (from (-R or -r/2) to (R or r/2)) and so on, and so on... But when we say Y axis on 2D diagram, we are thinking on Z axis on sphere, so pt=X,Y on 2D diagram is actually pt=r/2*cos(beta)*cos(alpha),r/2*sin(beta) and on sphere already stated pt=X,Y,Z=R*cos(beta)*cos(alpha),R*cos(beta)*sin(alpha),R*sin(beta)...
Now let's see what real distance between 2 points are... D=sqrt[(delta X)^2+(delta Y)^2+(delta Z)^2], but this is somewhat not so elegant for thinking... Firstly, if we know delta elevation between 2 points, we can say that delta Z is dependable from delta beta angle, so delta beta = asin [(delta Z)/R]; now if we know delta beta, we can say delta alpha = acos [R*cos(delta beta)]... Now if we have delta alpha and delta beta, we can have delta gamma which is actually value of real 3D arc length times R... Simply by Pitagora : delta gamma ^2 = delta alpha ^2 + delta beta ^2; delta gamma = sqrt (delta alpha ^2 + delta beta ^2)... 3D arc length = ARC = R*sqrt[{acos[R*cos{asin[(delta Z)/R]}]}^2+{asin[(delta Z)/R]}^2]...
Now let's concentrate on real 2D situation that's not dependable of rotation around Y axis of 2D diagram or Z axis of 3D sphere...
So we have real arc lengths dependable of : gamma1 (p1-p2), gamma2 (p2-p3), gamma3 (p1-p3), ...
Actually we found combinations of all point pairs between each points without repetitions...
(foreach p1 plst
(setq plst (cdr plst))
(foreach p2 plst
(setq p1p2arclenlst (cons (list p1 p2 (arclen p1 p2)) p1p2arclenlst))
)
)
So we map points : p1, p2, p3, ... dependable of 2D triangulation diagram where all arcs lengths are real distances and neither of triangles must not cross previous triangle, or be inside possible larger one (we have 2 solutions of circle-circle intersections for constructing triangulations between 2 points...)...
Possible start p1=0,0; p2=arclen(p1,p2),0; p3=arclen(p1,p3)*cos(a),arclen(p1,p3)*sin(a) = ci(p1,arclen(p1,p3))Xci(p2,arclen(p2,p3)); p4= ci(p1,arclen(p1,p4))Xci(p3,arclen(p3,p4)) or ci(p2,arclen(p2,p4))Xci(p3,arclen(p3,p4)) -- already here we have branching and we must decide which path is better from p1 or p2 --; then for p5 branching through p1-p4 or p3-p4 or through p2-p4 or p3-p4 ...
We solve 2D TSP on triangulation and we remember correct order of point list...
That would be good only if triangulation would satisfy real disposition which would assume that all relations between points are compact and unique... According to branching, that would not be correct, so we still must go through 2D diagram and create rotational dynamic TSP solutions based on sample rotational angle incrementations from 0 to 2*pi radians...
Transformational formula for 3D sphere to 2D diagram is like already stated :
pt=X,Y=r/2*cos(beta)*cos(alpha),r/2*sin(beta); but let's say that rotational angle is theta, so :
pt=X*cos(theta),Y=r/2*cos(theta)*cos(beta)*cos(alpha),r/2*sin(beta)...
Now for theta1, theta2,..., theta11 ; we could have TSP1, TSP2,..., TSP11 with incremental rotational angle of 30 degree...
But could we use real distances for TSP algorithm instead of used (distance) function, something like :
(defun _distance ( p1 p2 / d R ) ;; used bp as lexical global as 3D sphere center ;;
(setq R (distance bp p1))
(setq d (* R (sqrt (+ (expt (acos (* R (cos (asin (/ (abs (cadr (mapcar (function -) p2 p1))) R))))) 2) (expt (asin (/ (abs (cadr (mapcar (function -) p2 p1))) R)) 2)))))
)
and just replace in the code of TSP : "(distance " with "(_distance "...
Finally, what should we do with different TSP mapped point lists if they differ...
Beside this, given the fact that projection have from elevation view of 2D diagram likewise TOP and BACK sides, we could have overlapping points that are opposed to each other... So each TSP solution is TOP+BACK (alpha(0,pi) and alpha(pi,2*pi))...
Final conclusion :
From complexity reasons, 2D TSP is not really useful in terms of transformations from 3D spherical points distribution, further more to dissect even more, when we assume that we dynamically watched rotational dispositions of points along Y axis - corresponding to Z rotation of sphere, we could say that we watched longitudinal section of sphere and we looked points only from projection of Z axis of 2D diagram or some axis in XY plane of 3D sphere; so here we could say that we could have rotational axis from any direction around Z of 2D diagram, meaning infinite number of axises but from only single longitudinal section/elevation plane of view, whereas we could also say that that 2D diagram could have also been viewed from any Y rotational angle of diagram / Z rotational angle of sphere, meaning infinite number of elevations times infinite number of axises of each elevation = infinite^2 number of TSP solutions all with (TOP+BACK) representations of point distributions...
This all is so sad, but true...
So long from me,
Regards, M.R.
[EDIT]
Fooling we around about 2D TSP algorithm, it simply states that just by changing point data from 2D to 3D, we are in condition to solve 3D TSP... Simply we replace Convex Hull with 3D Convex Hull, where we are using TOP projection and FRONT one in case that in first projection (TOP) we have overlappings of points with different elevation...
Now for spherical aspect - we use RND points on sphere, and for intersection checking, we have 2 vectors - 2 tetives of sphere, so we find plane 2 points + origin of sphere, and 2nd plane (similary) => we find vector of intersection of 2 planes with origin as origin of sphere and 2nd point with distance R... So if that line intersect both tetives, then it's crossing and we then continue with reconstructing, by taking 2 shortest tetives and removing 2 originals...
Sincerely, yours, M.R.
[/EDIT]
TSP – TAČKE TRANSFORMACIJE SFERE U 2D PLANARNI DIJAGRAM
Prvo hajde da analiziramo nešto o svojstvima SFERE...
Recimo da znamo površinu sfere koja je izvedena iz integralnog računa - nešto ide ako mogu da se setim 2*2R*pi*int(cos x)|0->(pi/2)... Kada izračunamo dobijamo 4*R^2*pi...
Hajde sada da analiziramo nešto vizuelnije o tome kako se ekvatorijalna udaljenost smanjuje sa 2*r*pi na 0 sve do polova...
Šta biste rekli - izgleda poznato kao kada r=R*cos(beta) ide od R do 0 => beta ide od 0 do pi/2; u isto vreme ekvatorijalna udaljenost se menja sa 2*R*pi na 0, sa istim odnosom kao što smo napisali 2*r*pi...
Dakle, možemo jasno reći da je oblast hemisfere slična polovini elipse sa a=R*pi i b=R*4/pi... Možemo li pretpostaviti da je površina sfere 2 oblasti tih poluelipsi koje predstavljaju hemisfere, ili samo jedna oblast elipse = a*b*pi = R*pi*R*4/pi*pi = 4*R^2*pi...
Ali da li možemo da vidimo iz te elipse stvarnu dužinu i širinu 2D dijagram tačaka koje su grafički identične telu 3D sfere... Ne znam zaista, ali izgleda da taj prikaz ne ispunjava stvarna sferna geometrijska svojstva... Koja bi onda slika bila prikladnija... Pretpostavljam nešto kao krug, ali sa kojim radijusom? Da vidimo: površina kruga = R^2*pi i površina sfere = 4*R^2*pi... Recimo sada da je R sfere r... Dakle, dobijamo R^2*pi=4*r ^2*pi... Odavde možemo reći 4*r^2=R^2 i imamo R=2*r, dakle poluprečnik kruga je zapravo prečnik sfere... I to je to... To je najprikladnija slika... Ali šta sad? Ako nasumično postavimo tačke na sferu, šta možemo reći o njihovoj transformaciji u dijagram...
Sada da vidimo koliko je stvarno rastojanje između 2 tačke... D=sqrt[(delta X)^2+(delta Y)^2+(delta Z)^2], ali ovo donekle nije tako elegantno za razmišljanje. Prvo, ako znamo delta elevaciju između 2 tačke, možemo reći da je delta Z zavisna od delta beta ugla, tako da je delta beta = asin [(delta Z)/R]; sada ako znamo delta beta, možemo reći delta alfa = acos [R*cos(delta beta)]... Sada ako imamo delta alfa i delta beta, možemo imati delta gama što je zapravo vrednost stvarne dužine 3D luka puta R... Jednostavno od Pitagore : delta gama ^2 = delta alfa ^2 + delta beta ^2; delta gama = sqrt (delta alfa ^2 + delta beta ^2)... 3D dužina luka = ARC = R*sqrt[{acos[R*cos{asin[(delta Z)/R]}]}^2+ {asin[(delta Z)/R]}^2]...
Sada hajde da se koncentrišemo na stvarnu 2D situaciju koja ne zavisi od rotacije oko Y ose 2D dijagrama ili Z ose 3D sfere...
Dakle, imamo stvarne dužine luka zavisne od: gamma1 (p1-p2), gamma2 (p2-p3), gamma3 (p1-p3), ...
Zapravo smo pronašli kombinacije svih parova tačaka između svake tačke bez ponavljanja...
(foreach p1 plst
(setq plst (cdr plst))
(foreach p2 plst
(setq p1p2arclenlst (cons (lista p1 p2 (arclen p1 p2)) p1p2arclenlst))
)
)
Dakle, mapiramo tačke: p1, p2, p3, ... zavisno od 2D triangulacionog dijagrama gde su sve dužine lukova realne udaljenosti i nijedan od trouglova ne sme da prelazi prethodni trougao, ili da bude unutar moguće većeg trougla (imamo 2 rešenja kružnice - kružne preseke za konstruisanje triangulacija između 2 tačke...)...
Mogući početak p1=0,0; p2=arclen(p1,p2),0; p3=arclen(p1,p3)*cos(a),arclen(p1,p3)*sin(a) = ci(p1,arclen(p1,p3))Xci(p2,arclen(p2,p3)); p4= ci(p1,arclen(p1,p4))Xci(p3,arclen(p3,p4)) ili ci(p2,arclen(p2,p4))Xci(p3,arclen(p3,p4)) -- već ovde imamo grananje i moramo odlučiti koji je put bolji od p1 ili p2 --; zatim za p5 grananje kroz p1-p4 ili p3-p4 ili kroz p2-p4 ili p3-p4 ...
Rešavamo 2D TSP na triangulaciji i pamtimo tačan redosled liste tačaka...
To bi bilo dobro samo ako bi triangulacija zadovoljila realnu dispoziciju koja bi pretpostavljala da su sve relacije između tačaka kompaktne i jedinstvene... Prema grananju, to ne bi bilo tačno, tako da ipak moramo proći kroz 2D dijagram i kreirati rotaciono dinamička TSP rešenja na osnovu povećanja ugla rotacije uzorka od 0 do 2*pi radijana...
Transformaciona formula za 3D sferu u 2D dijagram je kao što je već rečeno:
pt=X,Y=r/2*cos(beta)*cos(alfa),r/2*sin(beta); ali recimo da je rotacioni ugao teta, dakle:
pt=X*cos(teta),Y=r/2*cos(teta)*cos(beta)*cos(alfa),r/2*sin(beta)...
Sada za theta1, theta2,..., theta11; mogli bismo da imamo TSP1, TSP2,..., TSP11 sa inkrementalnim rotacionim uglom od 30 stepeni...
Ali da li bismo mogli da koristimo stvarne udaljenosti za TSP algoritam umesto korišćene funkcije (distance), nešto poput:
(defun _distance ( p1 p2 / d R ) ;; koristi se bp kao leksička globala kao centar 3D sfere ;;
(setq R (distance bp p1))
(setq d (* R (sqrt (+ (expt (acos (* R (cos (asin (/ (abs (cadr (mapcar (function -) p2 p1))) R))))) 2) (expt (asin (/ (abs (cadr (mapcar (function -) p2 p1))) R)) 2)))))
)
i samo zamenite u kodu TSP-a: "(distance " sa "(_distance "...
Konačno, šta da radimo sa različitim TSP mapiranim listama tačaka ako se razlikuju...
Osim toga, s obzirom na činjenicu da projekcije imaju sa visinskog pogleda 2D dijagrama isto tako GORNU i ZADNJU stranu, mogli bismo imati tačke preklapanja koje su suprotne jedna drugoj... Dakle, svako TSP rešenje je TOP+NAZAD (alfa(0,pi) i alfa(pi,2*pi))...
Konačan zaključak:
Iz razloga složenosti, 2D TSP nije baš koristan u smislu transformacija iz distribucije 3D sfernih tačaka, dalje da bi se secirao još više, kada pretpostavimo da smo dinamički posmatrali rotacione dispozicije tačaka duž Y ose – što odgovara Z rotaciji sfere, mi bi mogli reći da smo posmatrali uzdužni presek sfere i posmatrali tačke samo iz projekcije Z ose 2D dijagrama ili neke ose u XY ravni 3D sfere; tako da ovde možemo reći da bismo mogli da imamo ose rotacije iz bilo kog smera oko Z 2D dijagrama, što znači beskonačan broj osa, ali samo iz jednog uzdužnog preseka/visinske ravni, dok bismo takođe mogli reći da je taj 2D dijagram takođe mogao biti posmatran iz bilo kog Y rotacionog ugla dijagrama / Z rotacionog ugla sfere, što znači beskonačan broj elevacija puta beskonačan broj osa svake elevacije = beskonačan^2 broj TSP rešenja sva sa (TOP+NAZAD) prikazima tačaka distribucije...
Sve je ovo tužno, ali istinito...
Tako dugo od mene,
Pozdrav, M.R.
[EDIT]
Glupirali se mi oko 2D TSP algoritma, on jednostavno kaže da samo promenom podataka o tačkama iz 2D u 3D, mi smo u stanju da rešimo 3D TSP... Jednostavno zamenimo Convex Hull sa 3D Convex Hull, gde koristimo TOP projekciju i FRONTALNU u slučaju da u prvoj projekciji (TOP) imamo preklapanja tačaka sa različitim elevacijama...
Sada za sferni aspekt - koristimo RND tačke na sferi, a za proveru preseka imamo 2 vektora - 2 tetive sfere, tako da nalazimo ravan 2 tačke + centar sfere, i 2 ravan (slicno) => nalazimo vektor preseka od 2 ravni sa centrom sfere i drugom tačkom sa rastojanjem R... Dakle, ako ta linija seče obe tetive, onda se javlja ukrštanje i onda nastavljamo sa rekonstrukcijom, uzimajući 2 najkraće tetive i uklanjajući 2 originalne...
S poštovanjem, M.R.
[/EDIT]