From: Igor Kondrasovas <igor_at_inovativatec.com>

Date: Wed, 17 Mar 2010 18:57:42 -0300

Date: Wed, 17 Mar 2010 18:57:42 -0300

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.Received on Wed Mar 17 2010 - 22:13:09 CET

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