|
Try non-parametric kernel density estimation to fit it. That way you don't have to assume a distribution a priori.
Link[^]!
|
|
|
|
|
looks promising... just need to change my question to how to do that! (or read more...)
Iain.
|
|
|
|
|
Hi Iain,
Kernel density estimation is not as complicated as it sounds. You just need the two functions from the Wikipedia article I linked to. The real problem is the choice of bandwidth, h. You can actually adjust this manually - algorithms for calculating h based on your sample can be more complicated than the density estimation itself. I always adjust h by hand (well, in most cases!).
|
|
|
|
|
Well, I'll be writing myself a dialog app with some self generated data later, and I'll see how well I've absorbed that page!
Should wake my brain up at the very least!
Iain.
|
|
|
|
|
If you need help, post here. I keep checking this forum.
|
|
|
|
|
PLZ SEND CODE. URGENTZ!!!!
Iain.
|
|
|
|
|
|
Dear All,
i have a list of edges like
(0,0),(2,0)
(2,3),(3,4)
(2,0),(2,2)
(0,0),(1,5)
(1,5),(1,10)
(3,4),(3,10)
(2,3),(1,5)
(3,4),(4,0)
(1,10),(3,10)
If you draw these edges on a Cartesian coordinate system, you visually see 3 polygons.
In mapping applications, a polygon is defined by a continuous, closed set of data points. So, output required is a a list like this.
(0,0),(2,0),(2,3),(1,5),(0,0)
(2,0),(4,0),(3,4),(2,3),(2,0)
(2,3)(3,4),(3,10),(1,10),(1,5),(2,3)
Can you please guide me how to????
Simplifying, i need to have Voronoi polygons around my points. Voronoi algorithms gave me the list of edges, but i am unable to get polygons from those edges.
Hope some one can guide!!!
|
|
|
|
|
Do you know a priori how many sides each polygon has?
Also, is this an ordered list?
|
|
|
|
|
we dont know about the no of sides, each polygon has different no of sides
what is meant by ordered list in this case? the list is totally random, just a list of all the edges, no ordering at all.
Thanks for looking into this!
ANY IDEA NOW?
|
|
|
|
|
furqan_sindhu wrote: what is meant by ordered list in this case? the list is totally random, just a list of all the edges, no ordering at all.
This is what I was trying to understand when I asked about an ordered list. If all the points are simply in a random list, how can you possibly reconstruct the polygons based only on a list of random points? The problem is that polygons can take on complicated shapes, so you need to know something about number of sides and/or which points should belong to which polygons. At the very minimum, the points should be ordered according to which polygon they belong to. Is there no way of doing this? Can't you create a polygon class that contains a list of points, for example?
|
|
|
|
|
You might want to check in "Algorithms" by Robert Sedgewick, published by Addison-Welsley. He has several algorithms, including "Convex Hull" and "Voronoi" for solutions for these problems.
Dave.
|
|
|
|
|
I'm not familiar with the book or the algorithms, but I don't think he's trying to construct the convex hull. I think he's got a randomized list of polygon edges for separate polygons and he's trying to reconstruct the component polygons from the list. A convex hull can certainly be determined given the points, but I'm not convinced that's what he wants to do.
|
|
|
|
|
My reply was more directed to his statement that he didn't know what to do with his Voronoi edges. In addition, his stated edges do NOT form three polygons. There are two missing edges one between 2,2 and 2,3, and the other between 2,0 and 4,0, both of which he filled in in the case of the polygon descriptions. He is forming a convex hull with enclosed polygons. He also probably wants to split up the polygons into triangles, but that is another topic.
Dave.
|
|
|
|
|
So the list isn't even complete? Hmmmm. Methinks he needs to put a little more forethought into this one. It helps to have the problem well-defined first!
|
|
|
|
|
oh, i had a look at your message a little late "Member 4194593".
thanks for your reply.
i think i accidentally missed those edges. my apologize!!!
i dont want to construct triangles, rather polygons. i will have a look at those alogs!
|
|
|
|
|
I have thought about the problem these last few days. Googled for "Convex Hull" and read all of the related articles. Usually only points are given, not edges. If edges are given, wouldn't at least those edges be required in the final solution? I don't think that eliminating one of these edges would be a solution. If you are given a triangle, then it is a triangle area, you can't make it a square by combining it with some other area - people don't take kindly to "re-districting" or "Gerrymandering".
Fortunately, it has been proven that you only need 4 colors to tint your map when you get it done.
I would be interested in the exact phrasing of the problem as given, along with your final solution. I love algorithms and I frequent these halls daily.
I am serious about the book "Algorithms" - there is such an abundance of simple piece-wise efficient solutions to this type of problem described in this book, and Sedgwick explains it so clearly.
Dave.
|
|
|
|
|
well,
i dont know anything at all. i just have a list of edges and thats all.
I was working on this and uptil now, i have come up with some code that gives me all possible polygons from those edges.
All possible means that it returns those polygons as well that contain multiple small polygons too. I am trying to come up with something to eliminate these bigger polygons 
Anyways! i think i will get it done, inshaALLAH.
|
|
|
|
|
I think you have some errors in the list of edges. For instance, your polygons include an edge from (2,0) to (2,3) but there is no such edge in your list of edges. Anyway, I think what you're suggesting here is that you've got a list of edges and vertices which define a mesh (often referred to a "boundary representation") and you want to find the polygons in that mesh. I'd suggest that you look at Winged Edge representation, turn your edges into a winged edge rep and get your polys from that. Essentially, you'd have to keep a list of vertices with the edges around them in clockwise order, then traverse each vertex and trace out each poly between adjacent edges. You have to be careful about skipping over polys that have already been listed which means you have to keep track of the polygons each edge separates. It'd be a bit ugly, but I think that's pretty much what's required. It would also mean that the area surrounding the entire mesh will be represented as a "polygon". You can recognize that polygon by looking at the rightmost vertex, getting the first edge from it that is CCW from vertical and the flagging the polygon clockwise from that edge as the "exterior polygon".
If you're looking for a Voronoi diagram that keeps a record of all the polygons, I've got one that I've been thinking about putting up on CodeProject. There's a fortune algorithm already out there on CodeProject, but it has some bugs and pretty much has a dump of edges like you're talking about without an indication of the polygons each edge goes with. Mine gives a full winged edge representation of the diagram which includes all the polygons, edges and vertices with them all hooked together intelligently. If that's what you're looking for, perhaps I'll put my fortune algorithm up earlier rather than later.
|
|
|
|
|
I have n random variables. Each random variable is normally distributed with mean 0 and variance 1. In addition, I have a function which I can call which will return a normally distributed random value with mean 0 and variance 1. For each pair of variables, I have their correlation. I would like to generate a list of n random values (one for each of the n variables) such that the given correlations apply. What algorithm should I use to do this?
Thanks
Bob
|
|
|
|
|
Do you mean a single random variable with a fixed autocorrelation structure, or are you taking about multiple random variables with a given correlation matrix?
In any event, there are two main ways of doing this; either by Cholesky decomposition or eigenvector decomposition. Cholesky decomposition is probably more conceptually simple.
For normal variables, the basic idea is to find a matrix U such that U'U = C (where U' is the transpose of U) and C is the given correlation matrix. You can then generate correlated random numbers, N' from random numbers N by multiplying by U. That is:
N' = NU
So, how to find U? Like I said, either by Cholesky decomposition or eigenvector decomposition. Until I know what you really want to do, I'll give you the case for pairs of r.v.'s.
For pairs of normal variables, you can generate two sequences of normal r.v.'s, say X1 and X2. Given correlation, p, the new sequence, Y is calculated as:
Y = p*X1 + sqrt(1-p^2) * X2
This will give you a sequence Y that has correlation p with sequence X1. If you want a fixed correlation structure between more than two sequences, we'll have to get into matrix calculations.
|
|
|
|
|
Zeppelin,
Thanks for the response. I am talking about multiple random variables with a given
correlation matrix. I am familar with Cholesky decompostion but not eigenvector decomposition.
Bob
|
|
|
|
|
Cholesky decomposition and eigenvector decomposition will give you the same result for this problem. Since Cholesky is easier to implement, I'd suggest using that method.
The method is just a matrix form of the calculation I described above.
We want U'U = C where C is the correlation matrix. So, assemble your correlation matrix and apply Cholesky decomposition to it. This gives you U. Generate, say, 5 series of random variates of 100 observations. Assemble those 5 column matrices into a large matrix so that the dimension of N is 100x5. This means the correlation matrix has to be 5x5 and contains your known/desired cross-correlations. The 5 correlated series are simply N*U. All done!
Eigenvector decomposition proceeds in a similar fashion but is more complicated to implement. Given the correlation matrix, C, you calculate its eigenvectors and eigenvalues (standard linear algebra). If the eigenvectors are E_i and the eigenvalues are L_i, where i is a subscript, then we calculate a matrix V such that:
V = E_i*diag(sqrt(L_i))
where diag is a diagonal matrix with L_i on the diagonal. Because of it's construction matrix V will have the property that: V'V = C, C being the correlation matrix. Then, as above we have U'U = C where, conveniently (ha!) U = V'.
Nifty, but a roundabout route and used mainly for matrices that have problems being decomposed via Cholesky. Now our correlated random numbers, R_c are just:
R_c = R*U where R is the matrix of original random numbers.
|
|
|
|
|
Zeppelin,
When you write U'U = C, is U' the transpose of U? I am thinking that U' should be lower triangular and U should be upper triangular. In addition, U' should have all 1s on its main diagonal. Is this right?
Thanks
Bob
|
|
|
|
|
Yes, sorry. The prime indicates the transpose. U should be upper triangular if C is positive definite, correct. Thus U' will be lower triangular.
Certainly C should have all ones on its main diagonal (and be symmetric) but U may not necessarily have all ones, no.
A quick calculation using the correlation matrix C:
1.0000 0.6000 0.3000
0.6000 1.0000 0.5000
0.3000 0.5000 1.0000
gives U as:
1.0000 0.6000 0.3000
0.0000 0.8000 0.4000
0.0000 0.0000 0.8660
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
