Is there a programatic method to simplify a polygon?

Question

I have an array, containing lat/lon coordinates which form a polygon(the boundaries of certain cities on the map). I got this data from OpenStreetMap's database, and my problem is what follows:

Certain location boundaries, are formed by 5-6000+ lat/lon coordinates, which is a very large data for me to work with. In the meanwhile, I've observed that a lot of these polygons could be trimmed down to contain a fewer points, because a lot of lat/lon coordinates are placed on the same line.

What I would be interested in, is if it would be possible, to get a polygon, and programatically check if multiple points of it reside on the same line(with a small error margin), and delete unneeded(in my case) points, thus so minifying the polygon itself?

Something like simplify should suffice and can be done with various python libraries. What software do you have access to? — Barbarossa, Mar 08 '17 at 14:41
A start could be postgres database? Maybe a too big step, hence st_buffer and st_makeline could be useful parts in a solution. — axel_ande, Mar 08 '17 at 14:43
You can do this in QGIS and R quite easily, might want to update your post to get tailored answers — GISHuman, Mar 08 '17 at 18:21

score 3 · Accepted Answer · edited Apr 13 '17 at 12:34

I've edited my answer for things to try in various programs. If you try one of these methods and it doesn't give the results you need, I would update your question with additional images/details.

Open source/Free solutions

In R:

library (rgeos)
library(rgdal)
setwd("C://Folder")
shp <- readOGR(".","myshapefile")
shp2<-gSimplify(shp,tol=0.01, topologyPreserve=TRUE)
simplified<-SpatialPolygonsDataFrame(shp2, data=shp@data)

You can change the tolerance from 0.01 to whatever value gives you the desired result, since gSimplify only simplifies the geometry, you then have to join back the attributes to the polygon.

In QGIS:

Explained in this GIS SE post - similar method to above, but a built in tool in QGIS. There is also this plugin Simpliply which could aid you

PostGIS:

Again, another tool called ST_Simplify. This may be the easiest if you have A LOT of nodes. PostGIS can typically handle larger datasets.

Proprietary

ArcGIS If you have access to ArcGIS you can use the "Simplify Polygon" tool this would remove the extra nodes you are speaking of, while preserving the general shape.

score 2 · Answer 2 · answered Mar 08 '17 at 16:52

2

Without knowing what software you might have access to - and assuming you'll program your own solution - the Douglas-Peuker algorithm is probably a good place to start.

That link is to a Wikipedia page, which has further links to code samples in C++, Java, etc.

Whether that's the best solution I don't know, but it's the one that comes to mind first.

answered Mar 08 '17 at 16:52

Mark Ireland

13,147
3
33
67

1

I agree Douglas-Peuker is probably what the OP wants given the requirements in the question, but the Wang-Müller algorithm may be worth a look too. – MappaGnosis Mar 09 '17 at 08:34

Is there a programatic method to simplify a polygon?

2 Answers2