4

I am trying to split a concave polygon into convex polygons using r. I am trying to figure out how to successfully accomplish this for one polygon with the hopes of implementing this on a large number of polygons in an automated way.

The only way I could think of so far was to use triangulation to break this shape into several smaller shapes, then group those into some minimized number convex polygons. 

library(sp)
library(rgdal)
library(sf)

files <- list.files("~/Cluster polygons 2020",pattern=".shp", full.names=TRUE)
cluster=readOGR(files[1])
spatstat::is.convex(maptools::as.owin.SpatialPolygons(cluster[1,])) #CHECK IF CONVEX
[1] FALSE

enter image description here 

plygn=sfdct::ct_triangulate(sf::st_as_sf(cluster[1,]),D=TRUE)
plygn=st_collection_extract(plygn, "POLYGON")
plygn=as_Spatial(plygn)

length(plygn) #HOW MANY TRIANGLES GENERATED?
[1] 58

enter image description here

This is as far as I have gotten. Is there a clever/principled way group the triangles into the smallest number of groups and then merge them so the final product is a set of convex polygons? Or is there an entirely better approach to this problem?

I appreciate the help. Here is a link to the shapefile

sea83
  • 81
  • 5
  • Is that `.shp` file available for everybody? – r2evans Feb 19 '20 at 01:01
  • I just edited the post so that it's downloadable – sea83 Feb 19 '20 at 06:45
  • Since a convex polygon has no internal corners, another algorithm might be to go round the polygon joining internal corner points and clipping them off, then recursing on the remainder. I can see problems if the clipping cuts across part of the polygon that has looped back inside though... Searching for "concave polygon decomposition" finds a few things. – Spacedman Feb 20 '20 at 10:52
  • Algorithm described as part of this paper seems similar to my idea above but... no code. Might implements it if I get stuck indoors on a wet weekend... https://journals.sagepub.com/doi/full/10.1177/1729881419894787 – Spacedman Feb 20 '20 at 12:04
  • I have now implemented this algorithm in an R package. If you are still interested let me know and I'll post it up somewhere. Best dissection its found so far is into 17 pieces. I'm not sure what the theoretical best is given your shape has 22 internal angles which have to be split... – Spacedman Feb 23 '20 at 12:39
  • Much appreciated, yes please share! I will be very grateful to be able to use your package! – sea83 Feb 24 '20 at 12:34

0 Answers0