Learning to Solve Geometric Construction Problems from Images

Jaroslav Macke, Jirí Sedlár, Miroslav Olsák, Josef Urban, Josef Sivic

Abstract

Traditional geometry solvers rely on symbolic logic and formal proofs, differing significantly from the visual, intuitive approach humans take. This paper presents a purely image-based AI agent that solves ruler-and-compass construction problems from the game Euclidea. By integrating a modified Mask R-CNN architecture with a tree-based search, the system achieves 92% accuracy on known problems and demonstrates remarkable generalization to unseen geometric challenges without requiring formal algebraic inputs.

Introduction: The Visual Challenge of Geometry

Automated geometry solving has historically been the domain of symbolic logic and algebraic methods like Wu’s method. However, these systems do not replicate the human experience of "seeing" a solution within a diagram. A purely visual approach faces significant hurdles: the infinite variability of diagrams (scale, rotation, position) and a massive search space where a multi-step construction can lead to billions of possible states.

Example of a geometric construction task from input to completion.

The authors address these challenges by creating a solver that operates directly on pixels, using computer vision to guide sequential construction steps.

Methodology

The proposed system, "Learning to Solve Geometric Construction Problems from Images," utilizes two primary components: a specialized neural network for perception and a search algorithm for reasoning.

Adapted Mask R-CNN for Geometric Perception

The core of the perception system is a modified Mask R-CNN. Unlike standard object detection, this model processes a three-channel RGB image:

  • Red Channel: Current construction state.
  • Green Channel: The target goal.
  • Blue Channel: History of previous states to provide temporal context.

The model performs two levels of detection. Primary detection identifies the appropriate geometric tool (e.g., Compass, Perpendicular Bisector), while secondary detection predicts the specific "click points" or coordinates required for that tool.

Overview of the image-to-action pipeline using Mask R-CNN.

To compensate for perceptual uncertainties, the agent employs an Iterative Deepening Depth-First Search (ID-DFS). This allows the system to explore a tree of possible construction steps rather than relying solely on the highest-probability prediction. A reward system assigns positive scores to steps that align with the goal (green) lines, effectively guiding the search toward a valid solution.

Training and Precision

To ensure mathematical accuracy, the model incorporates "snapping" to intersections. Training is conducted in four stages, gradually unfreezing the neural network backbone. Additionally, synthetic data generation includes "intersection degeneration rules" to filter out ambiguous cases where points are too close to distinguish.

Datasets and Experimental Results

The agent was benchmarked using the first six level packs of the game Euclidea, covering 68 distinct problem types. Thousands of random variations were synthetically generated for each level to ensure the model learned general geometric concepts rather than specific image patterns.

Key Findings

  • High Accuracy: The supervised agent solved all 68 level types with an average accuracy of 92%.
  • Generalization: In "zero-shot" testing on entirely unseen levels, the agent successfully solved 31 out of 68 problems, suggesting it learned reusable geometric "sub-routines."
  • Search as a Buffer: Ablation studies showed that a "Vanilla" Mask R-CNN failed on complex levels (0% success on harder packs), whereas the addition of the tree search and history channel enabled high performance.

Conclusion and Future Work

This research demonstrates that high-level geometric reasoning can emerge from pure visual perception. While the current system excels at synthetic images, future work aims to improve search efficiency for deeper constructions (10+ steps) and transition to processing hand-drawn sketches or textbook diagrams. Furthermore, applying Reinforcement Learning could enable the discovery of novel, more efficient construction paths beyond those found in human-provided training data.

Summary updated

BibTeX
@inproceedings{macke2021learning,
  author = {Jaroslav Macke and Jirí Sedlár and Miroslav Olsák and Josef Urban and Josef Sivic},
  title = {{Learning to Solve Geometric Construction Problems from Images}},
  booktitle = {CICM},
  year = {2021},
  doi = {10.1007/978-3-030-81097-9\_14},
}
Figure