[R-sig-Geo] Creating a tesselation of polygons around a set of lines

[Alan Chalk]

Dear List,

I have a set of lines that are within a given area.  I would like to 
create a set of polygons that tesselate the same area and which fulfil 
the condition that each polygon contains exactly one line (that is, the 
line is within the polygon and does not form one of its edges).

As an example, imagine we have the following three lines:

    require(sp)
# create 3 Lines objects
    Lines1.l <- Lines(ID=1, list(Line(matrix(c(0,0,1,1), ncol=2, 
byrow=TRUE))))
    Lines2.l <- Lines(ID=2, list(Line(matrix(c(1,1,2,3), ncol=2, 
byrow=TRUE))))
    Lines3.l <- Lines(ID=3, list(Line(matrix(c(4,4,5,5), ncol=2, 
byrow=TRUE))))

# Create and plot SpatialLines object
    exampleSpatialLines.sl <- SpatialLines(list(Lines1.l, Lines2.l, 
Lines3.l))
    plot(exampleSpatialLines.sl)

Then, one solution to the problem would be as shown below.

# Plot an example solution to my problem
    examplePolygons1.p <- Polygons(ID=1, 
list(Polygon(matrix(c(0,0,0,1,1,1,1,0,0,0), ncol=2, byrow=TRUE))))
    examplePolygons2.p <- Polygons(ID=2, 
list(Polygon(matrix(c(0,1,0,5,2,5,5,0,1,0,1,1,0,1 ),
                                                             ncol=2, 
byrow=TRUE))))
    examplePolygons3.p <- Polygons(ID=3, 
list(Polygon(matrix(c(5,0,2,5,5,5,5,0), ncol=2, byrow=TRUE))))

    exampleSpatialPolygons.sp <- SpatialPolygons(list(examplePolygons1.p,
                     examplePolygons2.p,
                     examplePolygons3.p
                       )
                 )
    plot(exampleSpatialPolygons.sp[1], border="red", col="NA", add=TRUE, 
lwd=4)
    plot(exampleSpatialPolygons.sp[2], border="green", col="NA", 
add=TRUE, lwd=2.5)
    plot(exampleSpatialPolygons.sp[3], border="blue", col="NA", 
add=TRUE, lwd=0.1)

Clearly there are many solutions to this problem - however any solution 
(where the lines are within the polygons and not one of the edges) will 
suffice.

I would be grateful if anyone could supply an automated solution to this 
problem.

Many thanks

Alan Chalk