Module arc_acreage::fast
source · Expand description
A faster implementation of the backtracking search algorithm to generate curves of a desired area.
This algorithm is only capable of generating curves of integer area. The search space is dramatically reduced by treating quarter circle arcs as straight line diagonal segments. Now, there are only two possible loop segments at each point along the loop, rather than the four possibilities when using curved quarter circle arcs. This reduces the branching factor in the search algorithm from 6 to 3. Each time we find a valid loop, it contributes (2n choose n) possibilities to the total count of closed curves built out of quarter circle segments (where 2n is the total path length). Each straight line segment in the configuration this algorithm discovers can maintain the same integer area when translated to the space of quarter-circle if and only half of the segments are converted to contributors of ‘1-π/4’ area, and the other half are converted to contributors of ‘π/4’ area.
This algorithm is so much faster than the original version that we can afford to completely relax the search constraints and it will still produce the result in under a second. This gives us even more confidence in the accuracy of our answer.
Structs
- Representation of an area enclosed by a closed curve in the grid.
- A data structure for generating closed loops of a target area, using a back-tracking algorithm.
- A 7x7 grid, containing empty cells and curve segments.
Enums
- An error returned when attempting to calculate the area enclosed by a loop in a
Grid. - A cell in the grid.
Functions
- Returns the value of 2n choose n, the central binomial coefficient. Implemented as const lookup table for speed and ease.