|
To merge K trees in O(N), where N is the sum of node counts, you must never search on insertion: all your insertions must complete in O(1). In other words, on each step you must insert the new root node, and maybe do a rotation or two. However, the new root could come from any of the K trees that you are merging, so the time to search for that node would be O(K) (perhaps you could do O(Log2 K), but regardless of how you do it, K will be a factor to it). That's why I think the best you can do is O(N*Log2 K).
|
|
|
|
|
i liked that idea, lets say we've got k tree where each one got one node.
we know that there is no algorithm that can sort with better than teta(klogk) so, in order to sort the nodes in array and scan an empty tree to insert them, it will takes at least teta(klogk)
|
|
|
|
|
Who can tell me more about Eye-like Algorithm?
|
|
|
|
|
|
I don't want google I want to hear the opnion of our fulks here in CP what they have to say about this subject.
|
|
|
|
|
I never heard the term, but back in the 80s I worked at a place that was doing (among other things) research on computer vision.
One innovation (by Stan Sternberg) was the use of Lissajous curves (http://en.wikipedia.org/wiki/Lissajous_curve[^] ) to adaptively trace the outline of an object like a real eye.
The algorithm would sample a single point on the curve at regular intervals and slightly adjust the Lissajous parameters to adaptively fit the edge of the object. (E.g. if it hit the interior of the object, it would expand the curve accordingly, and if it hit the background it would contract.)
For some tasks it was orders of magnitude faster than traditional algorithms that looked at every pixel.
|
|
|
|
|
Finally some one with an answer.
|
|
|
|
|
This is a bit of a 'name that method' query - I'm sure there must be a way to do this!
Say I have a set of 2D points with data values attached to them. Let's say the data is 0 - 100. If I colour the points in the ranges 0-19, 20-30, 31-69, 70-80 and 81-100 I will get five or more regions (which may include "islands" of data, and there may be several of each colour, and they are not necessarily connected).
I want to display those regions as a set of congruent polygons - how can I find the polygons?
I could grid the data and calculate iso-lines, but I was wondering if I could search each point and "assign" it to a polygon somehow (like a flood fill on the points?).
My data is ordered in a grid-ish manner (by "column") if that helps any.
Suggested approaches welcome.
Thanks!
|
|
|
|
|
Kyudos,
your problem statement is not totally clear to me. A figure would be helpful.
You can form polygons around your point clouds by means of the convex hull construction (tightest convex polygon that includes all points); if you mention unconnected islands, this means that convexity is a too strong requirement. You could resort to Alpha-shapes, a generalization of the convex hull (see http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html).
This suggestion only allows you to process each class independently, it will not guarantee that the polygons are nested. This requires a more general approach.
Another answer is provided by the Voronoi diagram, a tiling of the plane where every point is associated to all points that are closer to it than to another point. (http://en.wikipedia.org/wiki/Voronoi_diagram). Coloring the diagram will give you the desired polygon set (in reality some discrete form of iso-lines).
Maybe the specific arrangement of your data points can provide shortcuts to the solution...
|
|
|
|
|
Thanks for the reply. I created a couple of figures that may help.
Area[^]
Area Detail[^]
I'd want a polygon for each of the coloured areas, but bearing in mind that there may be no areas of any given colour, or several unconnected areas that may be islanded (e.g., there could be a "yellow" island in the middle of the "green").
Seems like Alpha-Shaped convex hulls might do the trick - will look into it 
|
|
|
|
|
Ah, the images sure help. I didn't have a clue what your description was about, but now I see.
Alas I don't know the official algorithm(s) that would do exactly this for you, however it resembles the flood fill problem, so I would read up on that, and study the A* algorithm.
Luc Pattyn [My Articles] Nil Volentibus Arduum
The quality and detail of your question reflects on the effectiveness of the help you are likely to get. Please use <PRE> tags for code snippets, they improve readability. CP Vanity has been updated to V2.3
|
|
|
|
|
Ah, this is quite different from what I had imagined (I thought of much sparser points irregularly arranged) !
There is a much simpler way then.
Consider every rectangular stich (or are they quasi-rectangular ?) in the grid in space and "cut" it with a plane at altitude 20 (say). You test every edge of the stich for intersection with this plane, just by detecting a change of sign in the Z coordinate mins 20. Then linear interpolation gives you the X and Y coordinates of the intersection point.
The Z test is such that you'll get an even number of intersections. When you have two of them, join them with a line segment; when you have four of them, join with two line segments using a nearest neighbor rule.
After doing that, you will obtain a nice polygonal decomposition of your domain. In reality, a C1 continuous approximation of the level curves. This takes two hours to implement.
If you need polylines rather than isolated line segments, it is possible (and not so difficult) to follow paths in the grid: every time you find an intersection in a stich, it is joined to a second intersection point in the same stich; this other intersection point also belongs to the neighboring stich, and so on, and so on.
Is that clear ? If you need more details, please ask me.
|
|
|
|
|
Ooops, did I say C1 continuty ? No, it's only C0. (C1 is achievable by using a more elaborate interpolation scheme inside the stiches, giving you smooth curves.)
|
|
|
|
|
Very good post. I had the same thought (that it was a few points scattered in space). The array certainly appears to be close enough to a grid to use a slightly modified version of normal grid-based contour finding.
|
|
|
|
|
I'm trying to construct a database of all the data types defined by the Win32 API.
I'm using the DIA SDK to read pdb files in order to extract the type information.
My question is the following:
The recursive nature of data type declarations makes it very difficult to flatten them into a traditional row and column structure.
Am I doing it the wrong way? Is there an easier structure I could use for my database?
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Hi Richard,
I'd suggest you google tree in database, and read some of the articles, maybe this one: Implementing a Tree Structure with Database[^]
Luc Pattyn [My Articles] Nil Volentibus Arduum
The quality and detail of your question reflects on the effectiveness of the help you are likely to get. Please use <PRE> tags for code snippets, they improve readability. CP Vanity has been updated to V2.3
|
|
|
|
|
Hello, I have a big maze (800x800) and I need to search for a shortest path on it, from one point to another.
I tried wave algorithm but it is very-very slow. I have to wait for several minutes.
Are there path finding algorithms that can accompish such a task relatively quickly?
|
|
|
|
|
Depending on the type of maze, you can just stick to the right wall the entire way and you will eventually get out of the maze, though it won't be the shortest path. Wouldn't work if the destination is in an island (e.g., where the ghosts go to in Pac-Man). Though, a properly implemented flood fill (maybe this is the same as your "wave algorithm") should find the exit fairly fast. It certainly shouldn't take minutes (should work in a few milliseconds on a modern computer). Can you post your implementation of the algorithm that is too slow?
|
|
|
|
|
finding a path is easy and can be handled quickly, finding the or a shortest path is quite difficult, as you have to consider a lot of possibilities, assuming a non-trivial maze. You have to choose your algorithm carefully, and then implement it even more carefully. And what is the information you have: the full map? or are you supposed to discover the maze while travelling?
Luc Pattyn [My Articles] Nil Volentibus Arduum
The quality and detail of your question reflects on the effectiveness of the help you are likely to get. Please use <PRE> tags for code snippets, they improve readability. CP Vanity has been updated to V2.3
|
|
|
|
|
I have lines on the image control that are like "walls" and I need to bypass them. Also I have two points, that I need to connect.
|
|
|
|
|
If the map is known beforehand, I think there are basically three ways:
1. start travelling in one direction, and implement backtracking (e.g. the righthand-on-wall approach). This is simple but may be slow.
2. perform what looks like a flood fill, i.e. start in all directions and visit everything for sure (look at A* algorithm).
3. turn the map into a graph and analyze the graph (sorry, no reference handy).
I'm not sure what is best when the goal is "find a shortest path with minimal effort". I'm not sure any of the above is always the best pick anyway.
Luc Pattyn [My Articles] Nil Volentibus Arduum
The quality and detail of your question reflects on the effectiveness of the help you are likely to get. Please use <PRE> tags for code snippets, they improve readability. CP Vanity has been updated to V2.3 modified on Friday, June 10, 2011 8:50 PM
|
|
|
|
|
Is this how your "wave algorithm" works?
|
|
|
|
|
Probably the best way is to convert the maze to a connectivity graph this will get the datasize down. Intersections are nodes and corridor lengths give the weighting.
For this you need some kind of linked list structure. Each node having a pointer to all connected nodes with a weighting for each link.
With that you can use either brute force with a recursive algorithm to take every path (but beware of loops) if it is small or apply something like Dijkstra's algorithm (see wikipedia) to it.
DC
Always remember that you are unique- just like everybody else.
|
|
|
|
|
Sorry for the late response, I was going back over some of old entries in the forum that I had not reviewed yet.
I have a question (or observation as the case may be) about the "wave algorithm" as it applies to a maze.
If you start at either point and flood fill, you may go down many unproductive paths (in paralel - the wave front expands equally from all points). It takes time to fill all the dead ends. Eventually the other point will be found.
What about starting the flood fill at both points? You may fill some dead ends from both points, but when you finally collide with the other wave front, it is "Game over!", stop filling the dead ends. OBTW, the flooding must be with different colors from each point to be able to correctly identify looping paths from either end - you need to find the opposite wave color to claim a complete path.
To identify the actual path from the first point to the second point, save (in a solution array that has the same size as the array) the x-y coordinates (or point ID of some kind) of the originating point that was being processed when this new point was flooded, into the array position for the new point. Do this for points starting from the first point (the first color). For the points starting from the second point (the second color), save the new point ID in the current point array position so the path is consistent. To walk the path, start at the second point in the solution array and backtrack to the first point. If you are processing blocks of points in a maze (i.e., 8x8), then you only need a solution array big enough for the number of blocks, not big enough for the number of pixels.
Dave.
|
|
|
|
|
Sorry for the double post.
What was I thinking!
This will not work:
To identify the actual path from the first point to the second point, save (in a solution array that has the same size as the array) the x-y coordinates (or point ID of some kind) of the originating point that was being processed when this new point was flooded, into the array position for the new point. Do this for points starting from the first point (the first color). For the points starting from the second point (the second color), save the new point ID in the current point array position so the path is consistent. To walk the path, start at the second point in the solution array and backtrack to the first point. If you are processing blocks of points in a maze (i.e., 8x8), then you only need a solution array big enough for the number of blocks, not big enough for the number of pixels.
What it should read is:
To identify the actual path from the first point to the second point, save (in a solution array that has the same size as the array) the x-y coordinates (or point ID of some kind) of the current point that was being processed when this new point was flooded, into the array position for the new point. Do this for all flooded points starting from either direction. When the collision occurs between the two wave fronts, you have two adjacent positions marked with different flood fill colors. For each of these positions, backtrack to the originating point and mark the positions with a shortest path color, then scan the entire array and mark all positions that are in either flood fill color with the normal color of the hallway. You will be left with the walls, the halls, the start and end points, and the shortest path between the points. If you are processing blocks of points in a maze (i.e., 8x8 blocks in a 800x800 maze), then you only need a solution array big enough for the number of blocks, not big enough for the number of pixels.
Dave.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
