Re: [eclipse-clp-users] Domain Definiton in Cut and Packing Problem

Igor Kondrasovas wrote:
> Hello All,
> 
> Currently I’m working in a bi-dimensional nesting decision problem 
> (classified in the cut and packing problem class).
> 
> This problem has some geometric constraints. One of them is to make sure 
> the pieces (convex polygons in my case) do not overlap each other in the 
> sheet they will be placed.
> 
> The following piece of code demonstrates an easy way (taken form 
> http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/ at subtitle 
> “Solution 3 (2D)”) to determine if a point is inside a specific polygon. 
> This would help to restrict where can I position each polygon (Xt and Yt 
> values) to make sure pieces do not overlap:
> 
> inside((Xt,Yt), Polygon) :-
>        checkPolygon((Xt, Yt), Polygon),
>        labeling([Xt,Yt]),
>        writeln(Xt),
>        writeln(Yt).
>
> checkPolygon(_,[]).
> checkPolygon((Xt, Yt), [Segment|PolygonTale]) :-
>        Xt #:: -10..10,
>        Yt #:: -10..10,
>        checkPointSide((Xt, Yt), Segment) infers most,
>        checkPolygon((Xt, Yt), PolygonTale).
>  
> checkPointSide((Xt, Yt), [(FromX, FromY),(ToX, ToY)]):-
>        (((Yt - FromY) * (ToX - FromX)) - ((Xt - FromX) * (ToY - FromY))) #< 0.
> 
> You can test the predicate using:
> 
> inside((X,Y),[[(0,0),(0,5)],[(0,5),(5,0)],[(5,0),(0,0)]]).
> 
> The problem here is that after labeling, I will have the values in the 
> specified domain that are inside the polygon. In other words, they will 
> assume values where piece DO overlap. This is the opposite from what I 
> need. Those values should be removed from the domain instead. 
> Unfortunately I could not find a way to impose the constraint in order 
> to label my variables (Xt and Yt) to a point where no overlap occurs. 

Your check is based on the idea that a point is inside a polygon, iff it
is "to the right of" every polygon side line (when going through them
clockwise).  This is a simple conjunction of conditions, and that's
what you have done in your code (the 'infers' you have used here actually
has no effect, because its left hand side is just a primitive constraint -
If you take it out, your code works just as well).
Left me rewrite it a bit:

% Point (X,Y) is right of line (X1,Y1)->(X2,Y2)
rightof_line((X,Y), (X1,Y1), (X2,Y2)) :-
        (Y - Y1) * (X2 - X1) - (X - X1) * (Y2 - Y1) #< 0.

inside_polygon(Point, Segments) :-
	( foreach([P1,P2],Segments), param(Point) do
	    rightof_line(Point, P1, P2)
	).


The problem with formulating outside-ness is that you have a disjunction:
A point is outside a polygon iff it is "to the left of" ANY side line.
We need

% Point (X,Y) is left of the line (X1,Y1)->(X2,Y2)
leftof_line((X,Y), (X1,Y1), (X2,Y2)) :-
        (Y - Y1) * (X2 - X1) - (X - X1) * (Y2 - Y1) #> 0.

To turn the disjunction into a proper constraint, there are two basic
possibilities:  the 'infers' solution, and using reified constraints.
Look at 'infers' first: it makes sense here, because its job is to
extract deterministic information from something disjunctive.  In this
case it's the disjunction of conditions over the line segments:

outside_polygon1(Point, Segments) :-
	(member([P1,P2],Segments), leftof_line(Point, P1, P2)) infers ic.

The other way is to use a reified version of the "leftof" constraint,
i.e. one that computes a boolean that reflects the truth value:

leftof_line((X,Y), (X1,Y1), (X2,Y2), Leftof) :-
        Leftof #= ((Y - Y1) * (X2 - X1) - (X - X1) * (Y2 - Y1) #> 0).

Only one of these must be true (i.e. 1) to prove "outside-ness", so:

outside_polygon2(Point, Segments) :-
	(
	    foreach([P1,P2],Segments),
	    param(Point),
	    foreach(Leftof,Leftofs)
	do
	   leftof_line(Point, P1, P2, Leftof)
	),
	sum(Leftofs) #> 0.    % at least one Leftof must be 1 (true)


I don't know which solution performs better in your application,
but the 'infers' technique can give better propagation:

?- poly(P), outside_polygon1((X,Y), P), [X,Y] :: -10..10, X=2.
P = [[(0, 0), (0, 5)], [(0, 5), (5, 0)], [(5, 0), (0, 0)]]
X = 2
Y = Y{[-10 .. -1, 4 .. 10]}
There is 1 delayed goal.
Yes (0.00s cpu)

?- poly(P), outside_polygon2((X,Y), P), [X,Y] :: -10..10, X=2.
P = [[(0, 0), (0, 5)], [(0, 5), (5, 0)], [(5, 0), (0, 0)]]
X = 2
Y = Y{-10 .. 10}
There are 3 delayed goals.
Yes (0.00s cpu)


-- Joachim