Question

Xavier Fischer on Wed, 09 Mar 2011 09:13:16


Good morning,

I am facing a problem when displaying polygon shapes in a mapping application.

For performance and bandwitdh purposes, I simplify polygons by calling Reduce() on geography instances, passing my screen resolution as tolerance parameter. This perfectly fits my needs for a given zoom level. Shapes seems preserved and unaccurate points are removed by Reduce() algorithm.

Now, I want to avoid retrieving the whole set of polygons for every zoom level and need to reduce them one time at a fixed tolerance , but the problem is that polygons that where touching themselves are not anymore after a call to Reduce(). ie: when I zoom in, polygons crosses and holes appears)

Is there any way or enhancement that can simplify polygons WHILE preserving their common boundary topology ?

Here is a picture :

By "preserving topology" I mean :

- if a polygon A has a common boundary with polygon B, if a point of that specific boundary is removed from A, it should be removed from B. All points unchanged after reduction should be on A and B.

ps: oh I know that should be hard to do, because the very instance of a polygon is not sufficient to perform this, as the algorithm should care about intersection and boundaries with other shapes.

Thank you ! I hope you will help me.


Sponsored



Replies

tanoshimi on Wed, 09 Mar 2011 12:43:18


Strange that you're the second person who I've seen ask this this morning... must be something in the air.

Unfortunately, as far as I know, there is no easy way to do this (not using native functions from within SQL Server, at least). You've already summarised the problems well - Reduce() works on each polygon in isolation and has no consideration for the overall topology of your data - it is a purely geometric function.

The approach that you'd need to take would be instead to break apart your polygon data into a set of edges - each edge representing a common boundary between two shapes (or, for those polygons that are on the "outside" of your dataset, it would be their exterior boundary). You also need to maintain an index of the edges from which each polygon is formed.

Then, you Reduce() each edge separately (not each Polygon). And finally, you reconstruct the polygons from the corresponding simplified edges to those from which they were originally built.

You could certainly do this in SQL Server using a custom SQLCLR procedure, but it would be hard to make it efficient. Perhaps something to add to the SqlSpatialTools project on codeplex? :)

Xavier Fischer on Wed, 09 Mar 2011 13:45:35


Thanks tanomishi for the quick and accurate answer. You understood my needs, and gave me very good clues to handle that on a geometric point of view.

Well you can be sure that if I had time to do this, I would put it into SqlSpatialTools that I am already using (aggregates and vacuousgeomtogeog... great stuff !!)

The hardest point is to detect edges that are most often not "equal" from one polygon to the touching other : small differences exists.

That could be done with a STDistance() test on all points with a certain tolerance that may be proportional to polygon extents.

I promess to share that or whatever workaround when I'll be done with my duty tasks.

Thanks

 

Spatial Ed on Wed, 09 Mar 2011 14:18:48


This is an oft asked for feature. If you have access to Safe Software's Feature Manipulation Engine (FME), a solution can be fashioned to solve this issue (i.e. I'd be happy to send you the workflow). You should also take a look at TopologyLite on CodePlex: http://topologylite.codeplex.com/. Lastly, products like Esri's ArcGIS can also solve this problem within the context of a SQL Server spatial data.

Thanks,

-Ed


Ed Katibah Spatial Ed Blog

tanoshimi on Wed, 09 Mar 2011 14:26:24


Oooh - thanks for the link to TopologyLite, Ed - I'd not heard of that project before. If its homepage is correct, it includes "Classes for performing gap-free simplification of a collection of SQL Server Spatial geometry" - which pretty much exactly fits the bill.

Now downloading - if I get it to work, I might feel a blog post coming on later....

Xavier Fischer on Wed, 09 Mar 2011 14:50:03


Thanks Ed for the link. I do not have access to FME. I Will test this.

My final objective is to speed up rendering vector tiles on silverlight (using deepEarth control). Drawing is fast, the only drawback is the bandwith used by wcf calls to Sql Server.

Reducing polygons is an efficient way to minimize client side latency, but the best would be

  1. having simplified polygons layers on server side (I've never been so closed to achieve this thanks to you Ed and tanomishi)
  2. reducing polygons on the fly in Silverlight code : that is hard, but a NetTopologySuite silverlight port would do the job, deepearth one is not working)

I'll let you know how things go with 1 asap.

 

tanoshimi on Wed, 09 Mar 2011 15:19:20


It seems that the topologylite project might need a little bit of love to get it working... the VS solution file seems to have a few broken file references (though these can apparently be deleted without any ill-effect), and there are some references to assemblies that either aren't present (quickgraph - a separate codeplex project), or that aren't on the "safe list" for SQL Server (System.Drawing)....so, you can't just click "Deploy" and expect it to work...

However, I think there's definitely something in there that's worth investigating some more - just don't expect it to be a 5 minute job!

clement_911 on Thu, 15 Sep 2011 01:21:23


Has anyone got it working ?

I'm getting an exception when calling Simplifier.Simplify(geoMetries, tolerance).

24306: The Polygon input is not valid because the start and end points of the ring are not the same. Each ring of a polygon must have the same start and end points.

 

Also some Debug.Assert are failing...

Definitely not as simple as I was wishing for...

JGallagher on Sat, 19 May 2012 21:37:00


Ditto the above question, anyone managed to get this VS project to work? From its documentation , it looks perfect for what I'm trying to achieve, just need to get it working now! :)

Xavier Fischer on Sat, 19 May 2012 21:55:14


I did not tried, but NetTopologySuite has a topoly preserving simplifier in the V1.X trunk : http://code.google.com/p/nettopologysuite/

There are a bunch of developers active on this project and may help you.

Bora Beran, MSFT on Mon, 05 Nov 2012 07:21:46


I posted some code on my blog that should help with this problem. I got a few comments suggesting I should write about it here.

http://boraberan.wordpress.com/2012/10/23/simplifying-multiple-neighboring-polygons/

This is something I put together in a couple of hours in my free time. So no guarantees, use it at your own risk. But source code (C#) is there, so you can judge for yourself and modify as you please.