Month: April 2012

UV LED Lamp


We use Norland Optical Adhesive (NOA-81) for gluing bits and pieces together in the lab. The glue cures in UV-light. So far we've used a fluorescent solarium lamp for this, but we broke one of the two remaining lamps and can't seem to source new ones.


So I decided to try an LED solution. These are LEDEngin LZ1-10U600 LEDs with a center wavelength of 365 nm, 28 euros each from Mouser. They are glued to an aluminium plate using a heat-conducting glue, Loctite Output 384:

For simplicity I used a LighTech 18 W 700 mA constant-current powersupply that runs directly off AC mains. The powersupply has a maximum output voltage of 24 V which is enough to drive the five UV-LEDs in series (the UV-LED has a voltage-drop of 4.1 V)

Here's how the lamp looks like:

Most of the blue in this picture is fluorescence from the white paper underneath the lamp. A quick test shows that the NOA-81 glue cures very quickly indeed (seconds) with this lamp. Much faster than with the old fluorescent lamp (minutes) anyway. This kind of lamp may be useful for PCB-making also? I didn't keep the lamp on for very long yet, so I don't know how adequate the alu-plate is as a heat-sink.

Warning: The UV-light from these LEDs may be more or less harmful for your eyes and/or skin. Don't try this at home unless you know what you are doing!

Söderkulla Seventy

70.33 km in 3h 21min, avg. 21.0 km/h

Sunday 59k

I put on new 32mm wide tires on the road-bike and took it out for a spin. Sunny but windy weather with what seemed to be a headwind in every direction...

59.2km in 3h 21min (avg 17.6km/h)
(You have to zoom in or out to see the GPX-track. I'm not sure why that is happening)

Aluerastit, Kumpula

First orienteering event of the year. 5 km course.

Critical Bikeride, April 2012

Hey I'm trying the OpenStreetMap plugin for wordpress. It should allow showing maps, places, and GPX-tracks in the blog.

They did have a critical bikeride in March already this year, but it was quite snowy and rainy so I didn't participate.

Today there were 130-140 participants.

Last year I think I participated in these events to raise awareness for bicycling four times: June, August, September, and October.

Random points VD benchmark

Here's some benchmark data for constructing the Voronoi diagram (or its dual, the Delaunay triangulation) for random point sites. Code for this benchmark is over here: https://github.com/aewallin/voronoi-benchmark

OpenVoronoi is my own effort using the incremental topology-oriented algorithm of Sugihara&Iri and Held. Floating-point coordinates with all sites falling within the unit-circle are used. Fast double-precision arithmetic is used for geometric predicates (e.g. "in-circle") during the incremental construction of the diagram, since the topology-oriented approach ensures that the algorithm finishes and produces an output graph regardless of errors in the geometric predicates. Quad-precision arithmetic is used for positioning vd-vertices. This benchmark runs in ca 7us*N*log2(N) time.

Boost.Polygon uses Fortune's sweepline algorithm. Only integer input coordinates are allowed, which ensures that geometric predicates can be computed exactly. Lazy arithmetic, where a high-precision slower number-type is used only when required, is used. This benchmark runs in ca 0.2us*N*log2(N) time.

CGAL uses exact geometric computation, which is slow but supposedly robust. The run-time gets worse with increasing problem-size and doesn't seem to fall on an O(N*log(N)) line.

Some thoughts:

  • OpenVoronoi is obviously too slow! Lazy arithmetic or other methods are required so that most vd-vertices can be positioned with fast double-precision code, and the quad-precision methods need to be called only rarely. OpenVoronoi uses a BGL adjacency_list to store the graph - this may also be too slow compared to a C-style "raw" data structure.
  • Other libraries which might be added to the benchmark: Triangle and QHull.
  • Held has, IIRC, reported around 0.5us*N*log2(N) for his closed-source VRONI algorithm. From the interwebs we also find this quote: "If your use is commercial, VRONI's license is a few thousand dollars."
  • It's easy to measure run-time, but how do we measure the correctness of the output that these algorithms produce? A first simple approach is write the output to a PNG or SVG file and visually inspect it, but something more precise and automated would be nice.
  • Neither Boost.Polygon nor OpenVoronoi support circular arc sites yet. Both can in principle be extended to do so.
  • Are we comparing apples to oranges? Is the output of these algorithms the same? OpenVoronoi produces a half-edge data structure of the diagram with edge-parametrizations (lines, parabolas) that allow computing a point on an edge at a given offset-distance from an adjacent site. The data structure allows for iterating through the edges, vertices, and faces of the graph.

 

Arc predicates

I started working on arc-sites for OpenVoronoi. The first things required are an in_region(p) predicate and an apex_point(p) function. It is best to rapidly try out and visualize things in python/VTK first, before committing to slower coding and design in c++.

in_region(p) returns true if point p is inside the cone-of-influence of the arc site. Here the arc is defined by its start-point p1, end-point p2, center c, and a direction flag cw for indicating cw or ccw direction. This code will only work for arcs smaller than 180 degrees.

def arc_in_region(p1,p2,c,cw,p):
    if cw:
        return p.is_right(c,p1) and (not p.is_right(c,p2))
    else:
        return (not p.is_right(c,p1)) and p.is_right(c,p2)


Here randomly chosen points are shown green if they are in-region and pink if they are not.

apex_point(p) returns the closest point to p on the arc. When p is not in the cone-of-influence either the start- or end-point of the arc is returned. This is useful in OpenVoronoi for calculating the minimum distance from p to any point on the arc-site, since this is given by (p-apex_point(p)).norm().

def closer_endpoint(p1,p2,p):
    if (p1-p).norm() < (p2-p).norm():
        return p1
    else:
        return p2
 
def projection_point(p1,p2,c1,cw,p):
    if p==c1:
        return p1
    else:
        n = (p-c1)
        n.normalize()
        return c1 + (p1-c1).norm()*n
 
def apex_point(p1,p2,c1,cw,p):
    if arc_in_region(p1,p2,c1,cw,p):
        return projection_point(p1,p2,c1,cw,p)
    else:
        return closer_endpoint(p1,p2,p)


Here a line from a randomly chosen point p to its apex_point(p) has been drawn. Either the start- or end-point of the arc is the closest point to out-of-region points (pink), while a radially projected point on the arc-site is closest to in-region points (green).

The next thing required are working edge-parametrizations for the new type of voronoi-edges that will occur when we have arc-sites (arc/point, arc/line, and arc/arc).