jaroslawwiosna / equidistant Goto Github PK

Description

Let's randomly put 4 points on unit sphere. The goal is to move the points to the following configuration:

So the points coordinates are*:

p1 = ( 0, -1/3 * pi)
p2 = ( 0, 1/3 * pi)
p3 = ( 2/3 * pi, 0)
p4 = ( 4/3 * pi, 0)

There are an infinitive number of ways to put the points so they are equally distant

Honestly, I am not sure about coordinates anymore; according to wiki, this configuration is identical or, at least similar to tetrahedron

How to do it?

Firstly, every single point on unit sphere can be represented by two parameters:

1. phi - [0, 2*pi)
2. theta - [-pi/2, pi/2]

Secondly, on a sphere we have two points, that are equally distant from three points:
(x, y) and (x + pi, y * (-1))

....so, the algorithm is:

• Pick one point. Let's call it A
• Find three closest points to A. Sort them and let's call them B (is the closest), C, D.
• Create 4 new points by adding and subtracting to phi and theta 0.0001 rad
• Check which (if any) is more optimal than A, then this point is the new A.
• Repeat procedure for remaining points. And once again for all points, and again...

What is more optimal?

According to my understanding of the problem we want A to move to (x, y) or (x + pi, y * (-1))
And when we have only 4 points on sphere in total, it is better to point to move where the distance from B, C, D is greater.

only 4 points? - image 20 points on a sphere, it's obvious, that we want that point (from the proposed two) that is closer to 3 neighbours. (I cannot explain it with words, if anyone wants a picture, please, let me know)

What is the stop criterium?

I think that point A shouldn't move when distance(A,B) = distance(A,C) = distance(A,D)

My questions?

1. Perhaps problem would be easier to solve on the surface of unit cube?
2. How to define distance function? My suggestions:

• using the Pythagorean theorem twice click
• absolute value of difference between phis + absolute value of difference between thetas
• And maybe final result of calculate distance function should be the sum of d(A,B) + d(A,C) + d(A,D)

3. What about moving A so the distance(A,B) will be greater? Eventually, C will be closer to A. Then let's move A so the distance(A,C) will be greater. Finally d(A,B) = d(A,C) = d(A,D), aren't they?
4. What about moving all points in parallel in one step?
5. Since the problem in 3D is not trivial, what about 2D? Let's imagine unit square and move them in a similar way? So, two points will move to the opposite corners, 4 points will move to corners, what about 6 points? Just like 4 points case and an additional one in the very center?
6. I wrote earlier, that 4 new points are created

• A1( x - 0.0001, y)
• A2( x + 0.0001, y)
• A3( x, y - 0.0001) <-- warning! What if y equals -pi/2 ?
• A4( x, y + 0.0001) <-- warning! What if y equals pi/2 ? Theta has value between -pi/2 and pi/2. But it shouldn't be a problem, because we calculate sin( X ) or cos( X )

7. Am I missing something?

...but what is it all about?

Sometimes images are better for imagination, so please, have a look at platonic solids.
Well, we know how it should look for 4 points, and 8 points...
What about five or six points? I cannot imagine that for 5 or 6 or 7 we can reach steady state
Nevertheless, I want to see transient process.

(by the way, if process won't reach steady state for sure..., can we call it transient?)

Is it possible to circumscribe a sphere on 5 points (or 6, 7, 9...) that are equally distant to the 3 closest neighbours?

I hope we can say circumscribe (1 ,2) when talking about sphere...

After ddecf10

From starting position results are:

After moving...
0.--	0.870781 0.491669 -0.000994549 0.514006 -0.000994549 
1.--	3.01584e-07 8.71253e-08 1 0.281236 1.5708 
2.--	-1.99689e-07 -2.42214e-07 -1 4.02293 -1.5708 
3.--	0.000133827 -0.000237749 -1 5.22508 -1.57052

...so

A.theta=0
B.theta=pi/2 
C.theta=-pi/2 
D.theta=-pi/2

I think, that's because of theta. When A = ( x , pi/2) x value does not matter at all, so adding or subtracting small value, like 0.0001 won't affect.

Possible fixes?

1. Firstly make theta smaller than pi/2, and create 4 new points: called itLeft, itRight, itUp, itDown by assign phi value of 0, pi/2, pi, 3*pi/2
2. Rotate the sphere so current point A would be (0,0). <-- we do not care about coordinates, so this wouldn't make a difference.

using free() instead of delete results:

➜ equidistant git:(master) ✗ make && valgrind --tool=memcheck --leak-check=full ./equidistant
[ 50%] Built target Sphere
[100%] Built target equidistant
==15755== Memcheck, a memory error detector
==15755== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==15755== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==15755== Command: ./equidistant
==15755==
0.-- 0.413246 0.643593 0.644218 0.7 1
1.-- -0.383297 0.837518 0.389418 0.4 2
2.-- -0.945776 0.134817 -0.29552 -0.3 3
3.-- 0.724292 0.0726716 -0.685653 -0.7555 0.1

==15755== Mismatched free() / delete / delete []
==15755== at 0x4C2EDEB: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x40870A: fun4(std::__cxx11::list<Spherepoint*, std::allocator<Spherepoint*> >&) (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== by 0x408B46: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== Address 0x11d590f0 is 0 bytes inside a block of size 20 alloc'd
==15755== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x407D0E: fun4(std::__cxx11::list<Spherepoint*, std::allocator<Spherepoint*> >&) (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== by 0x408B46: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755==
==15755== Mismatched free() / delete / delete []
==15755== at 0x4C2EDEB: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x408719: fun4(std::__cxx11::list<Spherepoint*, std::allocator<Spherepoint*> >&) (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== by 0x408B46: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== Address 0x11d59150 is 0 bytes inside a block of size 20 alloc'd
==15755== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x407D8B: fun4(std::__cxx11::list<Spherepoint*, std::allocator<Spherepoint*> >&) (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== by 0x408B46: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755==
==15755== Mismatched free() / delete / delete []
==15755== at 0x4C2EDEB: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x408728: fun4(std::__cxx11::list<Spherepoint*, std::allocator<Spherepoint*> >&) (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== by 0x408B46: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== Address 0x11d591b0 is 0 bytes inside a block of size 20 alloc'd
==15755== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x407DFF: fun4(std::__cxx11::list<Spherepoint*, std::allocator<Spherepoint*> >&) (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== by 0x408B46: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755==
==15755== Mismatched free() / delete / delete []
==15755== at 0x4C2EDEB: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x408737: fun4(std::__cxx11::list<Spherepoint*, std::allocator<Spherepoint*> >&) (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== by 0x408B46: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== Address 0x11d59210 is 0 bytes inside a block of size 20 alloc'd
==15755== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x407E7A: fun4(std::__cxx11::list<Spherepoint*, std::allocator<Spherepoint*> >&) (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== by 0x408B46: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755==
99.9988 %
After moving...
0.-- 0.413246 0.643593 0.644218 0.7 1
1.-- -0.383297 0.837518 0.389418 0.4 2
2.-- -0.945776 0.134817 -0.29552 -0.3 3
3.-- 0.724292 0.0726716 -0.685653 -0.7555 0.1

==15755== Conditional jump or move depends on uninitialised value(s)
==15755== at 0x15F73E2D: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F740C1: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F743FC: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F90549: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F93C0F: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F8C14F: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F780F5: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15AF3E76: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15AD3110: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x159AB551: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x159C04B1: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x5907F60: vtkOpenGLDisplayListPainter::RenderInternal(vtkRenderer*, vtkActor*, unsigned long, bool) (in /usr/lib/x86_64-linux-gnu/libvtkRenderingOpenGL-6.2.so.6.2.0)
==15755==
==15755== Conditional jump or move depends on uninitialised value(s)
==15755== at 0x15F73E2D: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F740C1: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F74437: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F90549: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F93C0F: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F8C14F: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15F780F5: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15AF3E76: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x15AD3110: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x159AB551: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x159C04B1: ??? (in /usr/lib/x86_64-linux-gnu/dri/swrast_dri.so)
==15755== by 0x5907F60: vtkOpenGLDisplayListPainter::RenderInternal(vtkRenderer*, vtkActor*, unsigned long, bool) (in /usr/lib/x86_64-linux-gnu/libvtkRenderingOpenGL-6.2.so.6.2.0)
==15755==
==15755== Mismatched free() / delete / delete []
==15755== at 0x4C2EDEB: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x409619: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== Address 0x11d587c0 is 0 bytes inside a block of size 20 alloc'd
==15755== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x40898F: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755==
==15755== Mismatched free() / delete / delete []
==15755== at 0x4C2EDEB: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x409628: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== Address 0x11d58820 is 0 bytes inside a block of size 20 alloc'd
==15755== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x4089BB: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755==
==15755== Mismatched free() / delete / delete []
==15755== at 0x4C2EDEB: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x409637: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== Address 0x11d58880 is 0 bytes inside a block of size 20 alloc'd
==15755== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x4089E7: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755==
==15755== Mismatched free() / delete / delete []
==15755== at 0x4C2EDEB: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x409646: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== Address 0x11d588e0 is 0 bytes inside a block of size 20 alloc'd
==15755== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x408A13: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755==
==15755== Mismatched free() / delete / delete []
==15755== at 0x4C2EDEB: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x409652: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== Address 0x11d58940 is 0 bytes inside a block of size 20 alloc'd
==15755== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x408A3F: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755==
==15755== Mismatched free() / delete / delete []
==15755== at 0x4C2EDEB: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x40965E: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755== Address 0x11d589a0 is 0 bytes inside a block of size 20 alloc'd
==15755== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x408A60: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755==
==15755==
==15755== HEAP SUMMARY:
==15755== in use at exit: 963,472 bytes in 1,290 blocks
==15755== total heap usage: 1,794,857 allocs, 1,793,567 frees, 112,885,947 bytes allocated
==15755==
==15755== 20 bytes in 1 blocks are definitely lost in loss record 17 of 1,016
==15755== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x40896B: main (in /home/osboxes/Downloads/github_matrixlibs2/equidistant/equidistant)
==15755==
==15755== 112 (56 direct, 56 indirect) bytes in 1 blocks are definitely lost in loss record 976 of 1,016
==15755== at 0x4C2FB55: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x15C98F1B: ???
==15755== by 0x15C5D4CB: ???
==15755== by 0x15C5D5B8: ???
==15755== by 0x15C5D627: ???
==15755== by 0x15C5E061: ???
==15755== by 0x15C7C494: ???
==15755== by 0x15C7EEB0: ???
==15755== by 0x15C79F58: ???
==15755== by 0x15C7A08F: ???
==15755== by 0x15C48769: ???
==15755== by 0x15D1B596: ???
==15755==
==15755== 192 (16 direct, 176 indirect) bytes in 1 blocks are definitely lost in loss record 985 of 1,016
==15755== at 0x4C2FD5F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x93741FC: ??? (in /usr/lib/x86_64-linux-gnu/libX11.so.6.3.0)
==15755== by 0x9374770: ??? (in /usr/lib/x86_64-linux-gnu/libX11.so.6.3.0)
==15755== by 0x937604E: ??? (in /usr/lib/x86_64-linux-gnu/libX11.so.6.3.0)
==15755== by 0x937687B: _XlcCreateLC (in /usr/lib/x86_64-linux-gnu/libX11.so.6.3.0)
==15755== by 0x939365F: _XlcDefaultLoader (in /usr/lib/x86_64-linux-gnu/libX11.so.6.3.0)
==15755== by 0x937DE4D: _XOpenLC (in /usr/lib/x86_64-linux-gnu/libX11.so.6.3.0)
==15755== by 0x937E05A: _XrmInitParseInfo (in /usr/lib/x86_64-linux-gnu/libX11.so.6.3.0)
==15755== by 0x9365D3F: ??? (in /usr/lib/x86_64-linux-gnu/libX11.so.6.3.0)
==15755== by 0x936935D: XrmGetStringDatabase (in /usr/lib/x86_64-linux-gnu/libX11.so.6.3.0)
==15755== by 0x9684CD5: ??? (in /usr/lib/x86_64-linux-gnu/libXt.so.6.0.0)
==15755== by 0x9686202: _XtDisplayInitialize (in /usr/lib/x86_64-linux-gnu/libXt.so.6.0.0)
==15755==
==15755== 775,560 (56 direct, 775,504 indirect) bytes in 1 blocks are definitely lost in loss record 1,016 of 1,016
==15755== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==15755== by 0x15C0729C: ???
==15755== by 0x7DA00B3: ??? (in /usr/lib/x86_64-linux-gnu/mesa/libGL.so.1.2.0)
==15755== by 0x7DA0917: ??? (in /usr/lib/x86_64-linux-gnu/mesa/libGL.so.1.2.0)
==15755== by 0x7D9F82B: ??? (in /usr/lib/x86_64-linux-gnu/mesa/libGL.so.1.2.0)
==15755== by 0x7D7A3B4: glXMakeContextCurrent (in /usr/lib/x86_64-linux-gnu/mesa/libGL.so.1.2.0)
==15755== by 0x5A25729: vtkXOpenGLRenderWindow::MakeCurrent() (in /usr/lib/x86_64-linux-gnu/libvtkRenderingOpenGL-6.2.so.6.2.0)
==15755== by 0x5A2507E: vtkXOpenGLRenderWindow::WindowInitialize() (in /usr/lib/x86_64-linux-gnu/libvtkRenderingOpenGL-6.2.so.6.2.0)
==15755== by 0x5A24FCC: vtkXOpenGLRenderWindow::Start() (in /usr/lib/x86_64-linux-gnu/libvtkRenderingOpenGL-6.2.so.6.2.0)
==15755== by 0x5A1A2FF: vtkXRenderWindowInteractor::Initialize() (in /usr/lib/x86_64-linux-gnu/libvtkRenderingOpenGL-6.2.so.6.2.0)
==15755== by 0x645513A: vtkRenderWindow::Render() (in /usr/lib/x86_64-linux-gnu/libvtkRenderingCore-6.2.so.6.2.0)
==15755== by 0x5A2B2E0: vtkXOpenGLRenderWindow::Render() (in /usr/lib/x86_64-linux-gnu/libvtkRenderingOpenGL-6.2.so.6.2.0)
==15755==
==15755== LEAK SUMMARY:
==15755== definitely lost: 148 bytes in 4 blocks
==15755== indirectly lost: 775,736 bytes in 11 blocks
==15755== possibly lost: 0 bytes in 0 blocks
==15755== still reachable: 187,588 bytes in 1,275 blocks
==15755== suppressed: 0 bytes in 0 blocks
==15755== Reachable blocks (those to which a pointer was found) are not shown.
==15755== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==15755==
==15755== For counts of detected and suppressed errors, rerun with: -v
==15755== Use --track-origins=yes to see where uninitialised values come from
==15755== ERROR SUMMARY: 1280002 errors from 16 contexts (suppressed: 0 from 0)

http://gmrand.blogspot.com/2013/01/how-to-vtk-point-picking-with-sphere.html

https://github.com/JaroslawWiosna/equidistant/blob/master/equidistant.cpp#L137-L165