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

From: Igor Kondrasovas <igor_at_...186...>
Date: Tue, 6 Apr 2010 21:10:31 -0300
```Hello,

Please let me rewrite a predicate that was erroneously copied while editing
the previous e-mail:

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

You can use as an example:

solve((X1,Y1),(X2,Y2),
[[[(0,0),(0,2)],[(0,2),(2,0)],[(2,0),(0,0)]],[[(0,2),(2,2)],[(2,2),(2,0)],[(
2,0),(0,2)]]]), [X1,Y1,X2,Y2] :: -100..100.

I still could not find a way to deal with the constraints in order to find
feasible values.

I would appreciate any suggestion.

Sincerely,

Igor Kondrasovas
Blog: http://ikondrasovas.wordpress.com

-----Mensagem original-----
De: Igor Kondrasovas [mailto:igor_at_...186...]
Enviada em: sexta-feira, 2 de abril de 2010 19:58
Para: 'Joachim Schimpf'; eclipse-clp-users_at_...105...
Assunto: [eclipse-clp-users] RES: Domain Definiton in Cut and Packing
Problem

Hello Joachim,

doing.

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:

solve([(X1,Y1),(X2,Y2)],[[(0,0),(0,2)],[(0,2),(2,0)],[(2,0),(0,0)]],[[(0,2),
(2,2)],[(2,2),(2,0)],[(2,0),(0,2)]]).

Where,

[(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
A.

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
Blog: http://ikondrasovas.wordpress.com

-----Mensagem original-----
De: Joachim Schimpf [mailto:joachim.schimpf_at_...44...]
Enviada em: quinta-feira, 18 de março de 2010 11:00
Para: eclipse-clp-users_at_...105...
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) :-
(
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

----------------------------------------------------------------------------
--
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.
http://p.sf.net/sfu/intel-sw-dev
_______________________________________________
ECLiPSe-CLP-Users mailing list
ECLiPSe-CLP-Users_at_lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users

----------------------------------------------------------------------------
--