Circle Packings – Week 5

While sadly there were no hikes this week, we did continue to make some pretty nice progress on our circle packing library. One of the main things that we worked on towards the beginning of the week was integrating code from a software called CirclePack into our own library, so that we would be able to use the software to generate circle packings from our hulls. To do this involved importing code from the CirclePack library and then creating our own circle packing class with additional functionality that utilized parts of CirclePack to compute packings. This made for some pretty amazing images, which you’ll see a little later on.

Additionally, you may recall that last week one of the things that I had worked on was creating a function within our convex hull code that randomly generates a specified number of points (in Euclidean 3 space) and then computes the convex hull of those points. Since we wanted to also be able to compute the convex hull of not only points but of circles as well, this week I worked on a creating a function to generate random convex hulls of DiskS2s, which is our class for circles on the sphere. To do this, I utilized the random convex hull function for points in E3 from last week, created maps from the E3 hull to a DiskS2 hull, and added the appropriate links between data structures present in the old hull to the new hull to copy over the combinatorics. Once this function was running successfully, we tested it out by generating a random convex hull of 1000 disks and then using the newly integrated CirclePack code to circle pack the hull. Lastly, we generated the Voronoi diagram of the repacked hull, and got some pretty stellar images, if I do say so myself!

            

Fig. 1: Circle packing of the sphere               Fig. 2: Circle packing and convex hull                 Fig. 3: Convex hull and Voronoi                   with 1000 circles                                                                                                                                                   Diagram

Fig. 4: Circle packing, convex hull, and Voronoi Diagram of sphere with 1000 circles (filtered)

 

Now that we have Voronoi Diagrams on the sphere, we would like to be able to project these diagrams and their corresponding circle packings from the sphere onto a 2D plane. So, another major part of what I worked on this week was adding code to the library to stereographically project points, disks, and arcs from the sphere onto the w = 1 plane (lying above the sphere and tangent to the sphere at the ‘north pole’ point). In order to do this, we created new classes that utilize oriented projective geometry: PointOP2, LineOP2, DiskOP2, and CircleArcOP2, and also added code to be able to draw these new structures on the w = 1 plane. Here is an example of two disks, defined by three points each, located on the sphere, and their projections to the corresponding six points and two DiskOP2s on the w=1 plane.
                                              

Fig. 5: Stereographic projection of two disks                                                              Fig. 6: Stereographic projection of a circular arc from the sphere onto the w=1 plane.                                                                               from the sphere onto the w=1 plane.

Another cool thing which Professor Bowers added to the library is the ability to zoom in and out of a sketch.  This provides for a more convenient interface and some more pretty awesome images, like these two:

Overall, it was a pretty successful week. I’ll admit though that I’m probably most excited at the fact that we’ve ordered custom coasters with our filtered packing on them. Woop!