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

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. Other approach are ver
"procedural" and complex. To my class of problem, this approach would be
just fine.

 

Now I must find out if it is best to investigate how to model this
constraints or if I can somehow "remove" the labeled value from the domain,
as this position would be marked as invalid.

 

What do you suggest?

 

Kindly Regards,

 

Igor.