I have a polygon with an arbitrary shape ( assume that it is well-formed with no self intersection, no duplicated points etc), and I need to subdivide the polygon into sub-polygons like how one would define roof on top of a building. How can I do that in any GIS software, or through any open source libraries, or through any algorithm?

The reason why I'm asking this is because for my flat terrain ( with 2D shape unknown obviously), I have to manually enforce artificial gradients at appropriate places, so that the water can flow to the neighboring cells correctly when I am applying D8 implementation to calculate the flow accumulation. So the most intuitive places for sub-division would be the places where roof lines are taking along.

I would be interested to know is there any algorithm that one can use for this, and also is there any C++ open source libraries implementation for this ( I don't want to reinvent the wheel); is GDAL or CGAL or any geometrical algorithm already has this implementation?

  • "Like how one would define roof on top of a building" is rather vague. Can you edit your question to include a definition, or perhaps some illustration, of what you mean here? – csk Jun 18 '18 at 16:59
  • @csk, no I can't define it precisely, but there is no need for me to do so; I've explained why I need such a roof line method further into the question. – Graviton Jun 19 '18 at 1:49

I think what you're asking for is skeletonisation

See Wikipedia on straight skeleton and topological skeleton

This will give the effect of a sloping roof, even on irregular shaped polygons (I'm not sure how well it works with donuts e.g. atriums). It's based on voronoi meshes.

I haven't tried it myself, but grass has an algorithm called v.voronoi with the -s option to produce skeletons, although it only appears to work with point layers. SAGA has a similar module but for rasters.

see also this question for other options (e.g. i think postgis sf-gcal extension can do this)


You may want to check out this thread. It's a method for deriving the centerline of polygons, and to me the product does look like rooftops.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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