From: Joachim Schimpf (Independent Contractor) <jschimpf_at_cisco.com>

Date: Thu, 18 Oct 2007 04:59:20 -0700

Date: Thu, 18 Oct 2007 04:59:20 -0700

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). -- JoachimReceived on Thu Oct 18 2007 - 12:59:53 CEST

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*