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 Twitter: @ikondrasovas Blog: http://ikondrasovas.wordpress.com Facebook: www.facebook.com/ikondrasovas -----Mensagem original----- De: Igor Kondrasovas [mailto:igor_at_inovativatec.com] Enviada em: sexta-feira, 2 de abril de 2010 19:58 Para: 'Joachim Schimpf'; eclipse-clp-users_at_lists.sf.net Assunto: [eclipse-clp-users] RES: Domain Definiton in Cut and Packing Problem Hello Joachim, Thank you for the reply. It made me have a brighter view about what I was 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 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) :- ( 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 ---------------------------------------------------------------------------- -- Download Intel® 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. 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 ---------------------------------------------------------------------------- -- Download Intel® 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. 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-usersReceived on Wed Apr 07 2010 - 00:10:42 CEST
This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET