Re: [eclipse-users] geometry and constraint programming

A few weeks ago, Malcolm Ryan wrote:
> Has anyone done any work describing geometrical problems in a CSP? I  
> mean things like:
> 
> Circle C(P,R) has midpoint P and radius R.
> P lies on the line joining P1 and P2.
> C touches circle Ck(Pk, Rk)
> Find the solution that minimises d(P, Q)
> etc.

A small example is in the Tutorial and the Library Manual.

Here is some more:

:- lib(ic).
:- lib(branch_and_bound).

% distance between P1 and P2 is D
distance(point(X1,Y1), point(X2,Y2), D) :-
	D $>= 0,
	sqr(X2-X1) + sqr(Y2-Y1) $= sqr(D).

% P is on the circle with PCenter and Radius
circle(PCenter, Radius, P) :-
	distance(PCenter, P, Radius).

% P is on the line through P1 and P1
line(P1, P2, P) :-
	line(P1, P2, _K, P).

% P is on the lice segment between P1 and P2
line_segment(P1, P2, P) :-
	line(P1, P2, K, P),
	K $:: 0.0..1.0.

line(point(X1,Y1), point(X2,Y2), K, point(X,Y)) :-
	X $= X1 + (X2-X1)*K,
	Y $= Y1 + (Y2-Y1)*K.

fix_real(X) :-
	X is breal_from_bounds(get_min(X),get_max(X)).



Some examples using the predicates above:

The unique intersection between a circle and a line segment:

?- circle(point(0, 0), 3, P),
    line_segment(point(-2, 0), point(3, 5), P).

P = point(_574{0.87082866818486693 .. 0.87082870103170329}, _369{2.8708286681848674 ..
2.8708287010317028})
There are 5 delayed goals.
Yes (0.00s cpu)
	


The two intersections between a circle and a line:

?- circle(point(0, 0), 3, P),
    line(point(-2, 0), point(3, 5), P),
    P = point(X, _150),
    locate([X], 0.01, log).

P = point(X{0.87082866818486693 .. 0.87082870103170329}, _473{2.8708286681848674 .. 
2.8708287010317028})
X = X{0.87082866818486693 .. 0.87082870103170329}
There are 5 delayed goals.
Yes (0.01s cpu, solution 1, maybe more)

P = point(X{-2.8708287010317028 .. -2.8708286681848674}, _473{-0.87082870103170329 ..
-0.87082866818486726})
X = X{-2.8708287010317028 .. -2.8708286681848674}
There are 5 delayed goals.
Yes (0.01s cpu, solution 2)



You could even use branch-and-bound to find the minimum distance between circle
and line, as follows:

?- circle(point(0, 0), 3, P),
    line(point(0, 5), point(8, 0), Q),
    distance(P, Q, D),
    term_variables([P, Q, D], Vs),
    bb_min((locate(Vs, 0.001, log), fix_real(D)), D, bb_options{delta:0.01}).

P = point(_887{1.5284676637721435 .. 1.5297642651352179}, _682{2.5806629561248995 ..
2.5814311148668918})
Q = point(X{2.1386853706646196 .. 2.1399296908568717}, Y{3.6625439432144544 ..
3.6633215975627791})
D = 1.240802103631685__1.2414797337480334
Vs = [1.240802103631685__1.2414797337480334, Y{3.6625439432144544 .. 
3.6633215975627791},
X{2.1386853706646196 .. 2.1399296908568717}, _682{2.5806629561248995 ..
2.5814311148668918}, _887{1.5284676637721435 .. 1.5297642651352179}]
There are 11 delayed goals.
Yes (2.89s cpu)

Note that this is probably not a good method though.  Branch and bound works
in discrete steps (here 0.01) and finds an arbitrary first point whose distance
is within 0.01 of the provable lower bound.  In this example I guess it would
be better to describe the min-distance condition geometrically (line C-Q being
orthogonal on P1-P2).


-- Joachim