Group points on a plane into 3 dice

user_4514496 0
Viewed 76

I have a (top-down) image of a roll of 3 (6-sided) dice from which I've extracted the coordinates of the dots, leaving me with 3..18 points.

How can I find what was rolled on the dice, or in other words, which points group together to form a die?

So far, I've simplified it into a problem of finding 3 circles so that each point lies in exactly one circle, and the size of the largest circle is minimized.

I have thought of 2 possible approaches to this, but both are just barely too slow.

Approach 1:
Find all possible triplets of disjoint point sets and the smallest bounding circle on each. Discard any solution where a circle contains points other than those in its set, or if a circle is larger than the largest circle in the best solution already found.

Approach 2: Find all possible triplets of circles (as defined by 1-3 of the points). Discard any solution which contains a circle containing more than 6 points, points already in other circles, a circle that is larger than the largest circle in the best solution already found, or a solution which doesn't encircle every point.

Is there any more efficient algorithm for solving this, as I've only managed to think of mostly brute-force solutions? I need a worst-case time of about 1s, and ideally an average time of up to 10ms.

computational-geometry algorithm
1 Answers

In the worst case with 18 pips, there are at most

>>> sum(math.comb(18, i) for i in range(1, 7))
31179

possible subsets of between 1 and 6 pips. Discard all of these whose smallest enclosing circle (use Emo Welzl's randomized algorithm) encloses a pip not in the subset. Using the Sauer–Shelah lemma and the fact that the VC dimension of disks is 3, we observe that the number of subsets remaining is at most

>>> sum(math.comb(18, i) for i in range(4))
988

(EDIT: actually we can just try the disks generated by triplets of points, disks generated by pairs of points, and individual points.) Now we look for three pairwise disjoint subsets whose union is everything. This is accomplished efficiently by indexing the subsets by bitmap, looping over pairs of subsets and testing 1) whether those subsets are disjoint 2) whether the complement of their union is also a subset.

I'm quite sure this can be made to run in 10 ms worst case if you're using a decent compiler.

user_21446690
Related