|
Please show a sample with this lib,Thanks
|
|
|
|
|
First of all many thanks for providing this implementation of Fortune's algorithm in c#. The code seems to be working fine on randomly created point sets. However I have tested the code on several point sets of real-world (geographical) data and many times incorrect Voronoi diagrams are the result. I don't know where the error lies but I can send you screenshots+data if you want, to show you the problem.
|
|
|
|
|
Mmmh, we had one real problem and several double rounding errors in the past, but I've used the current version for real applications as well (PIONEER robot laser data) and it worked very well.
Anyway, if you're sure it's not a rounding problem (relevant data <1e-6), I'll be happy to look at the examples you have and try to fix something.
Ben.
|
|
|
|
|
Okay I found the problem and it was my own fault
There were duplicate voronoi sites in the input data set which caused the wrong output.
It seems that the check for identical datapoints in the ParabolicCut routine does not work?
|
|
|
|
|
I would like to congratulation to your work.
This was the unique implementation in a civilized language (as you say).
But I don´t understand why you represent the 2D Vector as a double?
Could you make available some examples?
Bye
Cristiano
|
|
|
|
|
Thank you very much, Cristiano. I dont really understand the question, though. I represent a 2d-vector with two doubles. Single lacks the precision and Decimal is much too slow. There is some downside when it comes to rounding doubles, but I'm confident I got it working. Does that answer your question?
Regards,
Ben.
|
|
|
|
|
Hello!
I have a big problem to use the lib.
I type two code like this
Vector[] v = new Vector[] { new Vector(1, 1), new Vector(3, 1)};
VoronoiGraph r = Fortune.ComputeVoronoiGraph(v);
and then I dont know how to use the result.
Can anyone help me
Give me a little sample(ex:how to draw in pictureBox)
Thanks for help.
Have a nice day!!
Li.
|
|
|
|
|
Ben,
Under what EULA this software is distrubuted?
Best Regards,
Andrea
|
|
|
|
|
|
|
Hi all,
I dont know how to easily update the article so just download the new version from here.
modified on Friday, March 7, 2008 9:46 AM
|
|
|
|
|
Hi BenDi,
Thanks alot for the fast answer. Now everything is there. So then i will give it a big try.
Andre
|
|
|
|
|
New code, but the same old errors.
vectors (1, 1),(2, 3),(5, 1). Result is only 2 edges!
|
|
|
|
|
I've had a look at it and I think I got it (at least I could construct no example that didn't work). Please try it and let me know if you find any.
modified on Friday, March 7, 2008 9:46 AM
|
|
|
|
|
Congratulations!
I did not find any errors. So far.
|
|
|
|
|
First of all: nice work! - (just looked into your code yesterday) !
This means as well I do not yet get all implications (for instance, I would think the data events should be processed in the order highest Y-coordinate to lowest one) but your code seems to work.
This data set did not produce what it should be:
Point(-0.4, -0.4)
Point(-0.1, -0.4)
Point(-0.3, -0.2)
Point(0.05, -0.2)
Point(-0.4, 0)
Point(-0.1, 0)
Point(-0.3, 0.2)
Point(0.05, 0.2)
Point(-0.4, 0.4)
Point(-0.1, 0.4)
(I got my inspiration here: http://www.diku.dk/hjemmesider/studerende/duff/Fortune/[^])
I have it rendered but seem not to be able to post the results - please try it, you'll see a lot of edges get their second point on (+infinity, +infinity).
Thanks and good luck
Puzzled Dirk
|
|
|
|
|
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.
|
|
|
|
|