/* * Convex Hull (Quickhull) * The convex hull of a set of points is the smallest convex region * containing the points */ /* quickhull(Points, ConvexHullVertices) is true if Points is a list of */ /* points in the form p(X,Y), and ConvexHullVertices are the vertices in */ /* the form p(X,Y) of the convex hull of the Points, in clockwise order, */ /* starting and ending at the smallest point (as determined by X-values, */ /* and by Y-values to resolve ties). */ /* e.g. quickhull([p(0,6),p(3,7),p(4,6),p(4,5),p(3,4),p(2,4),p(5,0)], */ /* [p(0,6),p(3,7),p(4,6),p(5,0),p(0,6)]). */ quickhull(Points, [P1|Vertices]):- min_max_list(Points, P1, P2), points_to_left(Points, P1, P2, LeftMost, Ls), points_to_left(Points, P2, P1, RightMost, Rs), \+ both_empty(Ls, Rs), !, quickhull_1(Rs, P2, RightMost, P1, Vertices0, []), quickhull_1(Ls, P1, LeftMost, P2, Vertices, Vertices0). quickhull(Points, [P1,P1]):- min_max_list(Points, P1, P2), P1=P2, /* All points identical */ !. quickhull(Points, [P1,P2,P1]):- /* All points collinear */ min_max_list(Points, P1, P2). /* quickhull_1(Ps, P1, P2, P3, Ys, []) is true if Ys is that part of the */ /* convex hull to the left of the line from P1 to P3 of those points in Ps */ /* outside the triangle defined by the points P1, P2 and P3, where P2 is */ /* that element of Ps furthest to the left of the line from P1 to P3. */ quickhull_1([], _, _, P3, [P3|Ys], Ys):-!. quickhull_1(Ps, P1, P2, P3, Ys, Zs):- points_to_left(Ps, P1, P2, LeftMost12, Ps1), points_to_left(Ps, P2, P3, LeftMost23, Ps2), quickhull_1(Ps2, P2, LeftMost23, P3, Ws, Zs), quickhull_1(Ps1, P1, LeftMost12, P2, Ys, Ws). both_empty([], []). /* min_max_list(List, Min, Max) is true if Min is the minimum value in the */ /* List, and Max is the maximum value. */ min_max_list([X|Xs], Min, Max):-min_max_list_1(Xs, X, X, Min, Max). min_max_list_1([], Min, Max, Min, Max). min_max_list_1([X|Xs], OldMin, OldMax, Min, Max):- min_max(X, OldMin, OldMax, NewMin, NewMax), min_max_list_1(Xs, NewMin, NewMax, Min, Max). min_max(p(X,Y), p(X0,_), Max, p(X,Y), Max):-X < X0, !. min_max(p(X,Y), p(X,Y0), Max, p(X,Y), Max):-Y < Y0, !. /* Resolve ties */ min_max(p(X,Y), Min, p(X0,_), Min, p(X,Y)):-X > X0, !. min_max(p(X,Y), Min, p(X,Y0), Min, p(X,Y)):-Y > Y0, !. /* Resolve ties */ min_max(_, Min, Max, Min, Max). /* points_to_left(Ps, P1, P2, LeftMost, Ls) is true if Ls are the points of */ /* Ps strictly to the left of the line through P1 and P2, and LeftMost is */ /* the point furthest to the left of the line through P1 and P2. */ points_to_left(Ps, P1, P2, LeftMost, Ls):- points_to_left_1(Ps, P1, P2, a(0.0,void,LeftMost), Ls). points_to_left_1([], _, _, a(_,LeftMost,LeftMost), []). points_to_left_1([P|Ps], P1, P2, State, Ls):- area(P1, P2, P, Area), points_to_left_2(Area, Ps, P, P1, P2, State, Ls). points_to_left_2(Area, Ps, P, P1, P2, a(Area0,_,LeftMost), [P|Ls]):- Area > Area0, !, /* P is to left, and further than P0 */ points_to_left_1(Ps, P1, P2, a(Area,P,LeftMost), Ls). points_to_left_2(Area, Ps, P, P1, P2, a(Area,P0,LeftMost), [P|Ls]):- /* P is to left, and same distance as P0 */ area(P1, P0, P, Area1), Area1 > 0, !, /* P1 is nearer to P than P0 */ points_to_left_1(Ps, P1, P2, a(Area,P,LeftMost), Ls). points_to_left_2(Area, Ps, P, P1, P2, State, [P|Ls]):- Area > 0.0, !, /* P is to left and nearer than P0 */ points_to_left_1(Ps, P1, P2, State, Ls). points_to_left_2(_, Ps, _, P1, P2, State, Ls):- /* P is to right or collinear */ points_to_left_1(Ps, P1, P2, State, Ls). /* area(Pa, Pb, Pc, Area) is true if Area is twice the signed area of the */ /* triangle determined by Pa, Pb and Pc. The area is positive if Pa, Pb */ /* and Pc are oriented anti-clockwise, negative if clockwise, and zero if */ /* the points are collinear. */ area(p(Xa,Ya), p(Xb,Yb), p(Xc,Yc), Area):- Area is (Xb-Xa) * (Yc-Ya) - (Xc-Xa) * (Yb-Ya).