Matching

A Matching pairs two sets element by element at the least total cost: every element of the smaller set gets one partner in the other, no two share a partner, and the costs of the pairs add up to the smallest sum any such pairing can have. This is the assignment problem. With distance as the cost, a cloud of particles sent to the points of a shape this way travels the least in total, and no two of their paths cross. With a cost of your own, two palettes match color to color, or a set of pieces matches a set of holes by size.

Contents

• Quick start
• A cost of your own
• Reading the pairing
• Greedy, for comparison
• Cost and size
• Reference

Quick start

var particles: [Vector2] = []
var targets: [Vector2] = []
var match = Matching.optimal([Vector2](), [Vector2]())

override func setup() {
    particles = (0 ..< 800).map { _ in randomVector(in: canvasRectangle) }
    targets = textToShapes("HELLO", at: center).flatMap { randomPoints(in: $0, count: 160) }
    match = Matching.optimal(particles, targets)      // the cost is the distance
}

override func draw() {
    background(.black)
    fill(.white)
    for pair in match.pairs {
        particles[pair.first] = particles[pair.first].lerp(to: targets[pair.second], 0.04)
        drawCircle(center: particles[pair.first], radius: 3)
    }
}

Each pair names an index into the first set and an index into the second. The sketch keeps the sets themselves, and the matching only says who goes with whom.

A cost of your own

The point forms use the distance. The general form takes any two arrays and a closure that prices one element against one of the other:

let swatches: [Color] = [.red, .orange, .yellow]
let wanted: [Color] = [.blue, .green, .gray]
let byLook = Matching.optimal(swatches, wanted) { $0.distance(to: $1) }

let pieces: [Double] = [12, 30, 7, 22]        // radii
let holes: [Double] = [8, 31, 11, 20, 28]
let bySize = Matching.optimal(pieces, holes) { abs($0 - $1) }

A cost that is infinite, or not a number, forbids the pair: those two are never paired. The matching then pairs as many elements as the allowed pairs permit, at the least total cost among those pairings, and an element with no allowed partner is left out, so partner(of:) answers nil for it. That is how a sketch keeps particles out of a region or colors out of a group with one line in the closure:

let dots: [Vector2] = []
let spots: [Vector2] = []
let keepLeft = Matching.optimal(dots, spots) { dot, spot in
    spot.x > width / 2 ? .infinity : dot.distance(to: spot)
}

A table of costs works too, one row per element of the first set and one column per element of the second: Matching.optimal(costs:). A short row forbids the pairs past its end.

Reading the pairing

• pairs lists every pair made, ascending by first.
• partner(of:) answers the second set's index for an element of the first, or nil when it has none.
• totalCost is the sum over the pairs.
• reversed() is the same pairing read from the other side, so partner(of:) then answers for the second set's elements.

When the sets differ in size, every element of the smaller set is paired and the rest of the larger one is left out. Two hundred particles and fifty targets pair fifty particles; the other hundred and fifty answer nil to partner(of:) and are the sketch's to scatter, dim, or hold still.

Greedy, for comparison

Matching.greedy pairs the sets by the rule a first draft usually writes: each element of the first set, in turn, takes the cheapest partner still free. It is fast and it is a proper pairing, and its total is often well above the least, because the first few choices take the partners the later ones needed. With distance as the cost its paths cross each other, and the flight of a cloud paired this way reads as a tangle where the optimal one reads as a single motion. The worked example switches between the two with one key so the difference can be watched.

Cost and size

optimal finds the pairing exactly, by the shortest-augmenting-path method of Jonker and Volgenant. Its work grows with about the cube of the count, and it holds the cost of every pair in memory while it runs (the two counts multiplied, as numbers). In a release build a thousand on a side pairs in about sixty milliseconds, two thousand in a third of a second, and three thousand in under a second with seventy megabytes held for the table. Find the pairing once when the sets are set, not every frame: a cloud that gathers into a word matches once at the start of the flight and then moves along fixed roads.

Among pairings that share the least total, the one answered is fixed, so a seeded sketch reproduces.

Reference

Runnable: Examples/Patterns/GatherIntoLetters, a cloud of dots flying from one word into the next along the roads the least total gives, with the greedy pairing a key away.

See also Spatial index for the nearest-neighbor questions, which answer "who is close" rather than "who goes with whom", and Shape morphing for tweening one outline into another rather than one set of points into another.