linevoronoi-thiessen
I'm looking for a way to create a voronoi diagram based on line segments instead of points. See the example below (taken from this presentation).
Ideally I'd like something I can script from Python, but a solution using ArcGIS or similar would also be acceptable.
The only library to do this I've found so far is openvoronoi, which looks promising. Are there any others?
In QGIS 2.0, your solution no. 1 will work if you combine it with the new layer blending mode feature option "darken". It basically makes the white parts of the line transparent:
The following query appears to do a reasonable set of voronoi polygons starting from the Delaunay Triangles.
I'm not a big Postgres user, so it can probably be improved quite a bit.
WITH
-- Sample set of points to work with
Sample AS (SELECT ST_GeomFromText('MULTIPOINT (12 5, 5 7, 2 5, 19 6, 19 13, 15 18, 10 20, 4 18, 0 13, 0 6, 4 1, 10 0, 15 1, 19 6)') geom),
-- Build edges and circumscribe points to generate a centroid
Edges AS (
SELECT id,
UNNEST(ARRAY['e1','e2','e3']) EdgeName,
UNNEST(ARRAY[
ST_MakeLine(p1,p2) ,
ST_MakeLine(p2,p3) ,
ST_MakeLine(p3,p1)]) Edge,
ST_Centroid(ST_ConvexHull(ST_Union(-- Done this way due to issues I had with LineToCurve
ST_CurveToLine(REPLACE(ST_AsText(ST_LineMerge(ST_Union(ST_MakeLine(p1,p2),ST_MakeLine(p2,p3)))),'LINE','CIRCULAR'),15),
ST_CurveToLine(REPLACE(ST_AsText(ST_LineMerge(ST_Union(ST_MakeLine(p2,p3),ST_MakeLine(p3,p1)))),'LINE','CIRCULAR'),15)
))) ct
FROM (
-- Decompose to points
SELECT id,
ST_PointN(g,1) p1,
ST_PointN(g,2) p2,
ST_PointN(g,3) p3
FROM (
SELECT (gd).Path id, ST_ExteriorRing((gd).Geom) g -- ID andmake triangle a linestring
FROM (SELECT (ST_Dump(ST_DelaunayTriangles(geom))) gd FROM Sample) a -- Get Delaunay Triangles
)b
) c
)
SELECT ST_Polygonize(ST_Node(ST_LineMerge(ST_Union(v, ST_ExteriorRing(ST_ConvexHull(v))))))
FROM (
SELECT -- Create voronoi edges and reduce to a multilinestring
ST_LineMerge(ST_Union(ST_MakeLine(
x.ct,
CASE
WHEN y.id IS NULL THEN
CASE WHEN ST_Within(
x.ct,
(SELECT ST_ConvexHull(geom) FROM sample)) THEN -- Don't draw lines back towards the original set
-- Project line out twice the distance from convex hull
ST_MakePoint(ST_X(x.ct) + ((ST_X(ST_Centroid(x.edge)) - ST_X(x.ct)) * 2),ST_Y(x.ct) + ((ST_Y(ST_Centroid(x.edge)) - ST_Y(x.ct)) * 2))
END
ELSE
y.ct
END
))) v
FROM Edges x
LEFT OUTER JOIN -- Self Join based on edges
Edges y ON x.id <> y.id AND ST_Equals(x.edge,y.edge)
) z;
This produces the following set of polygons for the sample points included in the query 
Create the Delaunay Triangles from the input geometries
SELECT (gd).Path id, ST_ExteriorRing((gd).Geom) g -- ID and make triangle a linestring
FROM (SELECT (ST_Dump(ST_DelaunayTriangles(geom))) gd FROM Sample) a -- Get Delaunay Triangles
Decompose the triangle nodes and make edges can be made. I think there should be a better way to get the edges, but I didn't find one.
SELECT ...
ST_MakeLine(p1,p2) ,
ST_MakeLine(p2,p3) ,
ST_MakeLine(p3,p1)
...
FROM (
-- Decompose to points
SELECT id,
ST_PointN(g,1) p1,
ST_PointN(g,2) p2,
ST_PointN(g,3) p3
FROM (
... Step 1...
)b
) c
Build the circumscribed circles for each triangle and find the centroid
SELECT ... Step 2 ...
ST_Centroid(ST_ConvexHull(ST_Union(-- Done this way due to issues I had with LineToCurve
ST_CurveToLine(REPLACE(ST_AsText(ST_LineMerge(ST_Union(ST_MakeLine(p1,p2),ST_MakeLine(p2,p3)))),'LINE','CIRCULAR'),15),
ST_CurveToLine(REPLACE(ST_AsText(ST_LineMerge(ST_Union(ST_MakeLine(p2,p3),ST_MakeLine(p3,p1)))),'LINE','CIRCULAR'),15)
))) ct
FROM (
-- Decompose to points
SELECT id,
ST_PointN(g,1) p1,
ST_PointN(g,2) p2,
ST_PointN(g,3) p3
FROM (
... Step 1...
)b
) c
The Edges CTE outputs each edge and the id(path) of the triangle it belongs to.
'Outer Join' the 'Edges' table to itself where there are equal edges for different triangles (interior edges).
SELECT
...
ST_MakeLine(
x.ct, -- Circumscribed Circle centroid
CASE
WHEN y.id IS NULL THEN
CASE WHEN ST_Within( -- Don't draw lines back towards the original set
x.ct,
(SELECT ST_ConvexHull(geom) FROM sample)) THEN
-- Project line out twice the distance from convex hull
ST_MakePoint(
ST_X(x.ct) + ((ST_X(ST_Centroid(x.edge)) - ST_X(x.ct)) * 2),
T_Y(x.ct) + ((ST_Y(ST_Centroid(x.edge)) - ST_Y(x.ct)) * 2)
)
END
ELSE
y.ct -- Centroid of triangle with common edge
END
))) v
FROM Edges x
LEFT OUTER JOIN -- Self Join based on edges
Edges y ON x.id <> y.id AND ST_Equals(x.edge,y.edge)
Where there is a common edge draw a line between the respective centroids
Where the edge is not joined (exterior) draw a line from the centroid through the centre of the edge. Only do this if the centroid of the circle is inside the set of triangles.
Get the convex hull for the drawn lines as a line. Union up and merge all the lines. Node the line set so that we have a topological set that can be polygonized.
SELECT ST_Polygonize(ST_Node(ST_LineMerge(ST_Union(v, ST_ExteriorRing(ST_ConvexHull(v))))))
Best Answer
We (a university team) designed an implementation for this using an ArcGIS 10.0 addin and ArcObjects. The application is completely free. The implementation uses a raster methodology that takes as input points, lines or polygons to create ordinary or multiplicatevly weighted Voronoi diagrams (or a combination of the above, i.e. you can use one of each type of shape, creating a single diagram set from up to three distinct feature classes). It's still in development but should be fairly stable, especially if you only want to do lines. The addin requires the Spatial Analyst license to operate. The code itself is open source, so feel free to do with it as you please.
https://github.com/UNTGeography/VoronoiDiagramsGIS
It uses a similar method as the "Euclidean Allocation" described in @radouxju's answer and uses Flow Direction/Basin raster to create vector polygons from the resultant raster.