voronoi / thiessen polygons

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

voronoi / thiessen polygons

Stefan Steiniger
Hei Martin,

 > It's almost done, actually - so if you have a definite use case for
 > it, that would be great.

yep we have. I used it in my research (pattern recognition) but Nacho
Uve was using it too for some hydrological calculations if I remember
correctly, Ravi (for Geologist GIS training) and I think Hisaiji are
using it as well (he just asked recently). I got several times responses
by people that at least tested it.

 > Do you have examples of input data that caused problems with the
 > existing code?  It would be nice to be able to test my code against
 > them.

As far as I recognized the reason for this problem are collinear points
- i.e. points on a regular grid. I send an example where it doesn't work
with the implementation I used offlist to you.

 > Also, how does the current OJ code "close off" or bound the
 > constructed
 > Voronoi diagram?  Do you give it a bounding box, or is there some
 > other way?

Actually the approach the triangulation used was a bit different from
what you probably did. Because it starts with an initial triangle and
uses and point-insert approach (a Simplex Insert algorithm developerd
and implemented by L Paul Chew). So I basically deliver the bounds for
the initial triangle.
At the end I just cut out the part I need as this initial triangle is
pretty large. Not sure if this info helps but you can see my access code
in the package:

        org.openjump.core.graph.delauneySimplexInsert

that is DTriangulationForJTS here:
http://jump-pilot.svn.sourceforge.net/viewvc/jump-pilot/core/trunk/src/org/openjump/core/graph/delauneySimplexInsert/DTriangulationForJTS.java?view=markup

check out the access methods:
* DTriangulationForJTS(ArrayList pointList)
* DTriangulationForJTS(ArrayList pointList, Envelope envelope)
* drawAllVoronoi ()
* getThiessenPolys()

The Access function in OpenJUMP is to be found in
Menu>Tools>Generate>Create Thiessen Polygons
or org.openjump.core.ui.plugin.tools.CreateThiessenPolygonsPlugIn()

stefan
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: voronoi / thiessen polygons

Martin Davis


Stefan Steiniger wrote:

> Hei Martin,
>
> > It's almost done, actually - so if you have a definite use case for
> > it, that would be great.
>
> yep we have. I used it in my research (pattern recognition) but Nacho
> Uve was using it too for some hydrological calculations if I remember
> correctly, Ravi (for Geologist GIS training) and I think Hisaiji are
> using it as well (he just asked recently). I got several times
> responses by people that at least tested it.
Great, those all sound like good use cases.
>
> > Do you have examples of input data that caused problems with the
> > existing code?  It would be nice to be able to test my code against
> > them.
>
> As far as I recognized the reason for this problem are collinear
> points - i.e. points on a regular grid. I send an example where it
> doesn't work with the implementation I used offlist to you.
This doesn't seem to be a problem for the JTS code - it runs your
datasets fine.  I agree that collinear points are a known issue for some
Delaunay implementations.  Probably the use of an incremental algorithm
helps here.

>
> > Also, how does the current OJ code "close off" or bound the
> > constructed
> > Voronoi diagram?  Do you give it a bounding box, or is there some
> > other way?
>
> Actually the approach the triangulation used was a bit different from
> what you probably did. Because it starts with an initial triangle and
> uses and point-insert approach (a Simplex Insert algorithm developerd
> and implemented by L Paul Chew). So I basically deliver the bounds for
> the initial triangle.
Ok, so nothing out of the ordinary then.  The JTS code requires an
envelope of the input points, and builds the frame triangle
automatically.  It's easy to clip the Voronoi polygons as required when
they are generated.  There is a VoronoiDiagramBuilder that provides a
simple interface for doing this, or it's easy to deal with the raw
outputs as well.
>
> stefan
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Loading...