Arbitrary 2D Triangulation

/* triangles(Points, Triangles) is true if the elements t(P1,P2,P3) of       */
/*   Triangles comprise an arbitrary triangulation of the Points, the        */
/*   vertices of the triangles going anticlockwise.                          */
/* e.g. triangles([p(1,5),p(9,3),p(0,9),p(5,5),p(4,2)], X)                   */
/*   gives X=[t(p(4,2),p(9,3),p(5,5)), t(p(0,9),p(5,5),p(9,3)),              */
/*            t(p(0,9),p(4,2),p(5,5)), t(p(0,9),p(1,5),p(4,2))]              */
/* This is a O(nlogn) algorithm.                                             */
triangles(Points, Triangles):-
  sort(Points, [P1,P2|Points1]), % Duplicated points are discarded
  triangles_1(Points1, P2, [P1], [P1], [], Triangles).

triangles_1([], _, _, _, Triangles, Triangles).
triangles_1([P2|Points], P1, Us0, Ls0, Triangles0, Triangles):-
  upper_hull(Us0, P1, P2, Us1, Triangles0, Triangles1),
  lower_hull(Ls0, P1, P2, Ls1, Triangles1, Triangles2),
  triangles_1(Points, P2, Us1, Ls1, Triangles2, Triangles).

/* upper_hull(Us0, P1, P2, Us, [], Triangles) is true if [P1|Us0] are the    */
/*   vertices of the current upper convex hull, [P2|Us] are the vertices of  */
/*   the new upper convex hull after adding P2, and Triangles are the        */
/*   triangles resulting from 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.)                                                          */
upper_hull([P|Us0], P1, P2, Us, Triangles0, Triangles):-
  \+ strictly_to_right(P1, P2, P), !,
  upper_hull(Us0, P, P2, Us, [t(P,P1,P2)|Triangles0], Triangles).
upper_hull(Us0, P, _, [P|Us0], Triangles, Triangles).

/* lower_hull(Ls0, P1, P2, Ls, [], Triangles) is true if [P1|Ls0] are the    */
/*   vertices of the current lower convex hull, [P2|Ls] are the vertices of  */
/*   the new lower convex hull after adding P2, and Triangles are the        */
/*   triangles resulting from 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.)                                                          */
lower_hull([P|Ls0], P1, P2, Ls, Triangles0, Triangles):-
  \+ strictly_to_left(P1, P2, P), !,
  lower_hull(Ls0, P, P2, Ls, [t(P,P2,P1)|Triangles0], Triangles).
lower_hull(Ls0, P, _, [P|Ls0], Triangles, Triangles).

/* strictly_to_left(Pa, Pb, Pc) is true if Pa is strictly to the left of the */
/*   directed line from Pb to Pc.                                            */
strictly_to_left(p(Xa,Ya), p(Xb,Yb), p(Xc,Yc)):-
  (Xb-Xa) * (Yc-Ya) - (Xc-Xa) * (Yb-Ya) > 0.

/* strictly_to_right(Pa, Pb, Pc) is true if Pa is strictly to the right of   */
/*   the directed line from Pb to Pc.                                        */
strictly_to_right(p(Xa,Ya), p(Xb,Yb), p(Xc,Yc)):-
  (Xb-Xa) * (Yc-Ya) - (Xc-Xa) * (Yb-Ya) < 0.

LPA Index     Home Page

Valid HTML 4.01 Strict