VD for polylines and polygons

I've been hacking away at openvoronoi, adding support for polylines and polygons.

The code I had in November works with individual non-intersecting line segments, like this:

Note how each vertex in the figure above is of degree three, i.e. there are three edges incident on each vertex. There's something about the number three, or triangles, or both, that makes planar graphs of degree three particularly nice to work with.

Here's the same figure with some notes describing the elements. The line-sites are drawn in yellow, and are associated with their left R(L+) and right R(L-) regions. The purple lines are called separators, and they define the region associated with the start- or end-point of a line-site. The three possible edge-types are also shown: LineEdge between two point-sites, LineEdge between two line-sites, and a Parabolic (PointLine) edge between a point-site and a line-site.

Now, things get more complicated when we want to 'glue' two line-segments end-to-end in a polyline, or glue three or more line-segments together to form a polygon. Vertices are not necessarily of degree three any more. In fact the vertex degree is essentially unbounded, as you can start/end arbitrarily many line-segments at the same vertex. The solution I am using is to introduce what I call a null-face with zero-length null-edges around each point-site to which more than one line-segment connects. The mental picture is much like that of a key-chain, or mountaineering carabiners that are hooked-in to a loop. When we want to use the a vertex as a start/end-point for a segment we 'hook-in' to the null-face:

This introduces a number of new rules and associated code for how vertices should be created, removed, and moved around a null-face, but it seems to work somehow now:

Note how these null-faces and the circular null-edges around each end-point result in degree three vertices, which are much nicer to deal with in the algorithm. For example, the null-face around vertex "0" is 40->85->86->41->39. Without the null-face construction this vertex would be of degree five. Here is an annotated version of the same picture:

This image shows how the diagram divides the plane into regions associated with endpoints such as R(0) and with the right/left side of a line-segment such as R(0-29) and R(29-0). The null-edges that form null-faces around each end-point are drawn in white.

Of course, these null-edges are only a topological construction. Geometrically we can position each vertex on a null-face at the location of the encircled point-site. This effectively contracts away the zero-area null-faces, and the result is the diagram we want:

The code now runs for a few select test-cases. To be continued...

Update: The code now seems to work also for random polygons with a large number of vertices. Here is one with 400 vertices:

and 3200-vertices:

Call graph

For profiling I made a small c++ program which calculates a poisson voronoi diagram. When called through valgrind like this (under valgrind the program will run roughly 50 times slower than normal)
valgrind --tool=callgrind -v ./ovd_tst --n 1000
I can then use kcachegrind to draw a call graph.

I thought the nearest-neighbor grid-search (grid_find_closest_face()) would cost much more than it does.

The callee map may in fact better visualize where CPU time is spent:

The map changes significantly if we change the solver number type to double, which is faster but less accurate. A better strategy might be to run the fast solver(double) first, then check the quality of the solution, and run the slow solver(qd_real) only if necessary.

In this map there doesn't seem to be an obvious bottleneck or 'hot spot' in immediate need of optimizing, since there are 6-8 blocks/functions each taking roughly 10% of the CPU time.

After some tweaking the benchmark (with the double solver) run gives these results:

Poisson Voronoi diagram statistics

On g+, John Baez linked to work by Henk Hilhorst on the probability of finding voronoi cells with n sides in a poisson voronoi diagram.

A poisson voronoi diagram has point sites randomly and uniformly distributed, like this:

Here's the distribution I came up with, after counting the edges for each voronoi cell from 200 runs where openvoronoi generated the diagram for 100k point-sites in each run. The green line is Hilhorst's prediction. I'm assuming poisson statistics, so if the bin-count for a certain n is fn, I've drawn errorbars of length sqrt(fn). Cells with n=15 or n=16 are so rare that the statistical error is of the same size as the probability (but it does agree with Hilhorst's prediction). Among the 20M cells I looked at I did not find n >= 17. For n=17 the predicted probability is 2e-9, so there's should be a 50% chance of seeing one if I would produce 500M random cells (that would take about 7 hours of CPU time).

The relevant papers are

The logarithmic y-axis hides the fact that the distribution is very peaked around n=6, so here is a plot with a linear y-axis:

Colorhug build

The other parts for a Colorhug already arrived, and we got the missing color sensor TCS3200D, from Mouser last week.

Please don't laugh at my SMD soldering skills 🙂

I made a first PCB using the original pcb-layout from the git repo, but the combination of a printer driver that produced a fuzzy mask and less than perfect etching skills didn't produce a satisfactory result. I then re-drew the GND copper-fill and some other traces on the PCB for bigger clearances and easier etching. Printed from adobe acrobat on windows the mask also has much better resolution than when printing from Document Viewer/Ubuntu.

Here are my modified masks in PDF format: hardware_etched_2011dec04 (note that the board outline is enlarged)

The PCB is clearly made for commercial production. There are vias under the microcontroller, which you can see from the pictures I have filed down after soldering so that the chip will fit on top. This isn't an issue with a commercially produced PCB where the vias are plated. Also, I noticed while starting to assemble the board that the large pad on the 3.3V regulator in the upper right corner will short out the trace drawn under it. Thus the silicone tape as insulation in the following picture. This is also not an issue with a commercial PCB since it will have an insulating soldermask.

Then on to programming. From the servodrive adventure I have an ICD2 programmer/debugger. However using it was challenging. I first tried 64-bit Windows 7. The latest Microchip MPLAB IDE does ship with 64-bit drivers, but they are hidden away in a special place, and require manual installation. No luck here, from device-manager/update-driver I couldn't get Win7 to recognize a valid driver using the instructions supplied.

I then tried 64-bit Ubuntu11.10. They have a Java version of MPLAB, called MPLAB X. It installs and runs nicely, but when I started digging in the documentation it turns out that product only supports the newer ICD3 programmer/debugger, not my older ICD2! (there might be ICD2 support in some old beta-version of MPLAB X, but I didn't search).

Oh well, it's nice we keep those old 32-bit Windows XP machines around in the lab! So I repeat for the third time the whole download and installation process on an old XP machine. That seems to work. The C-compiler which I vaguely remember being free previously now has a 60-day trial period after which Micrchip proudly proclaims it will stop producing nice binaries and start producing crap binaries. Strange. There's both a bootloader and a firmware project in the colorhug firmware repo. My guess is I only need to build and deploy the bootloader, and the firmware can be flashed from any machine after that. The bootloader requires a USB-library, which I didn't manage to find before I had to quit for the day... To be continued.

Note to self: future projects should use ATMEL or other microcontroller which (a) has a free/open-source toolchain for building the firmware, and (b) can be programmed directly over USB. The 6-pin ICSP connector is just big and ugly on a cute little board like this.

Random polygons with CGAL

At some point I'm going to need random simple polygons for testing my voronoi diagram code. CGAL includes a function random_polygon_2 which uses the "2-opt" heuristic (see Auer&Held-1996).

I wrote a minimal boost::python wrapper around this function in order to test it and draw the polygons using vtk. Here are some examples of random polygons with randomly placed vertices inside the unit circle:


The one with 8k vertices takes 150 seconds of i7-2600K CPU time to generate. The worst-case running time of this algorithm is slow, O(n^4 log n), but it practice it seems better than O(n^3):

Code: https://github.com/aewallin/randompolygon

Another Nokia N9 vs. Garmin GPS test

These results are much like my previous ones. Close to buildings or other difficult places the N9 GPS performs significantly worse than the Garmin. This is somewhat surprising since the N900 performs very similar to a Garmin. Could better GPS-data on the N9 be just a software-update away? When is someone going to try to get TJ Lindfors's RTK-GPS Openmoko hack to work on the N9 ?!

Flower time-lapse movie

Still images (Logitech C270 webcam, modified for macro by placing a f=+150mm singlet lens in front of it) collected with 1 minute intervals for about a week. The flower grows too slowly to be interesting...

JPEGs assembled into a movie with

mencoder -mf type=jpeg:fps=100 mf://frames/*.jpeg -nosound -ovc lavc -lavcopts vcodec=mpeg4:mbd=2:trell:autoaspect:vqscale=3 -vf scale=1280:720 -o time-lapse.avi

Random line-segment voronoi diagram

Update3: version 11.10-148 now goes to 16k line-sites without errors or warnings:

Update2: This diagram with 8k vertices clearly has errors:

Update: Version 11.10-141 now copes with 4k random segments. But I don't know of any smart way to check the diagram for correctness..

Constructing the vd for random (non-crossing) line-segments is a reasonable stress-test for my vd-algorithm. When you've fixed one bug, just increase the number of line-segments by a factor of two and you will most likely uncover another! It now runs OK up to 2048 line-segments (yes, that does imply I get a segfault at 4096!).

There's some slowdown from 5us*n*log(n) in september 2011 (for just point-sites), to this code which runs in about 15 to 20us*n*log(n) when inserting the point-sites. Line-sites take longer, about 200us*m*log(m) for m line-sites.