Convex Hull

This is apparently a variation on Andrew's variant of Graham's scan.

/*
 * Convex Hull
 *   The convex hull of a set of points is the smallest convex region
 *   containing the points
 */

/* convex_hull(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). No three vertices of the convex hull  */
/*   will be collinear.                                                      */
/* e.g. convex_hull([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)]).                   */
convex_hull(Points, ConvexHullVertices):-
  sort(Points, Points1), % Duplicated points are discarded
  convex_hull_1(Points1, ConvexHullVertices).

convex_hull_1([P1], [P1,P1]):-!.
convex_hull_1([P1,P2|Points], ConvexHullVertices):-
  convex_hull_2(Points, P2, [P1], UpperHull, [P1], LowerHull),
  join(UpperHull, LowerHull, ConvexHullVertices).

/* convex_hull_2(Ps, P, Upper0, Upper, Lower0, Lower) is true if [P|Upper0]  */
/*   are the vertices of the current upper convex hull, [P|Lower0] are the   */
/*   vertices of the current lower convex hull, Upper are the vertices of    */
/*   the new upper convex hull and Lower are the vertices of the new lower   */
/*   convex hull after adding the points Ps.                                 */
convex_hull_2([], P1, Upper, [P1|Upper], Lower, Lower).
convex_hull_2([P2|Ps], P1, Upper0, Upper, Lower0, Lower):-
  update_upper_hull(Upper0, P1, P2, Upper1),
  update_lower_hull(Lower0, P1, P2, Lower1),
  convex_hull_2(Ps, P2, Upper1, Upper, Lower1, Lower).

/* update_upper_hull(Ps, P1, P2, Qs) is true if [P1|Ps] are the vertices of  */
/*   the current upper convex hull, and [P2|Qs] are the vertices of the new  */
/*   upper convex hull after adding P2.                                      */
/* (Go back along the vertices, discarding all up to but not including those */
/*   of the last encountered edge which is not visible from the outside by   */
/*   the point P2.)                                                          */
update_upper_hull([P|Ps], P1, P2, Qs):-
  to_left_or_collinear(P1, P2, P), !,
  update_upper_hull(Ps, P, P2, Qs).
update_upper_hull(Ps, P, _, [P|Ps]).

/* update_lower_hull(Ps, P1, P2, Qs) is true if [P1|Ps] are the vertices of  */
/*   the current lower convex hull, and [P2|Qs] are the vertices of the new  */
/*   lower convex hull after adding P2.                                      */
/* (Go back along the vertices, discarding all up to but not including those */
/*   of the last encountered edge which is not visible from the outside by   */
/*   the point P2.)                                                          */
update_lower_hull([P|Ps], P1, P2, Qs):-
  to_right_or_collinear(P1, P2, P), !,
  update_lower_hull(Ps, P, P2, Qs).
update_lower_hull(Ps, P, _, [P|Ps]).

join([], ConvexHull, ConvexHull).
join([Vertex|UpperHull], LowerHull, ConvexHull):-
  join(UpperHull, [Vertex|LowerHull], ConvexHull).

/* to_left_or_collinear(Pa, Pb, Pc) is true if Pa is to the left of, or on,  */
/*   the directed line from Pb to Pc.                                        */
to_left_or_collinear(p(Xa,Ya), p(Xb,Yb), p(Xc,Yc)):-
  (Xb-Xa) * (Yc-Ya) - (Xc-Xa) * (Yb-Ya) >= 0.0.

/* to_right_or_collinear(Pa, Pb, Pc) is true if Pa is to the right of, or on,*/
/*   the directed line from Pa to Pb.                                        */
to_right_or_collinear(p(Xa,Ya), p(Xb,Yb), p(Xc,Yc)):-
  (Xb-Xa) * (Yc-Ya) - (Xc-Xa) * (Yb-Ya) =< 0.0.

LPA Index     Home Page

Valid HTML 4.0 Strict