Add your own alternative version
Stats
243.6K views 2.6K downloads 49 bookmarked
Posted
10 Aug 2005

Comments and Discussions



That is always an issue with your double precision  try normalizing the space of your data points to +/1 and adjusting the epsilon value.





I am really sorry to disturb you but where do this adjustments ?





The provided code is absolutely shitted.
Why if I change epsilon value it will stop working correctly???????????
What epsilon value should be used??? Why 1e10???? Why not 1e20????
Did you try it for big numbers, for example: 220034495, 883612293??????
It's really piece of S H I T and I've wasted so huge amount of time on this crap...





Change work !
Programming is not for you.
All the problem with Fortune Algo is there, and after hour of search the info is there !!!





Civil Engineers typically add boundaries, cut holes, and have lines that are not allowed to be crossed by triangles (called breaklines).
Would this code take a lot of changing to introduce these abilities?





Isn't this beyond the scope of the voronoi algorithm?
In a situation like this, unless I misunderstand, perhaps you want to postprocess the voronoi output with some other polygon clipping code; I recommend clipper.
I realise the original message was posted months ago, so this response may not serve much purpose.





Nice, clean impementation





You are really stupid clown!!!!!!
Where do you see CLEAN implementation??????





I found it easy to understand, it solved my problem, so I voted it up.
If that doesn't suit you, I really couldn't care less.
P.S. You might find that a more conciliatory tone and writing correct English will improve your experience here.





Let me note: the world around would be much better if you had executed yourself.





This forum is for discussing programming problems.
If, as it appears, you're just trolling, there are plenty of other forums where people will be delighted to have a flame war with you.
Be so good as to go elsewhere.





i want to use this algorithm, input some point data and get the coordnates of the voronoi polygons of those point data. i tried to understand how this is implemented but it is hard for me. i can input the point data but i can't find from which method i can get the coordinates of the polygons. can you help by telling how i can get the polygon coordinates (from which method?)
dk





Hi,
I'm looking for a fast way to determine the location of a specified point (x,y) within your VoronoiGraph in C#.
Your VoronoiGraph only returns a list of edges and vertices of the graph. Are they in any specific order?
It would be great if there was an easy way to create a structure for a single Voronoi cell and a list of its neighbor cells.
Is there a fast way to determine in which cell my specified point is? (In literature a logarithmic runtime is said)
Thanks for your help in advance!





In the special case of 3 data points, all FixedPoints are equal to the unique Vertize, isn't wrong??
i made a test with: (0,0);(10,0);(0,10).
and for each edge the fixedPoint is equal to (5,5).
I hope your answer BenDi... Excellent tool!!
cheers





That's the proper result: for any three sites  except when they are perfectly aligned (in any direction), there will be only one vertex, shared by the three edges.





somebody have a free C# code, to generate the Polygon for each data point using a boundary polygon that could be the convex hull(or extended convex hull) of the data points.
thks.





Ben,
For following another set of points, algorithum misses the vertex by almost 250 mt.
NODE_ID EASTING NORTHING
6 10494.00016 10092.53629
7 10290.7531 10684.97519
8 9947.773702 11043.95948
9 9776.284008 11059.26798
10 10991.95541 10217.30055
11 10057.01902 10092.5363
It gives 8 edges and 3 vertex, but due to wrong location of vertex 3, egde no 6,7 and 8 have not come out properly. Actual location of vertex 3 should be 9819.40,10578.40. I strongly feel that it should have 4 vertexes.
Could you please look into it.
Thanks,
Sunil Terkar





Hi,
sorry to hear about that, the only problem I can image is double rounding...
I think what you need is a version of the algorithm based on the decimal class, not on double  should be done by replacing all occurences of 'double' with 'decimal'  please try it.
cheers,
Ben





Ben
Ok, will give try for this & get back to you. I have one more observation wrt last message, even program doesn't sorts correctly all site nodes on y coordiantes...does it could be the another reason for not producing correct vertex..
Regards,
Sunil Terkar





Ben,
Tried decimal type also, still its reporting 3 vertex at wrong coordinates. Even this circle at this vertex is not an empty circle.
Please look into this problem.
Thanks,
Sunil Terkar





I tried the numbers above, and with BenDi's version, I got 5 vertices:
y:10277.582825767151, x:10313.499324681763
y:10489.718951040446, x:9870.995694254938
y:10497.621153995677, x:10719.098572868817
y:10504.131065614873, x:9950.369665759434
y:13717.0357506786, x:12076.964532715061
(not 3 as you report, and neither 4 as you anticipate.)





Ben,
I have passed on following points to this algorithum,seems its generating atleast one less vertex and one less edge. I have compared voronoi diagram generated by these points wih standard GIS software like MapInfo, is it the thing that you need to address ?
1 399380.8371 5526801.89
2 400882.095 5525038.395
3 402256.1277 5524122.657
4 399247.2089 5525471.661
5 401383.9145 5523790.174
Regards,
Sunil Terkar





I tried it, and BenDI's version correctly reports 4 vertices:
y:5530625.902209154, x:405647.4244046288
y:5526166.085865074, x:400398.8301785578
y:5524717.980236851, x:401702.70591802325
y:5523959.683474038, x:399813.0172873341
Are you saying your GIS software is reporting 5 vertices?





Hello: I'm working on a project that involves finding the medial axis of
vector polygons and was hoping from all that I've read that using the voronoi would allow me to do this.
has anyone has experience w/ working w/ this project and finding the medial axis?
thanks,
Proctor





Thank you very much for posting this! It's a great starting point for developing my own Voronoi solver.





How does the code return the rays (ie sides with only one vertex and a direction). From what I can tell VVertexB is just set to NaN. But how does one generate the rays from this information?






Hi!
For (partly) infinite edges I provided two properties do make drawing easier: FixedPoint and DirectionVector. FixedPoint is either the (one) Vertex that exists or the middle between the two data points. DirectionVector is orthogonal to the connecting line between the data points (this is a property of all voronoi edges).
The secret to getting the direction of an infinite edge is in the voronoi algorithm itself  it provides edges with 'left' and 'right' data points. This gives a direct way to calculating the direction from the vertex. It goes in the direction where LeftData is left and RightData is right. Simple
Cheers,
Ben





Do you mean that the Voronoi edge ray must start at VVertexA and must have the direction of the line made by the points LeftData and RightData (i.e. from LeftData to RightData comes first). If yes, then your algorithm is wrong. Just test it on a rectangle and you will see the result. If I misunderstood you, please explain how to get the rays in more details.
VladovsoftSoftware products for fitness and health club management, storehouses, shops and barcode generation.





They start in VVertexA and go orthogonal to the line from LeftData to RightData, so that LeftData is on the left and RightData is on the right.





Ok, thanks. But what about the vertices. I made a simple polygon generator to test the algorithm and I saw that the location of the vertex for 3 points (i.e. a triangle) is sometimes out of the triangle. But it should be the center of the inscribed circle, shouldn't it ?
VladovsoftSoftware products for fitness and health club management, storehouses, shops and barcode generation.





No, Voronoi Vertex of a triangle is the center of it's outer circle, which is only inside the triangle for max(angle)<90 degree. (see wiki[^])
B.





Ok, thanks for the info. I was planning to use Voronoi diagrams for finding the Maximum Inscribed Circle in a simple polygon, but I guess I should read some more information about its properties to determine if it will work for me.
VladovsoftSoftware products for fitness and health club management, storehouses, shops and barcode generation.





According to this, if I take RightDataLeftData, I get the vector from left to right. Then swapping X and Y and negating one gets an orthogonal vector. Taking the nonunknown point and adding the orthogonal vector should produce the correct ray, with LeftData on the left and RightData on the right. However in some cases it does not, and the ray is cast in the wrong direction, as if LeftData and RightData are in the wrong order.
Do you have a correction for me, or updated version of this code?





Hi,
sorry, I dont have any free time at the moment... can you verify whether the left/right data points are actually wrong?
B.





I solved this the same way many other implementations do  don't try to draw the unbounded edges, just contain the points you want to draw within a much larger triangle or square.
With this, I don't have any issues.





Hello BenDi,
I tried to fix the ray problem many people seem to have. I verified the left/right data points and they really seem to be wrong. If I draw a green/blue line from RightData to LeftData (where the left part of the line is green and the right part is blue) you can see in the picture below, that the right/left side is sometimes wrong.
https://www.dropbox.com/s/1o4zl2izmkuv96d/voronoi_ray_problem.png[^]
Do you have any idea where I could fix that problem? How do you decide which one is the left and which one the right point?
It would be kind if you could help me with this problem, or at least give me a hint. Drawing the rays correctly is really necessary for me and I can't skip them.
Peh





Hi! As you can see from the image, the left data point (as seen from the center of the VoronoiEdge) is the one with the lower X coordinate.
Can you make the ray problem more precise? Then maybe I can help more.
Cheers,
B.





Hi,
thanks for your interest in my problem. I understand what you say and you are right for the image I posted. I made a more precise one now.
P are points
M are mids between two points
blue lines point to right data
green lines point to left data
V is the voronoi point (VVertexA)
Rays are drawn by hand so far. Starting at V.
https://www.dropbox.com/s/fqxkg9im5e5bnmk/voronoi_ray_problem2.png[^]
My Problem is how to get the correct direction of the ray vector.





Ah, I remember.
The right solution was posted a long time by ckaut:
On an unbounded edge, only one point, let's call is 'center', is set. Comput a vector
diff = (left_data+right_data)/2  center
and paint a line from center to center + N * diff (where N is large enough to go out of your viewing area.
For this it does not matter if left and right are correctly assigned.
BTW: I haven't looked at the code in a while, but it seems like I added
VoronoiEdge.FixedPoint (=center) and VoronoiEdge.DirectionVector (=diff, normalized)
for exactly this purpose Sorry for not documenting it better.





Yes this looks like a very easy solution and this was what I already tried.
But it's only the solution for the half of this problem.
If the center (V) is within the triangle of the three Points (P) then this way is right (correct for this problem[^]).
But if the center (V) is outside the triangle then it fails too (still fails in this problem[^]). Ray13 should be the other direction here.





Uh, that's true. Appearantly I did not see this case during debugging.
This will probably need a bit more smarts in the Algorithm itself to correctly assign left and right data points, but I might not have time for that in the near future.
Feel free to give it a shot: in FortuneVoronoi.cs, ProcessDataEvent, left/right data is assigned, but after that there are some special cases for how to insert the new tree nodes. My guess is that left/right data points should be assigned based on the same if/else distinguation. Give it a try!





This was a nasty trap ;(
I saw this example (Visualization of the 2D Voronoi Diagram and the Delaunay Triangulation[^]) of an implementation of your algorithm. I downloaded both (yours and the example) and picked the wrong one. What I didn't see is that this example is using an old and buggy version of your code.
With the code from this article here I finally got the correct rays by drawing a line using the DirectionVector and the FixedPoint. I better only post a class below how I did it. If anyone is interested in my full example code you can email me, because I don't want anyone to run into the same problems again by republishing another version of this code.
Thanks a lot for your help.
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using BenTools.Mathematics;
namespace FortuneVoronoiVisualisation
{
class Visualisation
{
public static Bitmap GetVoronoiMap(int width, int height, HashSet<Vector> datapoints)
{
Bitmap bmp = new Bitmap(width, height);
VoronoiGraph graph = Fortune.ComputeVoronoiGraph(datapoints);
Graphics g = Graphics.FromImage(bmp);
for (int w = 0; w <= width; w = w + 20)
g.DrawLine(Pens.AntiqueWhite, w, 0, w, height);
for (int h = 0; h <= height; h = h + 20)
g.DrawLine(Pens.AntiqueWhite, 0, h, width, h);
foreach (Vector v in datapoints)
{
g.FillEllipse(Brushes.Red, (int)v[0]  2, (int)v[1]  2, 4, 4);
g.DrawEllipse(Pens.Red, (int)v[0]  2, (int)v[1]  2, 4, 4);
}
foreach (Vector v in graph.Vertizes)
g.DrawEllipse(Pens.Indigo, (int)v[0]  2, (int)v[1]  2, 4, 4);
foreach (VoronoiEdge edge in graph.Edges)
{
try
{
if (!edge.IsPartlyInfinite)
{
g.DrawLine(Pens.Gray, (int)edge.VVertexA[0], (int)edge.VVertexA[1],
(int)edge.VVertexB[0], (int)edge.VVertexB[1]);
}
else
{
if (!edge.IsInfinite)
{
Vector VVertexB = edge.FixedPoint + edge.DirectionVector*edge.VVertexA.SquaredLength;
g.DrawLine(Pens.Blue, (int) edge.VVertexA[0], (int) edge.VVertexA[1],
(int) VVertexB[0], (int) VVertexB[1]);
}
else
{
Vector VVertexA = edge.FixedPoint 
edge.DirectionVector*Math.Sqrt(Math.Pow(width, 2) + Math.Pow(height, 2));
Vector VVertexB = edge.FixedPoint +
edge.DirectionVector*Math.Sqrt(Math.Pow(width, 2) + Math.Pow(height, 2));
g.DrawLine(Pens.Blue, (int)VVertexA[0], (int)VVertexA[1],
(int)VVertexB[0], (int)VVertexB[1]);
}
}
}
catch (Exception e)
{
}
}
return bmp;
}
public static Bitmap GetDelaunayTriangulation(int width, int height, HashSet<Vector> datapoints)
{
Bitmap bmp = new Bitmap(width, height);
VoronoiGraph graph = Fortune.ComputeVoronoiGraph(datapoints);
Graphics g = Graphics.FromImage(bmp);
foreach (Vector v in datapoints)
{
g.FillEllipse(Brushes.Red, (int)v[0]  2, (int)v[1]  2, 4, 4);
g.DrawEllipse(Pens.Red, (int)v[0]  2, (int)v[1]  2, 4, 4);
foreach (VoronoiEdge edge in graph.Edges)
if (edge.LeftData == v)
g.DrawLine(Pens.Black, (int)edge.LeftData[0], (int)edge.LeftData[1], (int)edge.RightData[0], (int)edge.RightData[1]);
}
return bmp;
}
}
}





Just a note to say I get the same thing unfortunately.





In most cases you have 2 infinite edges per area. Just find the crossing point of them and choose direction from this point to the VVertixA (or the midpoint between Left and Right points) of the edge.





Hi,
Can somebody provides sample code,how to call this function. I am trying following code & getting error as invalid cast
Vector V1 = new Vector(2,2);
Fourtune.ComputeVoronoiGraph(V1);
Quick help would be appreciated.
Thanks
Sunil Terkar





You need to put your values into a List.. like
List v=new List();
v.add(myVector);
//more points added
feed v into ComputeVoronoiGraph
Cheers
Wayne





Hi great code!
I am trying to change your algorithm to fit the needs of sharpmap.geometries.point.
Sharpamap is a GIS .net .
http://sharpmap.codeplex.com/[^]
As you can imagine I am having some difficulties.
any ideas on the steps i should take ?





What problems do you have? Contact me by direct message if you want
B.





i've a problem of virsion with the code diagrm voronoi
i've the virsion 2005 please help me!







General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

