Java library for (outermost point) Voronoi diagram

I have googled for hours, but I cannot find a Java library for calculating Voronoi (Farthest Point) charts.

There are a couple of applets that happily draw Voronoi diagram, but I haven't seen anyone with the source code.

The question I am trying to answer is "what are the defining points for this Voronoi peak", "which point is closest to this Voronoi peak", and "which point is farthest from this Voronoi peak",

I'll also agree with the pointer for a good explanation of how to write your own Furthest Point algorithm. Please note that I am not very interested in efficiency, I am just trying to prove that using these two Voronoi diagrams can solve my problem.

Please note that I need both FPVD and VD :)

azraelAT helped me find a library for normal Voronoi diagrams, but I still haven't found a library that could compute Faron Point Voronoi diagrams!

+3


source to share


3 answers


You might want to check out the Tektosyne library .



It can generate Voronoi and Delaunay triangulation diagrams with conversion to DCEL subdivisions and supports graph algorithms such as A * pathfinding, path coverage, fill fill, sigh line.

+1


source


There are so many free libraries out there that create Voronoi diagrams from different types of input.



Check simplevoronoi for example: http://sourceforge.net/projects/simplevoronoi/

0


source


For a pointer to an algorithm, you can see:

SKYUM, Sven. A simple algorithm for calculating the smallest circumferential circle . Information Processing Letters, 1991, 37.3: 121-125.

Abstract statements

... calculation algorithm ... long-range Voronoi diagram of a set of points

but the explanation (in section 3) indicates convex . I don't know the relationship between FPVD of a set of points S and FPVD like convex hull S.

EDIT:

Shamos in his Ph.D. dissertation work (p.201):

By Theorem 6.31, this [FPVD] diagram is defined only by points on the convex hull, and they are all open, so there are no bounded regions.

Michael Ian Shamos. 1978. Computational Geometry . PhD. Thesis. Yale University, New Haven, Connecticut, USA. AAI7819047.

I read that you are looking for a Java solution, but here you can find a C solution explained in qvoronoi Qu - far Voronoi diagram site

0


source







All Articles