Solved

Splitting an irregular polygon into convex parts

olivier
Rank
Badge +6

Hi,

Which combination of FME transformers would I need to use for splitting an irregular polygon into convex partitions (and possibly also minimizing the number of resulting parts). The following figure illustrates what I am trying to obtain:

I have come up with an approach based on the Triangulator which can be described as follows:

  1. Sorting all interior lines from the triangulation by decreasing length
  2. Consider the first occurrence
  3. Identify the 2 adjacent polygons
  4. Dissolve those 2 polygons
  5. Check convexity of result
    1. If convex, keep result
    2. If concave, discard result
  6. The process should for instance escape the loop when all interior lines have been considered

I created an FME workspace which does this.

The initial figure:

would become like this after triangulation:

And ultimately the end result would be the following where all parts are convex:

However the iterations are hard-coded for the moment because the custom transformer I tried to create contains blocking transformers and multiple loops which are not supported. My question is: how would you make the attached FME workspace generic so that it can work with any number of interior edges?

Thank you!

Best regards,

Olivier

icon

Best answer by gio 6 August 2020, 10:29

View original

24 replies

lars_de_vries
Badge +10

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
Rank
Badge +6

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.

Thank you for your suggestion @lars_de_vries !

 

However I have difficulties picturing the approach you describe. I can indeed create 2-coordinate lines from the polygon outline (Chopper set on max vertices = 2). This leads me to a set of lines outlining the same shape. Then I don't see how you are decomposing/splitting the irregular polygon.

 

lars_de_vries
Badge +10
Thank you for your suggestion @lars_de_vries !

 

However I have difficulties picturing the approach you describe. I can indeed create 2-coordinate lines from the polygon outline (Chopper set on max vertices = 2). This leads me to a set of lines outlining the same shape. Then I don't see how you are decomposing/splitting the irregular polygon.

 

If you use a Tiler transformer on the dataset, you can divide the total geometry in equal tiles. Next you can check which lines/vertices are within a tile and create a fictional group. Using these groups you can create convex hulls using the HullAccumulator. You might miss some features in the result, but you can solve that by Clipping the original feature(s) with the result.

 

G
Badge +3

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

G
Badge +3

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

G
Badge +3

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

Without (re)Triangulation of course!

olivier
Rank
Badge +6

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

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.

G
Badge +3

@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:

olivier
Rank
Badge +6

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

G
Badge +3

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

 

 

G
Badge +3

@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

 

b2c-final-resultpng

olivier
Rank
Badge +6

@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

 

b2c-final-resultpng

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

G
Badge +3

@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

 

b2c-final-resultpng

@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

olivier
Rank
Badge +6

@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!

G
Badge +3

@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

olivier
Rank
Badge +6

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

G
Badge +3

@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

olivier
Rank
Badge +6

@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

G
Badge +3

@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

G
Badge +3

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

 

olivier
Rank
Badge +6

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:

Figure_simple

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

G
Badge +3

Hi @gio​ !

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

Figure_simple

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

CC_out_finalHi @olivier​ 

 

I repacked it. I might have packed wrong versions of the sub-customs, i removed them all and kept the actual ones).

with the settings in the workspace it runs to following picture.

 

When i run the worskpace i packed it results in following.

You need to run Convex_Dissasembler_final.fmw

stats:

Translation was SUCCESSFUL with 0 warning(s) (0 feature(s) output)FME Session Duration: 1 minute 24.0 seconds. (CPU: 9.3s user, 15.3s system)

END - ProcessID: 13468, peak process memory usage: 125876 kB, current process memory usage: 119408 kB

Translation was SUCCESSFUL

 

 

No need to change settings.

Results in 7 polygons.

It should be the 6/08/2020 version.

 

 

G
Badge +3

Hi @gio​ !

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

Figure_simple

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)

 

olivier
Rank
Badge +6

Hi @gio​ !

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

Figure_simple

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

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.

Reply


Community Stats

28,692
Posts
109,433
Replies
36,544
Members
Terms & ConditionsCookie settings
A product of
Safe Software respectfully acknowledges that we live, learn and work on the traditional and unceded territories of the Kwantlen, Katzie, and Semiahmoo First Nations.