#### Quickhull

/*
* 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).