Fireworks

More on picasa: https://picasaweb.google.com/106188605401091280402/Fireworks201109  (shot using old 20D, which has written EXIF-data dating the pics to 2005...)

See also 2010 and 2009.

Unfortunately moving my blog by exporting an XML-file from the old site and importing it to the new site has not worked too well 🙁 I have all 800 posts, and about 2000 pictures/attachments, but the pictures aren't bound correctly to the posts, so posts with image-galleries don't work too well. Hope to fix this at some point. The wordpress-importer is also somewhat naive in that when importing attachments it simply re-names files (by appending "1") that are already on disk. I have now tried importing three times, which means I have three copies of all files, like so: "file.jpg", "file1.jpg", and "file11.jpg".

vd benchmark

Tuesday update: A few optimizations has shaved about half off the constant, to . This was mainly (a) choosing boost::vecS as the out-edge container for the BGL-graph, and (b) choosing std::vector instead of std::set for a temporary variable in the grid-search for the closest facet. I suspect the runtime is dominated by that grid-search. Profiling would tell.

I did some benchmarking of my vd-code. It is supposed to run in time. Benchmarking turns out to be not so simple. I normally compile without any optimizations, and with a lot of sanity-checks and assert():s all over the code. These checks have worse time-complexity and result in long runtimes with big inputs. Then there are compiler optimization flags like -O or -O3.

I was first running the algorithm by inserting each point from python-code:

    t_before = time.time()
    for p in plist:
        vd.addVertexSite( p )
    t_after = time.time()
    return (t_after - t_before)

which I thought could add some overhead. I also made a version ("batch mode") where we first push all points to c++, and then call a run() method:

    for p in plist:
        vd.pushVertexSite( p )
    t_before = time.time()
    vd.run()
    t_after = time.time()
    return (t_after - t_before)

but this seems to improve runtime only marginally. Here are the results. Runtimes are divided by , so ideally all points should fall on a horizontal line. At best the code now runs in about 10-16 microseconds times .

With 4096 input points the runtime improves from 12s down to 1.3s by turning off sanity-checks and assert():s. It further improves to 0.18s with -O3 and to 0.165s in batch-mode.

As an example, the voronoi diagram for 1000 random points looks like this:

New webhost - installing wordpress

After leaving my bill unpaid at my old webhost, changing DNS-servers for my domain, and setting up a new webhosting account, the site is back up again on the new webhost, kapsi.fi. It went down sometime in the afternoon on Friday, and it started working again at noon on Sunday.

I will install the plugins, upload pictures/attachments, and restore the database from the old site over the next few days...

WordPress install:

  • Downloaded latest wordpress as a zip-file, unzipped on laptop and uploaded with FileZilla/FTP to webhost.
  • Edited wp-config.php by adding MySQL server name, database name, username, and password.
  • completed wordpress install by going  /wp-admin/install.php  and entering some info
  • Trying the Black-LetterHead 1.5 theme.

Plugins:

  • Akismet ships with wordpress, just have to activate it, and dig up my old API-key. akismet.com now seems a bit more aggressive in wanting money than it did a few years back..
  • Latex for wordpress allows writing mathematical stuff like this:

  • WP-Syntax should make any C/C++ or python code I blog about more readable.
import this # try this in your python shell!
  • Google Analytics allows tracking roughly how many visitors the site has. I have used google-analytics since about 2007, and the graph of visitors looks like this. I should sometime analyse if those traffic-peaks coincide with interesting posts, or being linked to on some popular page.

File+Database restore:

  • I backed up the whole of /public_html from the old site. Have now restored most of the /wp-content directory which holds all pictures and attached files (PDF, movies, etc). This is about 1.5 Gb in total.
  • On the old wodpress-install I exported all posts, pages, and comments into an XML file which is about 7.5 Mb in size. This is now imported into the new site. This is 848 Posts, 8 Pages, 27 Categories, 384 Tags, and 750 Comments.
  • I'm not sure if everything went smoothly. In some cases it appears that images show up correctly in posts, in other cases the images/gallery is missing. This appears to be related to the wordpress Media Library being completely empty on the new site! Even though I uploaded all files to the same directories, and then did the XML-file import it seems that the Media Library is not imported correctly.
  • Update: it appears that the Import function chokes and I get "Internal server error" if the XML file is too large. I have now manually split the XML file into chunks of 1 Mb or less, and now the import function works better. I now have 2113 images and 2 videos in the Media Library. However they are all "Unattached", i.e. it appears wordpress doesn't know what images belong to what posts.

Line-segment voronoi diagram notes

The next step for the opencamlib voronoi-diagram (vd) algorithm is to be able to add line-segment generators. Some notes and ideas on that then (this turned into a rather long post...)

First let's recall (from February) how the point-generator vd-algorithm works:

In (A) we want to insert a new point-generator (yellow). First we need to identify the closest point-generator among the existing generators. (B) Then among the vertices that bound this voronoi-face(region) we search for a seed vertex (pink). The seed vertex is the one that violates the inCircle-predicate the most, i.e. has the minimum distance to the new point-to-be-inserted. (C) Starting from the seed vertex, we then identify other vertices (red) that need to be deleted, because they are closer to the new generator than to any other generator. These vertices are called "IN" vertices, and the associated edges (also in red) should (i) form a tree (a connected acyclic graph) and (ii) for any face, the "IN"-vertices should be connected, and the "OUT" vertices should be connected. (D) IN-IN edges (red) will be deleted completely, while NEW vertices will be generated on each IN-OUT edge (green). (E) NEW-NEW edges are created and connected into a cycle which forms the face/region for the new generator. (F) Now all IN-vertices and all IN-IN as well as IN-NEW edges are deleted and we are done.

Now the case when we insert a line segment. We start as above by constructing the diagram for all point-generators as well as all the endpoints of our line-segments. Here is an image from the Sugihara&Iri 2000 paper (http://dx.doi.org/10.1007/s004530010002) which I have enhanced with colors and text.

The steps of the algorithm are similar to (A)-(F) above: In (A), since we have already inserted the two endpoints of the line-segment, we obviously know in which face to look for the seed-vertex. (B) when we search for a seed-vertex we now need both a dist(VDVertex, PointGenerator) function and a dist(VDVertex, LineGenerator) function. In (C) we again expand the set of "IN" vertices (red circles), while keeping the associated graph a tree, and not disconecting "IN"-vertices or "OUT"-vertices of any face (i and ii above) .

A new (iii) requirement is that the tree should connect the regions of the line-segment endpoints. A new situation also appears where the two endpoints of an edge are classified as "IN", but the complete edge should not be deleted. This is because edges between point and line-segment generators are parabolic arcs (curved!). In this case two NEW vertices are generated on the edge, so it splits into three parts: IN-NEW, NEW-NEW, and NEW-IN. This needs to be dealt with, but I'm not sure exactly how. I think one of the Held papers talks about avoiding this special case by splitting each parabolic edge in two, at the "vertex" of the parabola i.e. the point of greatest curvature (?).

"IN-IN" edges (magenta) will again be deleted. (D) NEW-vertices (green) should now be generated on each IN-OUT edge. This needs new functionality, since we need to deal with two types of edges: LineEdge and ParabolicEdge. The LineEdge occurs between two PointGenerators or between two LineGenerators, while the ParabolicEdge appears between a PointGenerator and a LineGenerator. The NEW vertex we need to generate will obviously be located on the IN-OUT edge (with associated generators gen1, gen2), and should be positioned so that it is equidistant from gen1, gen2, and the new line-segment generator. In contrast to the old point-generator diagram code where we only had one type of VDVertex, namely VDVertex( PointGenerator, PointGenerator, PointGenerator), we now have 6 (six!) different types of vertices in the diagram, depending on the three neighbouring generators, which can be of type LineGenerator, PointGenerator(endpoint), or PointGenerator:

  • VDVertex( PointGenerator, PointGenerator, PointGenerator), type V1 in Okabe et al.
  • VDVertex( PointGenerator, PointGenerator(endpoint) , LineGenerator), type V2
  • VDVertex( LineGenerator, PointGenerator, PointGenerator), type V3
  • VDVertex( LineGenerator, LineGenerator, PointGenerator(endpoint) ),  type V4
  • VDVertex( LineGenerator, LineGenerator, PointGenerator ), type V5
  • VDVertex( LineGenerator, LineGenerator, LineGenerator ), type V6

When these NEW-vertices (green) have been created, the next step is to connect them into a cycle with NEW-NEW edges (green). As we loop around the face we need to create either LineEdges or ParabolicEdges, depending on the neighbouring generators. Okabe lists the four different types of edges that appear in the diagram:

  • VDEdge( PointGenerator, PointGenerator), type E1 (LineEdge)
  • VDEdge( PointGenerator(endpoint), LineGenerator), type E2 (LineEdge)
  • VDEdge( PointGenerator, LineGenerator), type E3 (ParabolicEdge)
  • VDEdge( LineGenerator, LineGenerator), type E4 (LineEdge)

That's about it. It shouldn't be that hard to modify the current code to allow for six types of different VDVertex and four different types of VDEdge, and come up with a suitable design-pattern so that the correct type of vertex and edge are generated based on the type of the generators. Stay tuned...

Update1: here is another image with the same color-coding, from the Held VRONI-paper. The orange edge illustrates a case where the edge is marked "IN-IN" but in fact two new vertices should be generated on it, and the NEW-NEW portion of the edge is retained in the updated diagram (on the right).

Update2: Here is an image from the Held 2009 paper, which describes VDs for line-segment and circular arc generators. The circular arcs add a few additional special cases and some complexity, but the core of the algorithm remains the same: (1) find a seed vertex, (2) expand the set of 'marked' or "IN" vertices maximally, while keeping IN-IN edges (red) a tree, (3) generate NEW vertices (green) on IN-OUT edges (cyan), (4) hook up the NEW vertices with new edges (green) to form the new voronoi region, (5) delete IN-vertices, IN-IN edges, and IN-NEW edges.

Update3: Here's a drawing which shows the six different types of vertices.