Module arc_acreage::slow

The original implementation of a backtracking search algorithm to generate closed curves of a desired area.

This algorithm builds fully general curves built out of quarter-circle arc segments, and can therefore represent any closed curve as defined in the problem. However, the search function has a large branching factor, since at each step in building out a curve, we can generally transition to any of the 3 adjacent cells, and each of these could have either of two quarter-circle arc segments in it (depending on which way the segment curves). So we usually have a branching factor of 6 at each step, and the algorithm can take a long time to terminate.

To help with narrowing the search space, we have included some constraints. It is possible to request the search to ignore curves which have too many segments not on the outer rim of the grid, and also curves above a threshold length. If we can prove constraints that curves of our desired area must obey, then we can use these to reduce the search space.

Structs

• Area
• Generator
  A data structure for generating closed loops of a target area, using a back-tracking algorithm.
• Grid

Enums

• AreaError
  An error returned when attempting to calculate the area enclosed by a loop in a Grid.
• Cell
  A cell in the grid.