21

I'm looking for a tool or algorithm to detect concave polygons and split them into convex polygons. Like explained in the picture, the blue polygon is split into A and B polygons

I'm using Arcpy under Arcgis 10.1

split polygons

PolyGeo
  • 65,136
  • 29
  • 109
  • 338
geogeek
  • 4,566
  • 5
  • 35
  • 79
  • 15
    Perhaps you could elaborate on why you are doing this? After all, (a) detection is easy: a concave polygon will have less area than its convex hull; and (b) any triangulation of a polygon automatically splits it into convex polygons, because all triangles are convex. This shows you have some flexibility in choosing among the many possible solutions. – whuber Oct 05 '12 at 12:42
  • 2
    This toolset will enable you to see what Bill is talking about http://resources.arcgis.com/gallery/file/geoprocessing/details?entryID=1E56696E-1422-2418-3462-F19FDA7E8B86 convert the polygon to points then run the Delaunay option –  Oct 05 '12 at 14:02
  • I have been convinced to just detect very concave polygons, by getting their centroid, then get the polygons having their centroid outside. – geogeek Oct 06 '12 at 10:25
  • Not sure how flexible you are with your result but aside from full triangulation as @whuber mentioned you can get close with monotone polygons. The algorithm I implemented in the past would give the result in your photo although convex is not guaranteed. Also those algorithms are relatively easy to implement. – Dandy Oct 23 '12 at 19:09
  • geogeek, your suggested solution is really hit-or-miss. Surely an external centroid identifies a concave polygon, but many extremely tortuous polygons have their centroids within their interiors. The area-comparison method I suggested is accurate (although conceivably it could miss polygons which are concave due to extremely thin internal slivers). But the hard part of the problem is the dissection once a concave polygon is found. – whuber Oct 23 '12 at 19:16
  • @whuber your suggested solution is the best, the problem remains in the dissection, i suggest that once the concave polygon found with your algorithm, we have to find its centroid, then split the polygon by the line passing by the two nearest points to the centroid, these points must not be adjacent. this two algorithms could be coupled in recursive one, so every polygon will be detected then split until not detected as concave polygon. – geogeek Oct 23 '12 at 21:00
  • Thanks for the explanation. It would be interesting to compare a recursive splitting solution to one that builds up convex pieces from a triangulation. The splitting might often be more efficient, but the synthetic one won't run into trouble with highly tortuous polygons (think of mazes, for instance). – whuber Oct 23 '12 at 21:03
  • triangulation based algorithm, need a combination step, so the combination could be done randomly, with each triangle added to the polygon we should check if the polygon is still convex. yeah this algo is more efficient. – geogeek Oct 23 '12 at 21:09
  • 1
    There is an answer to this over on Stack Overflow: http://stackoverflow.com/a/6686842/1300519 The algorithms described shouldn't be too difficult to write using arcpy. – Snorfalorpagus Dec 23 '12 at 16:47
  • 1
    @snorf That appears to answer a slightly, but importantly, different question. The solution apparently involves a combination of "polygons" and "holes", which is not what is usually meant by "splitting". At the least, that answer needs further elaboration to be useful here. (BTW, your answer was changed to a comment because cross-references to other solutions elsewhere on the Web, without any additional explanation, are not considered answers here on SE.) – whuber Dec 23 '12 at 21:58
  • 2
    Judging from the comments here and no answers arising, my recommendation would be to edit your question to incorporate that feedback and consider offering a bounty. – PolyGeo Jul 25 '13 at 02:23
  • Hi, I found two threads that talk about splitting concave polys into convex ones. This one on forums.esri.com but it is VBA script and this sample but this is in java. – GeoStoneMarten Dec 16 '13 at 20:32

1 Answers1

1

here are a few steps to identify the vertices from the concave parts :

with parcel: minimum bounding geometry (hull) -> parcelHull

with parcel: FeatureVerticesToPoint -> parcelPoints

with parcelHull : FeatureVerticesToPoint -> parcelHullPoints

with parcelPoint and parcelHullPoint : symmetrical Diff -> concavePoints

based on those points, you can either draw the bissectrice to cut your polygon (bearing distance to line), select the edges of the Voronoï triangle that intersect your point but are not sharing a segment with your parcel boundary (select by location after splitting triangle lines at vertices), select the vertex on the opposite site and make a line (points to line), select the closest point on the opposite edge and make a line (points to line)...

At the end, use your preferred lines and the original parcels with "feature to polygon" to split the polygons.

radouxju
  • 49,636
  • 2
  • 71
  • 144