Jarvis's March (Convex Hull)
/*
* Convex Hull (Jarvis's March)
* The convex hull of a set of points is the smallest convex region
* containing the points
*/
/* jarvis(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. jarvis([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)]). */
jarvis(Points, [Pstart|ConvexHullVertices]):-
min(Points, Pstart),
jarvis_1([Pstart|Points], Pstart, Pstart, ConvexHullVertices).
jarvis_1([P1|Ps], P0, Pstart, [Q|Qs]):-
jarvis_2(Ps, P1, P0, [], Ps1, Q),
Q \= Pstart, !,
jarvis_1(Ps1, Q, Pstart, Qs).
jarvis_1(_, _, Pstart, [Pstart]).
/* jarvis_2(Ps, P1, P0, [], Ps1, Q) is true if Q is that member of [P1|Ps] */
/* which is on or to the left of the line from P0 to P1, and for which */
/* the polar angle going anti-clockwise relative to P0 is the maximum. */
/* Ties are resolved by taking the point furthest from P0. Ps1 are the */
/* other elements of Ps (not necessarily in the same order), except that */
/* interior collinear points are discarded. (It still works if they are */
/* not discarded.) */
jarvis_2([], P, _, Ps, Ps, P).
jarvis_2([P0|Ps], P1, P0, Ps0, Ps1, Q):-!,
jarvis_2(Ps, P1, P0, [P0|Ps0], Ps1, Q).
jarvis_2([P2|Ps], P1, P0, Ps0, Ps1, Q):-
direction(P2, P0, P1, Direction),
jarvis_3(Direction, Ps, P2, P1, P0, Ps0, Ps1, Q).
jarvis_3(left, Ps, P2, P1, P0, Ps0, Ps1, Q):-!,
jarvis_2(Ps, P2, P0, [P1|Ps0], Ps1, Q).
jarvis_3(right, Ps, P2, P1, P0, Ps0, Ps1, Q):-!,
jarvis_2(Ps, P1, P0, [P2|Ps0], Ps1, Q).
jarvis_3(collinear, Ps, P2, P1, P0, Ps0, Ps1, Q):-
is_nearer(P2, P1, P0), !,
/* P2 is nearer to P0 than P1 is */
jarvis_2(Ps, P1, P0, Ps0, Ps1, Q).
jarvis_3(collinear, Ps, P2, _, P0, Ps0, Ps1, Q):-
/* P1 is nearer to P0 than P2 is */
jarvis_2(Ps, P2, P0, Ps0, Ps1, Q).
/* min(List, Min) is true if Min is the smallest element in List as */
/* determined by lt/2. */
min([X|Xs], Y):-min_1(Xs, X, Y).
min_1([], X, X).
min_1([Y|Ys], X, Z):-lt(Y, X), !, min_1(Ys, Y, Z).
min_1([_|Ys], X, Z):-min_1(Ys, X, Z).
lt(p(X,_), p(X1,_)):-X < X1, !.
lt(p(X,Y), p(X,Y1)):-Y < Y1.
/* direction(Pa, Pb, Pc, Dirn) is true if Pa is strictly to the left of the */
/* directed line from Pb to Pc, and Dirn=left; Pa is strictly to the right */
/* of the directed line from Pb to Pc, and Dirn=right; or Pa, Pb and Pc */
/* are collinear, and Dirn=collinear. */
direction(p(Xa,Ya), p(Xb,Yb), p(Xc,Yc), Dirn):-
Area is (Xb-Xa) * (Yc-Ya) - (Xc-Xa) * (Yb-Ya),
direction_1(Area, Dirn).
direction_1(Area, left):-Area > 0.0, !.
direction_1(Area, right):-Area < 0.0, !.
direction_1(_, collinear).
/* is_nearer(Pa, Pb, Pc) is true if Pa is strictly nearer to Pc than Pb is. */
is_nearer(p(Xa,Ya), p(Xb,Yb), p(Xc,Yc)):-
Xa_Xc is Xa - Xc,
Ya_Yc is Ya - Yc,
Xb_Xc is Xb - Xc,
Yb_Yc is Yb - Yc,
(Xa_Xc)*(Xa_Xc) + (Ya_Yc)*(Ya_Yc) < (Xb_Xc)*(Xb_Xc) + (Yb_Yc)*(Yb_Yc).
LPA Index
Home Page