Skip to main content
Question

Group tiles adjacent to each other up to a certain number


jakethepainter
Contributor
Forum|alt.badge.img+6

I'm trying to find optimal area of interest (AOI) polygons to make request for image tiles. I have my service territory (an irregular shape) tiled and each tile knows how many request would be required as a numeric attribute. What I want to do is group the tiles so that each group has as close to a sum of 150,000 without going over. Then the outline of each group forms a polygon that can be used as an AOI.

The Dissolver just does too much. All the polygons are adjacent.

Or I could have one giant polygon and figure out a way to split it, and if the value (sum) is still too large, split it again.

Ideas?

2 replies

gio
Contributor
Forum|alt.badge.img+15
  • Contributor
  • November 12, 2018

a subset (or subsets) from a superset. If you don't have a huge amount you can do that.

Else you'll need a seeded approach.

There might be more solutions or none. Can't calculate them as it is kind of an non deterministic problem.

Tricky issue and asked a lot.


mark2atsafe
Safer
Forum|alt.badge.img+44
  • Safer
  • November 13, 2018

Well, I looked at what seems to be a similar issue just recently. It is a complex task, and is more complicated depending on the requirements of the final polygon (does it need to be as compact as possible, for example?)

Basically FME has no single transformer intended to carry out this sort of function.

However... the task could be described as a form of "bin packing" or "clustering" (I don't think it's really clustering, but a lot of information on the subject uses that) and if you Google those terms you might find some algorithms that you can replicate in FME, or Python-based scripts that will run in FME.

For example, this paper has some useful information.

What you could try is creating a minimum spanning tree (see this blog post) and from there group together features with a tree connection until the maximum value is reached.

This is something that our developers will looks into shortly, but I don't know what the time frame will be exactly. Almost certainly it won't be FME 2019.


Reply


Cookie policy

We use cookies to enhance and personalize your experience. If you accept you agree to our full cookie policy. Learn more about our cookies.

 
Cookie settings