A Geometric Constrain t Solv er - Purdue University - geometry calculators and solvers

---

• (1) math calculator geometry
• (2) online geometry calculator
• (3) geometry math calculator math solver
• (4) geometry problem solver

stra
A Geometric Constraint Solver
William Bouma Ioannis Fudosy Christoph Ho mann
Department of Computer Science, Purdue University
West Lafayette, IN 47907-1398
Departmen
Jiazhen Caiz Robert Paigez
t of Computer Science, Courant Institute
251 Mercer Str., New York, NY 10012
Report CSD-TR-93-054x
Abstract
We report on the development of a two-dimensional geometric con-
CAD
int solver. The solver is a major component of a new generation of
resenta
systems that we are developing based on a high-level geometry rep-
and ach
tion. The solver uses a graph-reduction directed algebraic approach,
ieves interactive speed. We describe the architecture of the solver
and its basic capabilities. Then, we discuss in detail how to extend the
scope of the solver, with special emphasis placed on the theoretical and
human factors involved in nding a solution | in an exponentially large
search space | so that the solution is appropriate to the application and
the way of nding it is intuitive to an untrained user.
1 Introduction
Solving a system of geometric constraints is a problem that has been consid-
ered by several communities, and using di erent approaches. For example, the
symbolic computation community has considered the general problem, in the
Supported in part by ONR contract N00014-90-J-1599, by NSF Grant CDA 92-23502, and
by NSF Grant ECD 88-03017.
ySupported by a David Ross fellowship.
zSupported in part by ONR contract N00014-90-J-1890, by AFOSR grant 91-0308, and by
NSF grant MIP 93-00210.
xRevised January 1994. This report and others are available via anonymous ftp to
arthur.cs.purdue.edu, in directory pub cmh and subsidiaries.
context of automatically deriving and proving theorems from analytic geome-
try, and applying these techniques to vision problems; 5, 8, 14 . The geometric
modeling community has considered the problem for the purpose of developing
sketching systems in which a rough sketch, annotated with dimension and con-
straints, is instantiated to satisfy all constraints. This work will be reviewed in
the next section. The applications of this approach are in mechanical engineer-
ing, and, especially, in manufacturing.
purp
With this work, we have mainly manufacturing applications in mind. Our
oses and goals are as follows:
1. We develop a constraint solver in which the information ow between
the user interface and the underlying solver has been formalized by a
high-level representation that is minimally committed to the particular
o
capabilities or technical characteristics of the solver, and is independent
sk
f the interface. Such a representation can become the basis for archiving
sk
etches in a neutral format, with the ability to retrieve the archived
lar
etch and edit it; 13, 12 . Our solution is also a building block for a
an
ger project of developing a new generation of CAD systems based on
and
eutral, high-level geometry representation that expresses design intent
preserves the ability to redesign.
2. We explore the utility of several di erent general-purpose and interoperat-
ing rapid prototyping languages and systems for developing speci c tools
for experimenting conveniently with a variety of ideas and approaches to
constraint solving. Aside from well-known special purpose tools such as
g
LEX and Yacc, our constraint solver also makes use of the high level lan-
tr
uage SETL2 27 to specify complex combinatorial algorithms and the
sy
ansformational system APTS 7, 23 to perform syntactic analysis and
mbolic manipulation of geometrical constraint speci cations.
3. We study a number of neglected aspects of constraint solving. They in-
clude
a redirecting the solver to a di erent solution of a well-constrained
sketch,
b devising generic techniques for extending the capabilities of the solver
while preserving interactive speed, and
c a rigorous correctness proof of the solver.
Note that the correctness proof is reported separately 10 .
This paper reports substantial progress in all three problem dimensions, and
identi es a number of open issues that remain.
2
2 Approaches to Geometric Constraint Solving
We consider only well-constrained, two-dimensional sketches formed from points,
lines, circles, segments and arcs. Constraints are explicit dimensions of distances
and angles, as well as constraints of parallelism, incidence, perpendicularity, tan-
gency, concentricity, collinearity, and prescribed radii. We exclude relations on
dimension variables and inequality constraints. In particular, the user speci es
a rough sketch and adds to it geometric and dimensional constraints that are
normally not yet satis ed by the sketch. The sketch only has to be topologi-
cally correct. The constraint solver determines from the sketch the geometric
elements that are to be found, and processes the constraints to determine each
geometric element such that the constraints are satis ed.
tere
Solving over- and underconstrained sketches is of signi cant practical in-
proa
st. In our experience, solving underconstrained sketches is customarily ap-
metr
ched by adding, as the solution progresses, constraints derived from the
const
ic properties of initial sketch, using ad-hoc rules for the selection of such
solved
raints. We can prove that an underconstrained sketch can be partially
straints
in a unique way, using the given constraints; 10 . However, adding con-
must rely
the
deduced from the metric properties of the user-supplied rough sketch
We als
cons
on a heuristic selection. We explain in Section 5 why this is di cult.
o argue in Section 5 that consistently over-constrained sketches have
attractive property that the number of possible solutions is reduced. In
equence, such constraint problems can unambiguously specify user-intent.
However, nding a solution is intractable even for very simple con gurations,
and more research is needed to devise demonstrably e ective approaches.
proc
se
Our constraint solver is variational. That is, the solver is not obliged to
ess the constraints in a predetermined sequence, and the constraints speci-
ed by the user are not parametric in the sense that they must be determined
og
rially, each as an explicit function of the previous constraints. This is anal-
ous to writing the constraints in a declarative language, where the solution
is independent of the order in which the constraints are written down. This
greatly increases the generality of the constraint solving problem, and demands
solvers that are based on advanced mathematical concepts.
expr
While users of geometric constraint solving systems think geometrically and
inter
ess themselves with visual gestures, constraint solvers work with a di erent
unde
nal representation. Most users will be quite unaware of the nature of the
Coup
rlying representation and of the internal workings of the constraint solver.
in gen
led with the fact that a well-constrained geometric constraint problem has,
intent,
eral, exponentially many solutions, only one of which satis es the user's
constraint solvers therefore have to address two distinct tasks:
1. Determine whether the problem can be solved and if so, how.
2. Among the possible solutions, identify the one the user has intended.
3


• (http://www.cadnexus.com) Appropriate for geometry …
• College Geometry A Problem Solving Approach With
• Density-based Solvers Pressure-based Solvers
• Impact of Using Graphing Calculator in Problem …
• P.O. Box 2120 - Virginia