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

From: Igor Kondrasovas <igor_at_inovativatec.com>
Date: Fri, 2 Apr 2010 19:57:39 -0300
Hello Joachim,

Thank you for the reply. It made me have a brighter view about what I was

I rewrote a bit my check predicate to support an offset value. This is due
to the fact that my polygon will be offset in my domain:

leftof_line((X,Y), (OffX, OffY), (X1,Y1), (X2,Y2)) :-
        (Y - (Y1 + OffY)) * ((X2 + OffX) - (X1 + OffX)) - (X - (X1 + OffX))
* ((Y2 + OffY) - (Y1 + OffY)) #> 0.

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

This works fine when the Offset is hard-coded (for testing only). In
reality, this value represents a Point in the domain area, that will also be
found by the same predicate (outside_polygon1). Let me try to explain:

As I said before this is a nesting decision problem, so the program must
distribute the pieces (polygons) in the domain. For every piece, a Point
will be used as a reference and every Point must be assigned to a value that
has a constraint to not overlap the other polygons.

A possible call for the predicate that solves the nesting problem would be:



[(X1,Y1),(X2,Y2)] are the reference points for two polygons A and B
respectively that must be nested. These are the variables that I must find
in my domain

[[(0,0),(0,2)],[(0,2),(2,0)],[(2,0),(0,0)]] is the Non-Fit polygon from A to
B. To summarize this polygon is used to test if one polygon A is overlapping
B. That´s why we use the outside_polygon1 predicate.

[[(0,2),(2,2)],[(2,2),(2,0)],[(2,0),(0,2)]] is the Non-Fit polygon from B to

Thinking in 2 polygons scenario, I could have:

solve([(X1,Y1)|(X2,Y2)], [NFAB| NFBA]):-
	outside_polygon1((X1,Y1), (X2,Y2), NFAB),
	outside_polygon1((X2,Y2), (X1,Y1), NFBA).

Using this predicate actually did not produce any results, probably because
the offset values are not defined for the first outside_polygon1 call.

I would like to ask you if this is a feasible approach or if I should change
the strategy. Please let me know if you need some additional clarification.

Kindly Regards,

Igor Kondrasovas
Twitter: @ikondrasovas
Blog: http://ikondrasovas.wordpress.com
Facebook: www.facebook.com/ikondrasovas

-----Mensagem original-----
De: Joachim Schimpf [mailto:joachim.schimpf_at_infotech.monash.edu.au] 
Enviada em: quinta-feira, 18 de março de 2010 11:00
Para: eclipse-clp-users_at_lists.sf.net
Assunto: 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) :-
	   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

Download Intel&#174; Parallel Studio Eval
Try the new software tools for yourself. Speed compiling, find bugs
proactively, and fine-tune applications for parallel performance.
See why Intel Parallel Studio got high marks during beta.
ECLiPSe-CLP-Users mailing list
Received on Fri Apr 02 2010 - 22:57:50 CEST

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