So what you are looking for is an implementation of a optimization for bipartite graphs. The most well known algorithm is the Hungarian Algorithm (Kuhn–Munkres algorithm)
There are R packages and python codes available online. Those can be integrated into FME.
That said, I think if you replace your hatch marks with a point at the intersection, and have the labels be your base and the hatch points your candidates, a "waterfall approach" could be effective.
jdh wrote:
So what you are looking for is an implementation of a optimization for bipartite graphs. The most well known algorithm is the Hungarian Algorithm (Kuhn–Munkres algorithm)
There are R packages and python codes available online. Those can be integrated into FME.
That said, I think if you replace your hatch marks with a point at the intersection, and have the labels be your base and the hatch points your candidates, a "waterfall approach" could be effective.
I would create a close candidate list and then drop into python to
A) pair all the labels/hatches that have only one candidate
B) remove the hatches that were paired from
C) pair all the labels/hatches that now have only one candidate
Repeat B/C until all you are left with is labels with multiple candidates
D) pair the overall closest candidate (not the closest for each label)
E) remove that hatch from any other close candidate list.
repeat
until all candidates are paired.
jdh wrote:
I would create a close candidate list and then drop into python to
A) pair all the labels/hatches that have only one candidate
B) remove the hatches that were paired from
C) pair all the labels/hatches that now have only one candidate
Repeat B/C until all you are left with is labels with multiple candidates
D) pair the overall closest candidate (not the closest for each label)
E) remove that hatch from any other close candidate list.
repeat
until all candidates are paired.
Could you briefly elaborate on what you mean with step D? What logic test might you use?
alexandercaudet wrote:
Could you briefly elaborate on what you mean with step D? What logic test might you use?
Once you've eliminated all the "only option" pairs, you will have a set of label features with a '_distance' attribute to the nearest hatch (as well as the list of all hatches within the tolerance). If you sort the features so that the least _distance is first, that first feature should be you next match, and you should remove the corresponding hatch from the remaining label lists.
If removing that hatch causes any other labels to have only one candidate, then start again from A, if they all still have two or more, then take the next smallest distance.
