|
Hi, checked your example, works.
It's perfectly normal that there are edges with VVertexA or VVertexB equal to Fortune.VVInfinity: this means the voronoi edge is unbounded (e.g. if you only have two data points, the graph will have one infinite line between them).
To draw it, the VoronoiEdge offers the FixedPoint and DirectionVector properties:
<br />
Vector A = VE.VVertexA;<br />
Vector B = VE.VVertexB;<br />
if (A == Fortune.VVInfinite)<br />
A = VE.FixedPoint - 10 * VE.DirectionVector;<br />
if (B == Fortune.VVInfinite)<br />
B = VE.FixedPoint + 10 * VE.DirectionVector;<br />
Simple .
Cheers, Ben.
|
|
|
|
|
|
Crap! I hate to say this, but I tested the implementation with some random point sets, and sometimes a vertex is not found. Try this set, Ben! (20 points)
Point(-0.3692434, 0.07671795)
Point(-0.3255264, -0.3873076)
Point(0.1713028, 0.2256131)
Point(-0.2075872, -0.06491974)
Point(0.1658398, 0.3280339)
Point(0.3723957, -0.4436001)
Point(-0.2516395, 0.4356501)
Point(-0.2152362, 0.1000157)
Point(-0.2024738, 0.09652914)
Point(0.306734, 0.04758105)
Point(0.4167807, -0.2370589)
Point(0.1958051, 0.04800395)
Point(-0.250089, 0.4712972)
Point(-0.1643453, -0.1943359)
Point(-0.3176289, -0.07668655)
Point(0.1188253, 0.2242593)
Point(-0.4266324, -0.1413706)
Point(-0.4631779, 0.2715097)
Point(-0.006187368, 0.1215192)
Point(0.2943592, -0.2725327)
Again, good luck!
|
|
|
|
|
Hi Ben,
any thoughts on the point set I provided?
After re-reading my previous post, I see you might interpret it as insulting to you. If you felt offended, I apologise, as it was in no way intented to do so. I was just being very disappointed with the situation, and quoted Calvin (& Hobbes)'s "crap" stop word. I think your implementation is quite elegant on the contrary.
After having tested some other point sets, I still cannot see the logic in the error, as sometimes half-open (half infinite) edges point wrongly, but as well some normal edges are determined badly by the algorithm.
Any chance this has to do with the numerical stability?
Thank for your thoughts!
|
|
|
|
|
Hi,
sorry for the late response. Thanks for the apology, but I didn't feel insulted. If there is something wrong with the algorithm, I want to know .
On the other hand: did you find out why you thought the first point set to produce wrong results? - After my response I would have expected that there is some problem with the way you verify the solution, because there was definitively nothing wrong with the solution to the first point set.
Anyway, I'll try the second set as soon as I can, atm I don't have internet at home (just moved...), so it might take a few days. Numerical stability is an issue in the range of 1e-8 and lower - you can check if thats the problem by simply increasing the range of random values (-100..+100 instead of 0..1).
Cheers,
Ben.
|
|
|
|
|
Hi!
So all is well (*sighs gladly*)
As you say, I agree the first point set was ok - I just did not know how to handle half-infinite edges.
The test program I made simply creates a set of random points and draws them on the screen + and adds the edges your algorithm provides. On most occasions, the voronoi edges you generate are perfect, but in the some cases, you see edges going in a wrong direction, even edges intersecting other ones. I guess it has to do with points that lie close to each other, but I don't understand the calculations anough to tell for sure.
In the hope it helps, I made some screenshots of 2 failing test sets (6 others worked fine).
Note:
- I did not draw the half-infinite edges
- all points (x, y) fall within ([-1,1], [-0.5,0.5]), and the screenshot shows the rectangle (-0.5, -1) -> (+0.5, 1) to give a frame of reference
- The screenshot as well shows the point indices in yellow (in the order as listed below, starting from 0), and marks each edge's LeftSiteIndex and RightSiteIndex in white in this format "(left * right)" positioned at this following location v:
if (!edge.IsPartlyInfinite)
v = 0.5 * (edge.VVertexA + edge.VVertexB);
else
v = edge.FixedPoint;
You can find the screen shots here:
http://picasaweb.google.com/DirkEnKarin/Voronoi[^]
If you have a look at picture 2, you can see that the top big horizontal line is labelled (2 * 3) or (17 * 3). Now, line (17 * 3) is half-infinite, so is not drawn (I should have omitted the label as well) but would start at the point where the label is drawn, which is correct. So the top big horizontal line probably is the line (2 * 3). It does not stop where it should: it should stop at line (16 * 4) but it does not and goes across the entire screen.
If you check out picture 3 and 4, you'll see something strange between sites 0 - 9 - 16. They do not lie too close to one another, nevertheless there are no edges between them.
The first two pics are for these points:
Point(-0,8770161, 0,3571261)
Point(0,4292808, -0,3395853)
Point(0,945165, 0,1813804)
Point(0,9433113, 0,4362702)
Point(0,6853593, 0,1057913)
Point(-0,1928242, -0,2471879)
Point(0,4986012, -0,3799367)
Point(-0,3433116, -0,2408348)
Point(-0,950679, 0,1631617)
Point(0,6521221, -0,4515718)
Point(-0,2668834, 0,1676268)
Point(0,09276361, 0,1915899)
Point(-0,9682054, 0,002640424)
Point(-0,1192675, 0,06113185)
Point(0,9993334, -0,08276763)
Point(0,4726429, -0,008942189)
Point(0,6221064, 0,08648748)
Point(0,935222, 0,4400262)
Point(-0,4584866, 0,3371268)
Point(0,9511338, -0,02942981)
Teh last 2 pics for these points.
Point(0,455355, 0,05829995)
Point(0,1929335, 0,009441835)
Point(0,5437421, 0,3401005)
Point(-0,9115533, -0,08435139)
Point(-0,9706602, -0,2757154)
Point(0,8316388, 0,05917996)
Point(-0,3733743, -0,06540301)
Point(0,5178977, -0,3490196)
Point(0,9790662, -0,3070542)
Point(0,573801, 0,0295283)
Point(-0,4139821, -0,03086267)
Point(0,6281312, 0,3537335)
Point(0,7714128, -0,2068298)
Point(0,2258071, 0,1776088)
Point(-0,5620219, 0,1920761)
Point(-0,9399673, -0,20527)
Point(0,4427027, 0,1926527)
Point(-0,9442763, 0,4856069)
Point(-0,2187746, 0,02522353)
Point(-0,9538777, -0,03065272)
modified on Tuesday, April 15, 2008 5:28 PM
|
|
|
|
|
As i said in another post, it is becouse double.GetHashCode() = evil, also with rounding.
I don't fear computers.
I fear the lack of them.
(Isaac Asimov)
|
|
|
|
|
The link is not working. Can you please update it. Thanks,
|
|
|
|
|
Sorry, moved my website... I updated the link, you can download the new version here.
|
|
|
|
|
|
The program works great. Any thoughts if implement the power Voronoi based the program? Thanks.
|
|
|
|
|
I guess there is a mistake in the code.
I tried vector (1, 1),(2, 3),(5, 1) and got a result only 2 edges!
I am shure, it should be 3 edges.
I suppose the problem is Y coordinate of first point is equal of Y coordinate of therd point. When I changed (5,1)->(5,1.1) I got a correct result 3 edges.
Dim.
|
|
|
|
|
fyi, I see the same result.
Two edges when using (1, 1),(2, 3),(5, 1).
Three edges when using (1, 1),(2, 3),(5, 1.1)
|
|
|
|
|
So, is this a mistake?
Let look to another example.
new Vector(1, 1), new Vector(3, 1), new Vector(4, 2), new Vector(5, 1)
In this case edge between points (3,1) and (4,1) is
LeftData (3,1)
RightData (5,1)
VVertexA (4,1)
VVertexB (2,3)
FixedPoint (4,1)
DirectionVector (-0.7071067812,0.7071067812)
However, VVertexB should be (Infinity,Infinity) and DirectionVector (0,-1)!
Dim.
|
|
|
|
|
I'm very busy this week, but I'll have a look at the code next weekend. B.
|
|
|
|
|
Sorry I am new to Voronoi diagram and C#.
Could you post an example for me to test the source??
I dunno the meanings of the attributes, and what is the input and output??
Thanks
hello
|
|
|
|
|
Just a very short one:
first of all: dont worry about the attributes, that's not a part of the library. To compute a voronoi diagram you can do somthing like this:
<br />
Vector[] DataPoints = new Vector[]{};<br />
VoronoiGraph Result = Fortune.ComputeVoronoiGraph(DataPoints);<br />
Cheers, B.
|
|
|
|
|
Please tell me how could I compute voronoi's cell data such as area, perimeter ... and how do I traverse the entire graph with simple algorithm.
-*- Nothing impossible -*-
|
|
|
|
|
Mmmh, dont have a trivial solution for that, especcially since the cells might be infinite. It's not hard to find out which voronoi vertices are around one data point, you'll just have to look though all the edges and take the vertices of all edges that have the desired point either as left or right data point. From that set of vertices you should be able to compute cell data using some matrix operations, dont have an implementation for that, though.
|
|
|
|
|
Hello !
I've tryed to use your Fortune's implementation with about 5000 datapoints like this one: (-100085.42,-96826.36), and the result is not a correct Voronoi Diagram, it has a lot of errors. I can show you an image if you want.
Do you have any ideia of what may be the problem ? (too many datapoints, or too big values ?)
Thanx,
ramirob
|
|
|
|
|
I have tested the algorithms with great numbers of points (although they where always on a grid). I also had a few dificulties with minor rounding errors during development but thought that I eliminated them (because I never had a problem with it). I would like to see that image, yes.
B.
|
|
|
|
|
Hi
I have got the same problem. When datapoins number is over then 400 sometimes there are errors . I have noticed that probability of errors is growing with the number of points. but it is clear
I can send You an image or form with graphical implementation of your lib.
best wishes
TomekS
-- modified at 16:12 Monday 20th March, 2006
OK
Errors occures when two or more datapoints are identical. It can happen when we use Random.Next() methot to generate Vector object on a small bitmap.
We can use:
Vector v = new Vector(0,0);
v.Randomize(min,max);
to eliminate such errors or strongly eliminate identical vectors.
Cheers
Thx again for lib. It is great. At least Fortunes implementation in "civilized language"
|
|
|
|
|
I'll have a look at the form if you want, maybe I can fix it using your samples. B.
|
|
|
|
|
I'm not sure how to draw a semi-unbounded edge. My first try was to find the midpoints of the two original vertices and draw an "infinite" line from VVertexA through this midpoint. Unfortunately, sometimes the edge should be drawn away from this midpoint rather than through it. So it would seem that in addition to knowing the two originating vertices and the node in the voronoi diagram I also need to know whether to draw the unbounded line *towards* the midpoint of the originating vertices or *away* from the midpoint. Is there some way of telling this that I'm just missing or is it really something that needs to be added?
Thanks!
Darrell Plank
-- modified at 15:26 Tuesday 13th December, 2005
|
|
|
|
|
Jep, I ran into this problem a while ago and fixed it. Since I absolutely hate the way I have to re-submit everything to update the download link, I have just put the file here.
The VoronoiEdge has some new properties (IsInfinte, IsPartlyInfinite, FixedPoint (a point that is certainly on the line) and DirectionVector (multiply with 0..1 for bounded, 0..inf. for partly bounded and -inf..inf for unbounded edges and add to FixedPoint to create all points)). This also required a small adjustment to Fortune's algorithm to traverse the edge tree at the end to see which edges are (partly-)unbounded and mark them with VVInfinite (instead of VVUnknown).
Hope it works,
Ben.
PS: It runs on .NET 2.0 now, but you can kill the generics in HashSet by hand if thats a problem.
|
|
|
|
|