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?

closed as off-topic by PolyGeo Sep 10 '17 at 20:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions seeking help to debug/write/improve code must include the desired behavior, a specific problem or error and the shortest code necessary to reproduce it in the question itself. Providing a clear problem statement and evidence of a code attempt will help others to help you. See: How to create a Minimal, Complete, and Verifiable example." – PolyGeo
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    Something like simplify should suffice and can be done with various python libraries. What software do you have access to? – Barbarossa Mar 8 '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 8 '17 at 14:43
  • You can do this in QGIS and R quite easily, might want to update your post to get tailored answers – GISKid Mar 8 '17 at 18:21

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)
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.


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


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


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.


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.

  • 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 9 '17 at 8:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.