How to work with Voronoi tessellations

[robertdj]

Hi,

This looks like just the package I need:
I want to compute a Voronoi tessellation and then the area of each (bounded) cell.

However, playing around with the examples in the README there are some things I don't understand:

• The command tess = DelaunayTessellation() seems to produce the same output if I provide a sizehint input.
• Can I extract individual points from tess?
• After calling voronoiedges, can I extract the corners of a given cell?

Can you help me out?

Thanks,

Robert

[skariel]

hi, sorry for the late reply, for some reason I was not notified when you opened this issue.

About your questions:

• Indeed tess = DelaunayTessellation() will produce the same output regardless of the sizehint input. The sizhint is intended to affect only performance aspects
• You can extract individual points from tess, for e.g by iterating over the triangles or by just keeping a copy of the points that you pushed inside, I'm not completely sure what you mean here...
• By iterating over voronoiedges you get the corners of all cells, but I believe you want to ask how to get all corners of a specific cell. This package gives all the basic functionality needed to do this but currently there is no high level method to do this, so you'd have to do this yourself, it should not be very hard to achieve: just use a point type with an index, and then when you iterate over all voronoi cell edges with voronoiedges put the corresponding corners (point a and b) into some other data structure, something alond these lines:

for edge in voronoiedges(tess)
    a = geta(edge)
    b = getb(edge)
    gen_a = getgena(edge)
    gen_b = getgenb(edge)

    # push corners to cell a
    push!(celledges[gen_a.index], a)
    push!(celledges[gen_a.index], b)

    # push corners to cell b
    push!(celledges[gen_b.index], a)
    push!(celledges[gen_b.index], b)
end

this should be very efficient. Maybe I'll implement something like this next, so lets leave this issue open, and keep me updated if this works for you

[robertdj]

Hi

Thanks for you reply!

Regarding my second question:
If I make a tessellation made by tess = DelaunayTessellation() (and maybe fill it as explained in the README), can I extract element n? If tess was an array I could use tess[n], but this command gives an error.

Regarding the corners, your interpretation of my question is correct :-)
If I understand your code correctly it seems to give the corners, but I cannot execute it:
If I initialize celledges = cell(0) and run the loop I get an error:

ERROR: LoadError: type Point2D has no field index

(A small thing is that getgena and getgenb are currently not exported by the package)

Best,

Robert

[skariel]

You have to use your own Point2D type with an index, something like

immutable IndexablePoint <: AbstractPoint2D
    _x::Float64
    _y::Float64
    index::Int64
end

You have to implement getx, gety, etc. and then extract the corners as above

[robertdj]

Ahh, that makes sense! Thank you!

[robertdj]

Returning to this old issue I have a new question.
I am making code to collect the corners of each Voronoi cell and wonder if I can avoid the corners of the allowed area? I.e., do the corners (1,1), (1,2), (2,1) & (2,2) need their own Voronoi cell?

[skariel]

yes, more or less. You should not draw any line which has a corner as a generator. But then you'll find that a few cells have lines that stop where the corner cell was, whereas now they should actually continue further. This may or may not be a problem, depending what exactly you want to do

Note that I fixed a bug with the generators, please use the latest code in master

if you describe what exactly you want to achieve I may be able to better help :)

Also

[skariel]

for cells that don't share an external point ( ie 1,1 1,2 2,1 or 2,2) you should b getting correct corners

The problem is for the cells that do share one of these special points. In this case just ignoring the special points will lead to incorrect corners.

So a solution could be to use some cells that you don't care about as "padding" for the cells that you care about

of course this should be properly fixed,maybe I'll do it soon. When I have some time that is :)

[robertdj]

In the end I would like to compute the area of each Voronoi cell intersected with the bounding box (allowed area) and the vector of area values should be ordered like the points in tess.

Right now I'm making a Dict where the keys are the generators and the values of a key are the corners of the corresponding cell.
During construction I can check if an edge is related to a special point and make corrections if necessary -- I was just wondering if there was a way to avoid this :-)

[skariel]

are you getting good results with your solution? are you concerned with performance?

[robertdj]

I've only just implemented it and haven't tested performance yet :-)
I am concerned about performance -- which is also why I would like to avoid checking and computing too many things.

[skariel]

ok, please update me about the performance, and correctness, when you have some data -- Thanks!

[robertdj]

Sure!

[robertdj]

I'm running into performance problems: The generators of an edge may not be exactly equal to the original points in a tess, so instead of simply working with Dict[ generator ] I have to search through keys[Dict] for an approximate match...

[skariel]

I don't understand -- if you iterate over the voronoiedges(tess) then the generators that edge.getgena() et al give you are just pointers to the original generators. Also you can put an index inside of them, no dict is needed. Best if you can write here some minimal code that does what you want, I can try to examine and fix it...

[robertdj]

I had not realized that getgena etc gave pointers, but in that case it is weird... I've been writing some code -- let me collect it and upload.

[robertdj]

Sorry about my long absence! I started thinking about indexing generators and forget to reply. Are you thinking about adding and index to AbstractPoint2D?

[skariel]

see comments above -- you can easily add your own index (or whatever other data) into a point by subtyping AbstractPoint2D

to quote myself:

You have to use your own Point2D type with an index, something like

immutable IndexablePoint <: AbstractPoint2D
    _x::Float64
    _y::Float64
    index::Int64
end

You have to implement getx, gety, etc. and then extract the corners as above

[skariel]

it may be worth adding a default indexed poit2d though... I'll open a separate issue on this

[robertdj]

Right!

[robertdj]

I hope I'm not missing something obvious, but I'm having problems with an IndexablePoint:

immutable IndexablePoint <: AbstractPoint2D
    _x::Float64
    _y::Float64
    index::Int64
end

getx(p::IndexablePoint) = p._x
gety(p::IndexablePoint) = p._y
getindex(p::IndexablePoint) = p.index

When I try to push points to a tess with IndexablePoint I get an error:

tess = DelaunayTessellation2D{IndexablePoint}
a = IndexablePoint(min_coord+rand()*width, min_coord+rand()*width, 1)
push!(tess, a)

ERROR: MethodError: `push!` has no method matching push!(::Type{VoronoiDelaunay.DelaunayTessellation2D{IndexablePoint}}, ::IndexablePoint)
Closest candidates are:
push!(::Any, ::Any, ::Any)
push!(::Any, ::Any, ::Any, ::Any...)
push!(::Array{Any,1}, ::ANY)
...

Also, is it not a problem that the four corners doesn't have a default index, cf. #6 ?

[skariel]

it works (and with no warnings) when doing the following:

1. use the latest code do a Pkg.checkout('GeometricalPredictes') and Pkg.checkout('VoronoiDelaunay')
2. explicitly import getx and gety from VoronoiDelaunay to override them
3. IndexablePoint needs a constructor with just the coordinates (x,y)
4. the index used for the outer corners will be the index given in the constructor above (-1 in the example below)

see image below for a working example:

[robertdj]

Now my code runs -- and fast, too :-) What is a good way to share? Should I make a new repository?

[skariel]

what exactly your codes does? this repository is only for the library... is your code relevant for the library? if its just using the library then yeah you should make a new repo. If it adds some functionality that could belong in the library then maybe it can be merged

[robertdj]

Collects corners of each Voronoi cell and at some point I would like it to compute the area of each cell.
I'm not sure it is suited for this library as it falls in the 'application' category.

[robertdj]

BTW: Is it possible to exclude the corner points from the tessellation?

[skariel]

currently there is no good solution, I have to implement point deletion and then just remove those... currently what everybody does is just check in the loop for the corners and just skip them...

[robertdj]

Do you have a reference that describes how to implement point deletion? If so, I'd be happy to look into implementing it.
I've looked briefly into the Springel paper -- are the corner points what he refers to as 'ghost points'?

[skariel]

ghost points are points from different processors, its good for making the algorithm distributed, not exactly what we need right now :)

Regarding removing points, I have no reference, I have to research this a bit, there are algorithms of course its just a matter of finding the literature

[robertdj]

I have found some references on how to remove points, but that is for half point and quad edge data structures...

[robertdj]

FYI, I've collected the code I mentioned above in a package.
I'm thinking of a post-processing hack to remove the corner vertices, but if you find a reference for doing this as part of voronoiedges I'd still be happy to look into it.