

On line 350 of FortuneVoronoi.cs in CircleCheckDataNode(), after creating a new circle for three points the code checks if the bottom of the circle is below the most recently added point, since if the circle is above that it would defy the sweep line
if(VC.Y>=ys)
However you round the circle y value to 10 decimal places, so in extreme situations where the new node is at the exact bottom of the circle it can have higher precision on its y value and invalidate the circle, throwing off the whole graph. The if statement needs changed to something like
if(VC.Y>ys  Math.Abs(VC.Y  ys) < 1e10)
to account for it
http://puu.sh/2CVs2.png
http://puu.sh/2CVsK.png
An example graph exhibiting this problem, with the offending point marked red, before and after fixing





Thanks! I was trying to reduce the rounding problems for a while now, good work.
To make changes more easy in the future and since I don't have a lot of time to work on this, I moved the code to Google Code.





I always find it harder to read someone else's code. I was hoping to use this to get me started in making some really unique terrain generation, but I can't seem to understand where to start. If someone could send a visual studio project with the most simple beginning I would greatly appreciate it.
modified 19Apr13 9:29am.





Almost no comments in the code. Some things could be implemented in a nicer way.
But the code is working fine.





I've been able to draw the data nicely with the help of XNA, but how do I get a region? so for instance I can retrieve point data and edge data to draw point and lines, but is there a way to define a region? Here is a simple windows form I set up >> http://nbixel.tumblr.com/post/37385174326/beenwantingtocreateproceduralmapgeneration[^]  Ive since created a new program for more felxibility, like move points or removing them. But i want to add a method of create primitives based on the region.





Do you want to get the polygons of the voronoi regions? (Might be tricky, you need to collect all the intersection and somehow order them.).
Or do you want to triangulate the data points (so called 'Delauney triangualation')? This is very simple, you just have to connect the original data points every time they have a common voronoi edge, which will magically lead to triangles.





oohh interesting... I actually want the regions, but I will try and experiment with the getting the triangles as well. I figured it would be harder than just simply tally up all fixed points associated with the center point. Since I have a working GUI I can have the user pick the fixed points and create a poly shape from that. Of course this would be a little tedious but that's a good start until I find a way to code it. I may post a link to the program at some point so people can try it out.





I am looking for a method that will allow me to separate all edges and vertices that describe a sampled medial axis from from a closed polygon of points.
I would like to accomplish this so I can then fit an individual geometric component to each branch of the medial axis, whether it be a line, spline, or arc.
I was thinking of creating a method for the separation using a depth first search that marked each vertex with a degree of greater than one as the split point. I would like to find a algorithm or library that might accomplish this if possible. No need to recreate the wheel. Looking for some good ideas...





I am attempting to use this Voronoi algorithm for medial axis computation of a closed boundary of lines, curves, or splines. I have sampled each boundary edge type to create a point at some distance value for a line or arc length of a curve. I then pass these set of points, which represent a filtered closed polygon of the boundary, into the ComputeVoronoiGraph function. I am returned VoronoiGraph vertizes that represent the sampled medial axis.
One of the other challenges is that I would like to fit lines, arcs, or splines to the vertizes. But that is a different story...
By definition a medial axis is represented as the center points of all inscribed circles that fit within the boundary, which is what I currently have. Although what I would like to also find is the radius of each of the vertizes (inscribed circle center points) that are returned from the ComputeVoronoiGraph function. Any pointers on how to accomplish this? Can I get this information from the algorithm somehow?
My intention is to compute the medial axis and filter it similar to the Scale Axis Theorem





Very interesting question! The voronoi algorithm places voronoi vertices in the center of circles described by three data points each, i.e. each voronoi vertex should be the center of an inscribing circle  iff it is inside the polygon.
So it should just be a matter of computing the closest data point for each vertex and determining whether the vertex is inside the polygon.
See very good algorithm description here: nms.lcs.mit.edu/~aklmiu/6.838/L7.ppt






Good comment on the link. I have seen this video and even briefly looked into utilizing the code. I believe the code for Mesecina has been released. Although I decided to look elsewhere for because the voronoi computation utilizes CGAL, which I wanted to avoid.
I did implement a method of finding the radii of each of the vertices by computing the polygon point that has the minimum distance and setting this magnitude as the radius value for each vertices. Although before hand I also have a quick method that filters the vertices and edges that lie outside of the polygon. I accomplish this using the method described in this CodeProject article, Is a Point inside a Polygon?[^]. First the point is checked to see if it lies in the polygon min and max x and y values. If so, the point is then checked using the algorithm from the article, which uses each polygon sample point for each voronoi vertex for the check. This does take some computation time.
I am sure that there is a more efficient way to accomplish filtering only vertices and edges that lie in the polygon. Although because of this increased computation time I have considered diving into the Voronoi algorithm to see if the radius value can be found during the sweep line algorithm. Or I was thinking for each medial axis voronoi vertex the radius can be extracted by finding the intersection of the infinite edge attached to the medial axis voronoi vertex. This may be the most efficient approach.





Hello,
Is there a way to construct polygons from all the edges ? And how ?
Regards





Hello,
I think there is a mistake anywhere, when I draw 2 points the program don't give me 2 area. On each applet I could test (ie : http://www.cs.cornell.edu/Info/People/chew/Delaunay.html) when we draw a least 2 points we can see a line.
I don't understand the difference between the appel and your code
Regards





2 points is a special case I really didn't spend time on, so it's quite possible it does not handle it. Everything from 3 points up should work fine, though.





In fact the real problem is that some points are not separated by a line especially near the border of the area. I think it's the "rays" problem expose in some other thread.
Have you got a solution for that ?
Regards





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?



