Polygons from Points
-
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!
-
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...
-
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 :)
-
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 -
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, 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.
-
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.
-
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.
