From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>

Date: Fri, 19 Mar 2010 00:59:36 +1100

Date: Fri, 19 Mar 2010 00:59:36 +1100

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) -- JoachimReceived on Thu Mar 18 2010 - 13:59:48 CET

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