Sketch-based pruning of a solution space within a formal geometric constraint solver

DOI10.1016/S0004-3702(00)00061-8MaRDI QIDQ1589579zbMATH OpenFDO

Authors C. Essert-Villard, Pascal Schreck, Jean-François Dufourd

Publication date 12 December 2000

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0004-3702(00)00061-8

zbMATH Keywords

computer-aided designformal geometric constructionssymbolic constraint solvingtree pruning

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computer science aspects of computer-aided design (68U07)

Review text

In CAD systems, formal geometric solvers enable the designer to draw a sketch and to provide constraints that are compiled into a construction plan by symbolic geometric reasoning. Then the plan is interpreted in order to generate the required figure. In case there are multiple solutions, they allow to scan the entire solution space. But when the number of solutions becomes too high, it is very time-consuming to examine each of them to determine which one is the closest to the user's will. In this paper, we introduce a sketch-based heuristic that enables to easily eliminate most of the solutions and to keep, among a solution space represented by a tree, only one branch, or at the worst a small subtree of solutions, that has the best likeness with the original sketch.

Recommendations

• scientific article; zbMATH DE number 1149429
• A formalization of geometric constraint systems and their decomposition
• Combinatorial approaches to geometrie constraint solving: problems, progress, and directions
• A 2D geometric constraint solver using a graph reduction method
• Geometric constraint satisfaction using optimization methods.
• Locating geometric primitives by pruning the parameter space

Cites work

• Boosting complete techniques thanks to local search methods
• Geometric constraint satisfaction using optimization methods.
• Geometric constraint solver
• Geometric construction by assembling solved subfigures
• Higher order rule characterization of heuristics of compass and straight edge constructions in geometry
• scientific article; zbMATH DE number 4072432 (Why is no real title available?)
• scientific article; zbMATH DE number 767435 (Why is no real title available?)
• Modular algebraic specification of some basic geometrical constructions

Cited in

(9)

• Searching the solution space in constructive geometric constraint solving with genetic algorithms
• Towards a better integration of modelers and black box constraint solvers within the product design process
• DECOMPOSITION OF GEOMETRIC CONSTRAINT SYSTEMS: A SURVEY
• GPDOF — A FAST ALGORITHM TO DECOMPOSE UNDER-CONSTRAINED GEOMETRIC CONSTRAINT SYSTEMS: APPLICATION TO 3D MODELING
• Computer theorem proving for verifiable solving of geometric construction problems
• scientific article; zbMATH DE number 558488 (Why is no real title available?)
• scientific article; zbMATH DE number 1787161 (Why is no real title available?)
• scientific article; zbMATH DE number 2087076 (Why is no real title available?)
• AN EFFICIENT METHOD TO DETERMINE THE INTENDED SOLUTION FOR A SYSTEM OF GEOMETRIC CONSTRAINTS

Describes a project that uses

Uses Software

• Cabri

This page was built for publication: Sketch-based pruning of a solution space within a formal geometric constraint solver

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1589579)