Question

Group tiles adjacent to each other up to a certain number

  • 12 November 2018
  • 2 replies
  • 4 views
jakethepainter
Rank
Badge +5

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

G
Badge +3

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
Rank
Userlevel 4
Badge +25

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


Community Stats

28,743
Posts
109,582
Replies
36,583
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.