(*
   Ejemplos
*)

P = {{0.85, 0.14}, {0.91, 0.23}, {0.59, 0.29}, {0.88, 0.44}, {0.68, 0.45},
     {0.8, 0.62}, {0.86, 0.56}, {0.92, 0.68}, {0.92, 0.56}, {0.96, 0.57},
     {0.96, 0.84}, {0.63, 0.9}, {0.61, 0.76}, {0.69, 0.77}, {0.64, 0.64},
     {0.49, 0.76}, {0.4, 0.69}, {0.46, 0.59}, {0.38, 0.54}, {0.31, 0.72},
     {0.21, 0.82}, {0.13, 0.81}, {0.17, 0.65}, {0.11, 0.6}, {0.28, 0.57},
     {0.2, 0.46}, {0.33, 0.37}, {0.19, 0.35}, {0.13, 0.21}, {0.08, 0.2},
     {0.07, 0.36}, {0.035, 0.36}, {0.038, 0.12}, {0.33, 0.11}, {0.54, 0.53},
     {0.52, 0.094}, {0.68, 0.23}, {0.71, 0.094}};

Q = Reverse[P];

(*
   ======================================================
   Área de un triángulo
   ======================================================
*)

Área[{p1_, p2_}, {q1_, q2_}, {r1_, r2_}]:= (1/2) Abs[Det[{{p1, p2, 1}, {q1, q2, 1}, {r1, r2, 1}}]]


(*
   ======================================================
   Orientación de un triángulo
   ======================================================
*)

Orientación[{p1_, p2_}, {q1_, q2_}, {r1_, r2_}]:= Sign[Det[{{p1,p2, 1}, {q1, q2, 1}, {r1, r2, 1}}]]


(*
   ======================================================
   Posición relativa de un punto respecto a un triángulo.
   ======================================================
*)


InteriorQ[{p_, q_, r_}, v_]:= InteriorQ[{r, q, p}, v] /; Orientación[p,q,r]==-1

InteriorQ[{p_, q_, r_}, v_]:= Orientación[q,p,v]=!=1 && Orientación[r,q,v]=!=1 && Orientación[p,r,v]=!=1



(*
   ======================================================
   Vértice convexo de un polígono simple
   ======================================================
*)

VérticeConvexo[P_]:= First[Ordering[P, 1]]


(*
   ======================================================
   Orientación de un polígono simple
   ======================================================
*)

Orientación[P_]:=
 Module[{v, u, w, vsints},

        (* Un vértice convexo y sus contiguos *)

        v = VérticeConvexo[P];
        u = If[v==1, Length[P], v-1];
        w = If[v==Length[P], 1, v+1];

        (* Orientación del triángulo *)

        Orientación[P[[u]], P[[v]], P[[w]]]]


(*
   ======================================================
   Determinación de una diagonal interior a un polígono.
   ======================================================
*)


DiagonalInterior[P_]:=
 Module[{v, u, w, vsints, r},

        (* Un vértice convexo y sus contiguos *)

        v = VérticeConvexo[P];
        u = If[v==1, Length[P], v-1];
        w = If[v==Length[P], 1, v+1];

        (* Vértices interiores al triángulo (u,v,w) *)

        vsints = Select[Delete[P, {{u}, {v}, {w}}], InteriorQ[P[[{u,v,w}]], #]&];

        (* Si no hay vértices interiores *)

        If[vsints == {}, Return[Sort[{u, w}]]];

        (* En caso contrario *)

        r = Position[P,
                     Last[Sort[vsints, (Área[P[[u]], #1, P[[w]]] <= Área[P[[u]], #2, P[[w]]])&]]][[1,1]];

        Sort[{v,r}]]


(*
   ======================================================
   Triangulación de un polígono.
   ======================================================
*)


Triangula[P_]:= Triangula[P, Range[Length[P]]]

Triangula[P_, {i_, j_, k_}]:= {{i,j,k}}

Triangula[P_, inds_]:=
 Module[{d},
        d = DiagonalInterior[P[[inds]]];
        Join[Triangula[P, Take[inds, d]], Triangula[P, Drop[inds, d+{1,-1}]]]]


(*
   ======================================================
   Coloreado.
   ======================================================
*)


Colorea[P_]:= Colorea[P, Triangula[P]]

Colorea[P_, t_]:= {1, 2, 3} /; Length[P] == 3

Colorea[P_, t_]:=
  Module[{oreja, v, colores},
         oreja = First[Select[t, (Abs[#[[3]] - #[[1]]] == 2) &, 1]];
         v = Part[oreja, 2];
         colores = Colorea[Delete[P, v], DeleteCases[t, oreja] /. {n_?(# > v &) :> n - 1}];
         Insert[colores, 6-colores[[v-1]]-colores[[v]], v]] /; Length[P] > 3

(*
   ======================================================
   Vigilantes
   ======================================================
*)


Vigilantes[c_]:=
  Module[{aux},
         aux = Map[Count[c, #] &, {1, 2, 3}];
         aux = Part[Position[totales, Min[totales]], 1, 1];
         {Flatten[Position[c, aux]], aux}]
         
         
(*
   ======================================================
   Funciones para pintar
   ======================================================
*)


PintaPolígono[P_, p_:{}]:=
 Show[Graphics[{Line[Append[P, First[P]]], Map[Point, P[[p]]]}]]


PintaTriangulación[P_, t_]:=
 Show[Graphics[{{Thickness[0.012], Line[Append[P, First[P]]]},
                Map[Line[P[[#]]]&, t]}]]


PintaPintaColorea[P_, t_, c_]:=
  Module[{colores},
         colores = {RGBColor[1, 0, 0], RGBColor[0, 1, 0], RGBColor[0, 0, 1]};
         Show[Graphics[List[Map[Line[P[[#]]]&, t],
                            {Thickness[0.012], Line[Append[P, First[P]]]},
                            {PointSize[0.025], Map[List[Part[colores, First[#]], Point[Last[#]]]&, Transpose[{c, P}]]}]]]]
                            
                            
PintaVigilantes[P_, vg_]:=
  Module[{color},
         color = Part[{RGBColor[1, 0, 0], RGBColor[0, 1, 0], RGBColor[0, 0, 1]}, Last[vg]];
         Show[Graphics[List[{Thickness[0.012], Line[Append[P, First[P]]]},
                            {PointSize[0.025], List[color, Map[Point[P[[#]]] &, First[vg]]]}]]]]


ShowGuards[poly_]:= (col3 = ThreeColor[poly];
        Show[Graphics[{{Thickness[0.008], Line[extend[poly]]}, {PointSize[0.03], 
            Point /@ poly\[LeftDoubleBracket]Flatten[Position[col3,
                                        Position[counts = Count[col3, #] & /@ {1, 2, 3},
                                            Min[counts]]\[LeftDoubleBracket]1, 
                      1\[RightDoubleBracket]]]\[RightDoubleBracket]}}],
            AspectRatio -> Automatic])