//package delaune;


class Algorithm {
  int s, t, u, bestPoint;
  Circle bC = new Circle();

  Triangle t1;

  public Algorithm(Triangle t, int point_number) {
    this.t1=t;
  }

  public synchronized void triangulate(Triangle tri) {   // pagrindinis algoritmas
    int seedEdge;
    int currentEdge;

    tri.findClosestPoints();
    seedEdge = tri.addEdge(tri.s,tri.t, Triangle.Undefined, Triangle.Undefined);
    currentEdge = 0;
    while (currentEdge < tri.edge_number) {
      if (tri.edgeArray[currentEdge].r == Triangle.Undefined||
          tri.edgeArray[currentEdge].l == Triangle.Undefined) {
        int eI=currentEdge;
        Edge e[] = tri.edgeArray;
        Point2D p[] = tri.pointArray;

        if (e[eI].l == Triangle.Undefined){
          s = e[eI].s;
          t = e[eI].t;
        }
        else if (e[eI].r == Triangle.Undefined){
          s = e[eI].t;
          t = e[eI].s;
        }

        // randame taska briaunos kaireje
        for (u = 0; u < tri.point_number; u++){
          if (u == s || u == t)
            continue;
          if (onWhichSide(p[s], p[t], p[u]) > 0.0)
            break;
        }

        // randame geriausia nauja taska
        bestPoint = u;
        if (bestPoint < tri.point_number){
          bC.circumCircle(p[s], p[t], p[bestPoint]);
          for (u = bestPoint+1; u < tri.point_number; u++){
            if (u == s || u == t)
              continue;
            if (onWhichSide(p[s], p[t], p[u]) > 0.0)
              if (bC.inside(p[u])){
                bestPoint = u;
                bC.circumCircle(p[s], p[t], p[u]);
              }
          }
        }

        // pataisoma senoji briauna
        if (bestPoint < tri.point_number){
          tri.updateEdge(eI, s, t);

          // pridedama nauja briauna arba taisoma senoji
          eI = tri.findEdge(bestPoint, s);
          if (eI == Triangle.Undefined)
            eI = tri.addEdge(bestPoint, s, 1, Triangle.Undefined);
          else
            tri.updateEdge(eI, bestPoint, s);

            // pridedama antra nauja briauna arba taisoma senoji
          eI = tri.findEdge(t, bestPoint);
          if (eI == Triangle.Undefined)
            eI = tri.addEdge(t, bestPoint, 1, Triangle.Undefined);
          else
            tri.updateEdge(eI, t, bestPoint);
        }
      }
      currentEdge++;
    }
  }


  static float onWhichSide(Point2D p1, Point2D p2, Point2D p3) {
       float u1, v1, u2, v2;
       u1 =  p2.x - p1.x;
       v1 =  p2.y - p1.y;
       u2 =  p3.x - p1.x;
       v2 =  p3.y - p1.y;
       return u1 * v2 - v1 * u2;
   }
}