Voronoi Diagram for line segments / polygons

[Marcel Gangwisch]

Hi All!

I want to calculate a Voronoi Diagram based on line segments or complete polygons and points.
Currently it works with an implementation of fortunes algorithm and sampled line segments. It works, but its slow and sometimes not correct if two different line segments have a smaller distance than the sample rate used before.

So I want to ask if I can somehow calculate such a voronoi diagram based on the functions of spatialite.

I read this page here: https://www.gaia-gis.it/fossil/libspatialite/wiki?name=tesselations-4.0
There it says that the "input Geometry can be of absolutely arbitrary type; all Linestrings and / or Polygons will eventually be dissolved into Points corresponding to vertices. So after all ST_VoronojDiagram() (exactly as ST_DelaunayTriangulation) will always process a MultiPoint."

So even if I use ST_VoronojDiagram(geometry) on polygons I only get an approximation of what I want.

I also thought about using another library like cgal (https://www.cgal.org/) to compute the diagram.
But since I have to use C# and there are no wrappers or bindings of cgal for C#, this is also not possible!

Maybe you have another Idea on how to calculate such voronoi diagrams with C#

Thank you for your help!
Best regards,
Marcel

[a.fu...@lqt.it]

On Tue, 10 Feb 2015 04:34:01 -0800 (PST), Marcel Gangwisch wrote:
> Hi All!
>
> I want to calculate a Voronoi Diagram based on line segments or
> complete polygons and points.
>

Hi Marcel,

a Voronoi Diagram is always expected to be based on a collection
of *POINTS*

accordingly to Wikipedia [1]:
"In mathematics, a Voronoi diagram is a partitioning of a plane into
regions based on distance to points in a specific subset of the plane.
That set of points (called seeds, sites, or generators) is specified
beforehand, and for each seed there is a corresponding region
consisting
of all points closer to that seed than to any other. These regions are
called Voronoi cells. The Voronoi diagram of a set of points is dual
to its Delaunay triangulation."

as you can easily check, pretending to pass line segments or polygons
as Voronoi "seeds" seems to be a mathematical nonsense.

[1] http://en.wikipedia.org/wiki/Voronoi_diagram

> I read this page here:
>
> https://www.gaia-gis.it/fossil/libspatialite/wiki?name=tesselations-4.0

> [1]

> There it says that the "input Geometry can be of absolutely arbitrary
> type; all Linestrings and / or Polygons will eventually be dissolved
> into Points corresponding to vertices. So after all
> ST_VoronojDiagram() (exactly as ST_DelaunayTriangulation) will always
> process a MultiPoint."
>
> So even if I use ST_VoronojDiagram(geometry) on polygons I only get
> an
> approximation of what I want.
>

sorry, I disagree: extracting all individual vertices from input
Linestrings / Polygons isn't at all "an approximation"; it's the unique
possible way to create a mathematically acceptable set of Points (aka
seeds) required by Voronoi as its input set.

> Currently it works with an implementation of fortunes algorithm and
> sampled line segments.
>

sorry again, this is incorrect; it currently works on *points* (forget
at all "line segments", it's a misconception) because this is a strict
Delaunay/Voronoi mathematical requirement.
the underlaying algorithm adopted by SpatiaLite is entirely based on
the GEOS implementation of Delaunay Triangulation.
GEOS does not directly supports the Voronoi Diagram; anyway Voronoi
simply is the dual graph of Delaunay, so SpatiaLite will simply apply
the reverse operations required to derive a Voronoi set out from a
Delaunay set. no more and no less than this.

> It works, but its slow
>

surely yes: computing a GEOS Delaunay set is an intrinsically slow
operation; then reversing the Delaunay set so to get the Voronoi set
is another complex (thus slow) operation.
the overall time is never expected to be a very brilliant one, and
will certainly dramatically increase when an huge number of points
(aka seeds) are passed as the input set.

> and sometimes not correct if two different line segments have a
> smaller distance than the sample rate used before.
>

the ST_VoronojDiagram() SQL function accepts a "tolerance" optional
argument; do you have tested if different tolerance values can
eventually help to get better (more accurate) results ?

OTH,
Sandro

[Roberto Angeletti]

Hi Marcel,

perhaps, you are trying to calculate a skeleton line of polygons ?

In the case, I just create an algorithm that does this.

Tell me

Regards

Roberto

--
You received this message because you are subscribed to the Google Groups "SpatiaLite Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to spatialite-use...@googlegroups.com.
To post to this group, send email to spatiali...@googlegroups.com.
Visit this group at http://groups.google.com/group/spatialite-users.
For more options, visit https://groups.google.com/d/optout.

[Marcel Gangwisch]

Hi Sandro,

thank you for your reply!

a Voronoi Diagram is always expected to be based on a collection
of *POINTS*

accordingly to Wikipedia [1]:
"In mathematics, a Voronoi diagram is a partitioning of a plane into
  regions based on distance to points in a specific subset of the plane.
  That set of points (called seeds, sites, or generators) is specified
  beforehand, and for each seed there is a corresponding region
consisting
  of all points closer to that seed than to any other. These regions are
  called Voronoi cells. The Voronoi diagram of a set of points is dual
  to its Delaunay triangulation."

as you can easily check, pretending to pass line segments or polygons
as Voronoi "seeds" seems to be a mathematical nonsense.

[1] http://en.wikipedia.org/wiki/Voronoi_diagram

Actually I know the usual way of defining a voronoi diagram! I know its the only way of defining the voronoi diagram as the dual graph of a delaunay as you think.

But in terms of polygons it makes no sense.
You can think about a partitioning of a plane into regions based on distance to polygons in a specific subset of the plane.

And therefore I also want to cite some pdfs:
[1] http://www.cise.ufl.edu/~sitharam/COURSES/CG/kreveldmorevoronoi.pdf (starting at slide 83)
[2] http://www.cs.uu.nl/docs/vakken/ga/slides7b.pdf (starting at slide 6)
[3] http://www.tcs.tifr.res.in/~ghosh/subhas-lecture.pdf (slide 59)

Maybe you see, that the calculation of a voronoi diagram based on line segments is also a mathematical problem to think about!
 

> I read this page here:
>
> https://www.gaia-gis.it/fossil/libspatialite/wiki?name=tesselations-4.0
> [1]
> There it says that the "input Geometry can be of absolutely arbitrary
> type; all Linestrings and / or Polygons will eventually be dissolved
> into Points corresponding to vertices. So after all
> ST_VoronojDiagram() (exactly as ST_DelaunayTriangulation) will always
> process a MultiPoint."
>
> So even if I use ST_VoronojDiagram(geometry) on polygons I only get
> an
> approximation of what I want.
>

sorry, I disagree: extracting all individual vertices from input
Linestrings / Polygons isn't at all "an approximation"; it's the unique
possible way to create a mathematically acceptable set of Points (aka
seeds) required by Voronoi as its input set.

and sorry, I also disagree: if you consider only the points which form the polygon, you get only an "approximation" (in the sense of the other definition of a voronoi diagram).
Because mathematical its not enough to only consider the end points of a line (which is part of a linestring forming the polyong). A line can be given by infinitely many points given by the function of the line.
So in the sense of the old definition of the voronoi diagram you must calculate the diagram based on these infinitely many points.. (which is not possible...) otherwise its an "approximation".

 

> Currently it works with an implementation of fortunes algorithm and
> sampled line segments.
>

sorry again, this is incorrect; it currently works on *points* (forget
at all "line segments", it's a misconception) because this is a strict
Delaunay/Voronoi mathematical requirement.
the underlaying algorithm adopted by SpatiaLite is entirely based on
the GEOS implementation of Delaunay Triangulation.
GEOS does not directly supports the Voronoi Diagram; anyway Voronoi
simply is the dual graph of Delaunay, so SpatiaLite will simply apply
the reverse operations required to derive a Voronoi set out from a
Delaunay set. no more and no less than this.

"Currently it works with an implementation of fortunes algorithm and sampled line segments." - I dont want to make any statement about Spatialite and GEOS Voronoi Diagram.
I just wanted to state, how I solved the problem in an unsatisfactory way. And I don't want to forget the line segments because its necessary for my research.
 

> It works, but its slow
>

surely yes: computing a GEOS Delaunay set is an intrinsically slow
operation; then reversing the Delaunay set so to get the Voronoi set
is another complex (thus slow) operation.
the overall time is never expected to be a very brilliant one, and
will certainly dramatically increase when an huge number of points
(aka seeds) are passed as the input set.

With the calculation of the voronoi diagram by fortunes algorithm you are actually fast (O(nlogn)) - the fastest you can get!
The problem is the sampling of the line because you create really a lot of points!

But considering the pdfs I cited before, there are existing algorithms, computing the voronoi diagram based on line segments also in O(n log n) :-) (And this would be actually fast!)

Have a nice evening!
- Marcel