Splitting an irregular polygon into convex parts

I think what you might need is some itterative process. I think I would first chop the polygon into 2-coördinate lines. A possibility might be to create groups using e.g. a Tiler transformer and create convex features using a HullAccumulator. In a subsequent step you can check whether all lines / vertices have been used and adjust the outcome if necessary.

@Olivier

Multiple loops can be done with multiple custom transformers.

Blocking transformers in a loop requires export of the relevant custom.

Both limitations you mention are not limitations afaik.

Can't open your sample alas.

@olivier

Here is a custom.

How to get to minimal amount of convex objects to describe input object, I have not solved it in this one.

Can't load your posted workspace (to see how you did that)

result after one run of the custom. (all are convex so it stops)

you can call the custom multiple times but have to rebuild the counter in between.

Without (re)Triangulation of course!

Thank you @gio ! I think you solved it. Congratulations! Based on your screenshots (you did not share the workspace but that is fine) I was able to recreate and test it on my data and it works. My tentative workspace was similar in terms of triangulation and deaggregation but the logic inside the custom transformer was somewhat different. Am I right that the Dissolver transformer in your custom transformer is creating a list named "UsedParts" and that this is reused in the ListBasedFeatureMerger as requestor list attribute? I am not sure because the image is a bit blurred.

@Olivier

Hi,

Yes it uses a listbasedfeaturemerger (just an alternative method).

It is meant to release parts which result in concave dissolves and thus need to be processed again.

I will try to upload, often it fails because on the fme server it enters my local path..

I have made some updates. B

Convex_Dissasembler.fmwt

I hope you can upload it. If not, I can always use like some transferring. (or more pics?)

I have not managed to get the custom inside a custom working.

The workspace I uploaded calls the custom couple times to reduce the parts of the end result. Still not 100%, but close:

Thank you @gio. It looks promising. But indeed the end goal is to end up with the largest convex polygons possible. So the two remaining parts of the abdomen should still be dissolved. Same for the remaining parts composing the head. I downloaded your workspace successfully but I am missing the Break2Convex custom transformer.

@olivier

Hi,

I thought it would automaticaly pack the custom.Break2Convex.fmx

The end bits are stubborn. Partly because the relater actually says some of them don't touch. I think I may have to insert some snapping. I'm actually trying it out now.

@olivier

Hi,

Only a remover between calls of the custom was needed. To prevente the spatialpredicatees getting messed up.

Now to find a way to have it do it in a (wrapping) custom.

Now result is 100% after 5 calls.Convex_Dissasembler.fmw

Thanks @gio! This is impressive. Unfortunately I obtain a strange error when trying to download the workspace: "error on line 1 at column 1: Document is empty ". Maybe it needs to be uploaded again or first being zipped. I am curious to look into it and see if it can work with polygons which are more natural or complex (river basins,...).

Olivier

@Olivier

Hi,

Here is latest version.

I managed to do away with the intermediate removers and added testclause in the custom.

(basically using the UsedParts listelementcount (initiated at 0 ))

Still tricky to get it to iterate though.

Yes uploading can be tricky at this forum. Convex_Dissasembler.fmwt

Thank you @gio! It sounds promising. I have the workspace but I would also need your custom transformer named "Break2Convex" for making it work. Could you upload it here? Thanks!

@Olivier

Hi Olivier.

The custom is in the package I uploaded (just above your post). I just checked. It has 2 subfolders, the custom is in the "transformers" map.

hdocumentsfmetransformersconvex-dissasembler.fmwt

@gio: Perfect! Sorry for that. I had not unzipped the package. I now have all I need. :-)

@Olivier

Hi,

I tried it on random geometries, and it works.

I only need to manage to get it to iterate, as it is unknown how many passes are needed.

I'll let you know as soon as I got it (unless you manage to do it before, in which case you could post it for us)

Success!

Greets,

Gio

Thank you @gio! Making it iterate is indeed the main issue which I didn't crack yet. Maybe if I learn some Python I would be able to do something about it. The purpose would be to have the flow iterate as many a number of times as required. Some complex real-life polygons may require hundreds of iterations or even more probably (think of large complex water basins with lots of branches). I am adding a slightly more complex input polygon for reference.Input_polygon.zip

@Olivier

Hi Olivier,

I managed to get it into a loop.

And I managed to loop that as well, but..

I have not managed to get it to run to some minimum. It runs some iterations, but ends not at the known minimum, so still some fiddling to do there.. (I have not included my most recent attempt ).

Basically I shift the starting edge and run it again, test if it I smaller or not etc.. It ends at 12 parts..which is not good as it should be 7. So its still WIP.

But you might get inspired to find it.Convex_Dissasembler_SFSG.fmwt

Greets,

Gio

Hi.

I was reviewing my workbenches and came along this one.

Took me like 5 mins now to make the iteration to work!

Here is the complete workspace.

If you might still be interested in the soltuion.

Works on large ones (many vertices) too...but be prepared to be patient of course.

Greets and stay healthy!

Gio

Hi @gio​ !

Thanks for looking into this again! I really appreciate. I just tested it using the sample figure and obtained this:

Do you know how to get rid of the redundant edges? I got the above result after changing the B2B max iteration parameter to 150. With 20 I was getting even more triangles. Actually it seems that the greatest convex polygons are produced but they are on top of (or underneath) smaller ones.

All the best!

Olivier

@olivier​ 

I downloaded the package which i just uploaded and ran the main workbench(with no change in settings) Convex_Dissasembler_final.fmw.

And it gives the correct 7 polygnon figure.

I also increased the B2B maxiteration and funnily it runs in 46 sec at max. 40 and 50 sec at max. 150 (interesting: I need to study that behaviour)

WHilst at 20 it runs over a minute!

Version used:

FME(R) 2018.0.0.2 (20180414 - Build 18301 - WIN64)

Thank you very much @gio​ ! And sorry for the late reply as I was out of the office for a while...

I unzipped the package, copied the two custom fmx transformers into FME's transformers folder, then ran Convex_Dissasembler_final.fmw. It resulted in the expected set of 7 polygons. I am very happy to see that FME can solve this sort of spatial challenge.