Reduce number of points in polygon

1
votes

I have a table in sqlserver with 55k geometry points. Each point are 5 meters apart and have a value assigned to them. My task is to draw these points in a google map. Early I concluded that google maps could not handle drawing the 55k points. So I figured I had to group the points by value (10% intervals, 1-9,10-19 etc) to form polygons. However the polygons still consist of the same amount of points. I need to reduce the number of points in each polygon. I need the polygons to atleast roughly keep their shape, so convex hull is out of the question.

Getting the concave hull/alpha shape would be the best solution I guess, but I haven't been able to find an implementation of it for sqlserver 2008 r2 or a .NET assembly / function.

It would also be acceptablef or me to just get the points that creates the outer line of the polygon, so I can pass those points to Google Maps and make it draw the polygons.

Here is a picture of how the collection of points for a polygon looks:

2
.netsql-serverpolygon
Do you just need to see the positions of the points? Or are you going to use the polygons for some other purpose like to test if a point is inside, or to fill the polygons? What I am asking is if it is ok to treat the polygons purely as a set of points or not? – Mark Setchell
I need to draw the polygons in a Google map, so I do not care for the points inside the polygon. My experience is that Google Maps will draw lines to each point inside if I pass it a collection of all the points. So I just need to points that make the outer border of the polygon. Here is an image of how it should look in the end. This image is created using a GIS program that can handle drawing all the points. Image – Kennedine
You didn't answer my question... is it ok to just draw 55,000 points on the map and ignore the fact that they form a polygon? – Mark Setchell
In theory it would yes, but the map cannot handle drawing 55k points, hence why I am forced to create polygons to reduced the number of points. – Kennedine

2 Answers

1
votes

If you just want to see 55,000 points on a map but don't care that they form a polygon - so you will not be able to fill the polygon with colour, for example, you could use Google Fusion Tables.

They support 100,000 points per layer and 5 layers in toto - i.e. up to 500,000 points. They are lightning fast too as you access them via an SQL-type language that runs on Google's servers - exactly where your data will be when you upload it.

You load your CSV into a Fusion Table in your Google drive and get a key to that table and you then use the key in your Javascript.

I created the following website with Fusion Tables and I am a zero in Javascript! See Skyscan website here

enter image description here

0
votes

"Each point are 5 meters apart and have a value assigned to them."

That sounds a lot like you can treat the point set as a sparse 2D (boolean) matrix. You can use this to remove redundant points in the center of the shape. This could be applied to alpha shapes as well, but it only works well when the points are tightly packed together as in the case in your example and as implied by the above line in your question.

The pseudocode (not sure how to actually implement it in the languages you seek) for a single pass looks like this:

Verify that the points are lexicographically sorted
Create a list to hold the unfiltered points
Create a set of the points for the fast membership tested needed
For each point:
    If none of patterns are present:
        Add the point to the list of unfiltered points
return list of unfiltered points

The patterns are based on a 3x3 matrix, which represents the offsets from the center. So the center is (00,00), since it is not offset from the points. There are 12 main patterns to look for in the 3x3. Which can then be generalized into larger odd sized square matrices (5x5, 7x7, 9x9, 13x13...). The 3x3 with the offsets looks like this:

[[(-5,+5),(00,+5),(+5,+5)],
 [(-5,00),(00,00),(+5,00)],
 [(-5,-5),(00,-5),(+5,-5)]]

The 5x5 with offsets looks like this:

[[(-10,+10),(-05,+10),(00,+10),(+05,+10),(+10,+10)],
 [(-10,+05),(-05,+05),(00,+05),(+05,+05),(+10,+05)],
 [(-10,000),(-05,000),(00,000),(+05,000),(+10,000)],
 [(-10,-05),(-05,-05),(00,-05),(+05,-05),(+10,-05)],
 [(-10,-10),(-05,-10),(00,-10),(+05,-10),(+10,-10)]]

Just using one of the 12 patterns below will remove a lot of points leaving just the outer and inner (if the polygon isn't filled in) hull. The additional patterns are used to reduce the number of points in the outer/inner hull. This may be enough for your purposes. However, each additional pass should only remove about half the remaining points, but the number of patterns to look for grows at a rate of O(p^2). Note that p is O(d) where d is the greatest distance between two points in the point set, which in this special case is O(N). This should be enough to allow for a simple graph algorithm to extract the outer concave hull by picking an element on the convex hull and walking around the shape to produce the concave hull. Further passes will further reduce the number of points until some point dependent on which patterns are used. In the extreme case, it'll reduce it to a triangle.

There are then 12 patterns to look for to determine if the center point is redundant. This is done by checking if the center point is on a line (for the first four) or an approximate line/arc (last 8). Note that only one of these are needed to actually hollow out the point set. The rest are simply used to further reduce the number of points.

 1. [[0,1,0], |  2. [[0,0,0], |  3. [[1,0,0], |  4. [[0,0,1],
     [0,1,0], |      [1,1,1], |      [0,1,0], |      [0,1,0],  
     [0,1,0]] |      [0,0,0]] |      [0,0,1]] |      [1,0,0]]

 5. [[1,0,0], |  6. [[0,0,1], | 7.  [[0,0,1], | 8. [[0,0,0],
     [0,1,0], |      [0,1,0], |      [1,1,0], |     [1,1,0],  
     [0,1,0]] |      [0,1,0]] |      [0,0,0]] |     [0,0,1]]  

 9. [[0,1,0], | 10. [[0,1,0], | 11. [[1,0,0], | 12. [[0,0,0],
     [0,1,0], |      [0,1,0], |      [0,1,1], |      [0,1,1],  
     [0,1,0]] |      [0,1,0]] |      [0,0,0]] |      [1,0,0]]

The patterns are intended to form arcs with the center point as the point under consideration. The above arcs are really more for example. To make things easier, only two more general patterns are used they are listed below. Note that at least one 2 must be present at at least one 3 must be present. If this is done until 

13. [[2,2,2], | 14. [[2,0,3],
     [0,1,0], |      [2,1,3],
     [3,3,3]] |      [2,0,3]]

Extending 13 and 14 to a 5x5 (second pass) results in the following:

15. [[2,2,2,2,2], | 16. [[2,0,0,0,3],
     [0,0,0,0,0], |      [2,0,0,0,3],
     [0,0,1,0,0], |      [2,0,1,0,3],
     [0,0,0,0,0], |      [2,0,0,0,3],
     [3,3,3,3,3]] |      [2,0,0,0,3]]

A further generalization of 13 and 14 resolves some offset issues and leads the following in the 5x5 case. Although, care needs to be taken to avoid duplicating work of previous passes.

15. [[2,2,2,2,2], | 16. [[2,2,0,3,3],
     [2,2,2,2,2], |      [2,2,0,3,3],
     [0,0,1,0,0], |      [2,2,1,3,3],
     [3,3,3,3,3], |      [2,2,0,3,3],
     [3,3,3,3,3]] |      [2,2,0,3,3]]

Leaving the outer/inner hull intact:

The goal of the above is was to reduce the number of points and I included points in the hulls in that as well. If it is desired to only remove points between the hulls, then each pattern can check for more than two neighboring points only removing the point if they don't exist. The most extreme example would be the following 3x3 pattern, where the center point is only redundant if it's completely surrounded. Using a 5x5 pattern first instead of 3x3 would make the outer/inner hull as 3 points thick and has no effect being applied after any 3x3 pattern:

17. [[1,1,1],
     [1,1,1],
     [1,1,1]]