Delaunay triangulation

It too long....

///

package triangulationapplet;

import java.applet.*;

import java.awt.*;

import java.lang.Math;

import java.io.PrintStream;

/*

* Sometimes we just have to die.

* Simple thinking!!!

*/

class Panic {

static public void panic(String m) {

System.err.println("Panic:"+m);

System.exit(1);

}

}

/*

* Wrapper class for basic int type for pass by reference.

*/

class Int {

int i;

public void Int() {

i = 0;

}

public void Int(int i) {

this.i = i;

}

public void setValue(int i) {

this.i = i;

}

public int getValue() {

return i;

}

}

/*

* Point class. RealPoint to avoid clash with java.awt.Point.

*/

class RealPoint {

float x, y;

RealPoint() { x = y = 0.0f; }

RealPoint(float x, float y) { this.x = x; this.y = y; }

RealPoint(RealPoint p) { x = p.x; y = p.y; }

public float x() { return this.x; }

public float y() { return this.y; }

public void set(float x, float y) { this.x = x; this.y = y; }

public float distance(RealPoint p) {

float dx, dy;

dx = p.x - x;

dy = p.y - y;

return (float)Math.sqrt((double)(dx * dx + dy * dy));

}

public float distanceSq(RealPoint p) {

float dx, dy;

dx = p.x - x;

dy = p.y - y;

return (float)(dx * dx + dy * dy);

}

}

/*

* Edge class. Edges have two vertices, s and t, and two faces,

* l (left) and r (right). The triangulation representation and

* the Delaunay triangulation algorithms require edges.

*/

class Edge {

int s, t;//s and t are the n掳 of vertices forming the edge.

int l, r;//For what matter did we need to know in which face are we?

Edge() { s = t = 0; }

Edge(int s, int t) { this.s =s; this.t = t; }

int s() { return this.s; }

int t() { return this.t; }

int l() { return this.l; }

int r() { return this.r; }

}

/*

* Vector class. A few elementary vector operations.

*/

class Vector {

float u, v;

Vector() { u = v = 0.0f; }

Vector(RealPoint p1, RealPoint p2) {

u = p2.x() - p1.x();

v = p2.y() - p1.y();

}

Vector(float u, float v) { this.u = u; this.v = v; }

float dotProduct(Vector v) { return u * v.u + this.v * v.v; }

static float dotProduct(RealPoint p1, RealPoint p2, RealPoint 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 * u2 + v1 * v2;

}

float crossProduct(Vector v) { return u * v.v - this.v * v.u; }

static float crossProduct(RealPoint p1, RealPoint p2, RealPoint 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;

}

void setRealPoints(RealPoint p1, RealPoint p2) {

u = p2.x() - p1.x();

v = p2.y() - p1.y();

}

}

/*

* Circle class. Circles are fundamental to computation of Delaunay

* triangulations. In particular, an operation which computes a

* circle defined by three points is required.

*/

class Circle {

RealPoint c;

float r;

Circle() { c = new RealPoint(); r = 0.0f; }

Circle(RealPoint c, float r) { this.c = c; this.r = r; }

public RealPoint center() { return c; }

public float radius() { return r; }

public void set(RealPoint c, float r) { this.c = c; this.r = r; }

/*

* Tests if a point lies inside the circle instance.

*/

public boolean inside(RealPoint p) {

if (c.distanceSq(p) < r * r)

return true;

else

return false;

}

/*

* Compute the circle defined by three points (circumcircle).

*/

public void circumCircle(RealPoint p1, RealPoint p2, RealPoint p3) {

float cp;

cp = Vector.crossProduct(p1, p2, p3);

if (cp != 0.0)

{

float p1Sq, p2Sq, p3Sq;

float num, den;

float cx, cy;

p1Sq = p1.x() * p1.x() + p1.y() * p1.y();

p2Sq = p2.x() * p2.x() + p2.y() * p2.y();

p3Sq = p3.x() * p3.x() + p3.y() * p3.y();

num = p1Sq*(p2.y() - p3.y()) + p2Sq*(p3.y() - p1.y()) + p3Sq*(p1.y() - p2.y());

cx = num / (2.0f * cp);

num = p1Sq*(p3.x() - p2.x()) + p2Sq*(p1.x() - p3.x()) + p3Sq*(p2.x() - p1.x());

cy = num / (2.0f * cp);

c.set(cx, cy);

}

// Radius

r = c.distance(p1);

}

}

/*

* Triangulation class. A triangulation is represented as a set of

* points and the edges which form the triangulation.

*/

class Triangulation {

static final int Undefined = -1;

static final int Universe = 0;

int nPoints;

RealPoint point[];

int nEdges;

int maxEdges;

Edge edge[];

Triangulation(int nPoints) {

// Allocate points.

this.nPoints = nPoints;

this.point = new RealPoint[nPoints];

for (int i = 0; i < nPoints; i++)

point = new RealPoint();

System.out.println("** Triangulation(int nPoints) **");

System.out.println("(1)- Allocate points");

System.out.println("this.nPoints="+Integer.toString(nPoints));

System.out.println("the array point["+Integer.toString(nPoints)+"] is empty!!!");

// Allocate edges.

maxEdges = 3 * nPoints - 6;// Max number of edges.

edge = new Edge[maxEdges];// Allocating an array of an object should be done like that...

for (int i = 0; i < maxEdges; i++)

edge = new Edge();

nEdges = 0;

System.out.println("(2)- Allocate edges.");

System.out.println("maxEdges="+Integer.toString(maxEdges));

System.out.println("the edge["+Integer.toString(maxEdges)+"] creation + it is empty!!!");

System.out.println("nEdges=0");

//System.out.println("== Triangulation(int nPoints) ==");

}

/*

* Sets the number of points in the triangulation. Reuses already

* allocated points and edges.

*/

public void setNPoints(int nPoints) {

System.out.println("** public void setNPoints(int nPoints) **");

// Fix edge array.

System.out.println("(1)- Fix edge array");

Edge tmpEdge[] = edge; // I think it should be done like that:Edge tmpEdge[] = edge[];

System.out.println("tmpEdge[] = edge[]");

int tmpMaxEdges = maxEdges;// I learn how to set an object array by another method...

System.out.println("tmpMaxEdges"+Integer.toString(tmpMaxEdges)+" = maxEdges"+Integer.toString(maxEdges));

maxEdges = 3 * nPoints - 6;// Max number of edges.

System.out.println("maxEdges"+Integer.toString(maxEdges));

edge = new Edge[maxEdges];// (*)I don't know if the edge array content is deleted by calling the new operator?

System.out.println("edge = new Edge[" + Integer.toString(maxEdges) +"] ;");

// Which is smaller?

int minMaxEdges;

System.out.println("(2)- Which is smaller?");

System.out.println("tmpMaxEdges"+Integer.toString(tmpMaxEdges)+" = maxEdges"+Integer.toString(maxEdges));

if (tmpMaxEdges < maxEdges)

minMaxEdges = tmpMaxEdges;

else

minMaxEdges = maxEdges;

System.out.println("minMaxEdges"+Integer.toString(minMaxEdges));

// Reuse allocated edges.

System.out.println("(3)- Reuse allocated edges.");

for (int i = 0; i < minMaxEdges; i++) // this is the answer of (*)

this.edge = tmpEdge;

// Get new edges.

System.out.println("(4)- Get new edges.");

for (int i = minMaxEdges; i < maxEdges; i++)

this.edge = new Edge();

// Fix point array.

System.out.println("(5)- Fix point array.");

RealPoint tmpPoint[] = point;

point = new RealPoint[nPoints];

// Which is smaller?

System.out.println("(6)- Which is smaller?");

int minPoints;

if (nPoints < this.nPoints)

minPoints = nPoints;

else

minPoints = this.nPoints;

// Reuse allocated points.

System.out.println("(7)- Reuse allocated points.");

for (int i = 0; i < minPoints; i++)

this.point = tmpPoint;

// Get new points.

System.out.println("(8)- Get new points.");

for (int i = minPoints; i < nPoints; i++)

this.point = new RealPoint();

this.nPoints = nPoints;

System.out.println("==> (nPoints="+Integer.toString(nPoints)+",maxEdges="+Integer.toString(maxEdges)+")");

System.out.println("== public void setNPoints(int nPoints) ==");

}

/*

* Generates a set of random points to triangulate.

*/

public void randomPoints(RealWindow w) {

System.out.println("** public void randomPoints(RealWindow w) **");

point[0].x = 0.3f;

point[0].y = 0.2f;

point[1].x = 0.9f;

point[1].y = 0.1f;

point[2].x = 0.5f;

point[2].y = 0.3f;

point[3].x = 0.2f;

point[3].y = 0.5f;

for (int i = 0; i < nPoints; i++)

{

//point.x = (float)Math.random() * w.xMax();

//point.y = (float)Math.random() * w.yMax();

System.out.println("point["+Integer.toString(i)+"]=("+

Float.toString(point.x)+","+

Float.toString(point.y)+")");

}

nEdges = 0;

System.out.println("nEdges="+Integer.toString(nEdges));

System.out.println("== public void randomPoints(RealWindow w) ==");

}

/*

* Copies a set of points.

*/

public void copyPoints(Triangulation t) {

System.out.println("(3)- Copy points to the array t.point[]");

System.out.println("\tpublic void copyPoints(Triangulation t) **");

int n;

if (t.nPoints < nPoints)

n = t.nPoints;

else

n = nPoints;

for (int i = 0; i < n; i++) {

//We can only copy the nPoints that allows this triangulation

//The copy will only concern n=min(this.nPoints,t.Npoints)

point.x = t.point.x;

point.y = t.point.y;

}

nEdges = 0; //I think a triangulation should be necessary after this copy...

//System.out.println("== public void copyPoints(Triangulation t) ==");

}

void addTriangle(int s, int t, int u) {

//System.out.println("** void addTriangle(int s, int t, int u) **");

addEdge(s, t);//s, t and u are used as if they were vertices, but they are int!!!

addEdge(t, u);//NO, they are the n掳 of vertices!!!

addEdge(u, s);

/*System.out.print("\n====>addTriangle:("+Integer.toString(s)+","+Integer.toString(t)+")");

System.out.print(";("+Integer.toString(t)+","+Integer.toString(u)+")");

System.out.println(";("+Integer.toString(u)+","+Integer.toString(s)+")");*/

//System.out.println("== void addTriangle(int s, int t, int u) ==");

}

public int addEdge(int s, int t) {

//System.out.print("==>addEdge:("+Integer.toString(s)+","+Integer.toString(t)+",-1,-1)\n");

return addEdge(s, t, Undefined, Undefined);

}

/*

* Adds an edge to the triangulation. Store edges with lowest

* vertex first (easier to debug and makes no other difference).

*/

public int addEdge(int s, int t, int l, int r) {

System.out.println("\tpublic int addEdge(s="+Integer.toString(s)+",t="+Integer.toString(t)+",l="+Integer.toString(l)+",r="+Integer.toString(r)+")");

//System.out.println("(*) Init (s="+Integer.toString(s)+",t="+Integer.toString(t)+",l="+Integer.toString(l)+",r="+Integer.toString(r)+")");

int e;

// Add edge if not already in the triangulation.

e = findEdge(s, t);

if (e == Undefined){

System.out.println("\t\t"+Integer.toString(e)+"=findEdge("+Integer.toString(s)+", "+Integer.toString(t)+");");

if (s < t) {

System.out.println("\t\ts="+Integer.toString(s)+"<t="+Integer.toString(t));

edge[nEdges].s = s;

edge[nEdges].t = t;

edge[nEdges].l = l;

edge[nEdges].r = r;

System.out.println("\t\t===>edge["+Integer.toString(nEdges)+"]=("+Integer.toString(s)+","+Integer.toString(t)+","+Integer.toString(l)+","+Integer.toString(r)+")");

System.out.println("\t\t===>nEdges="+Integer.toString(nEdges+1));

return nEdges++;

//I don't understand the rule of faces l (left) and r (right)

}

else {

System.out.println("\t\ts="+Integer.toString(s)+"> t="+Integer.toString(t));

edge[nEdges].s = t;

edge[nEdges].t = s;

edge[nEdges].l = r;

edge[nEdges].r = l;

System.out.println("\t\t===>edge["+Integer.toString(nEdges)+"]=("+Integer.toString(s)+","+Integer.toString(t)+","+Integer.toString(r)+","+Integer.toString(l)+")");

System.out.println("\t\t===>nEdges="+Integer.toString(nEdges+1)+" inversion of l && r");

return nEdges++;

}

}

else{

System.out.println("\t\t"+Integer.toString(e)+" = findEdge("+Integer.toString(s)+", "+Integer.toString(t)+");");

System.out.println("\t\t===>return Undefined;");

return Undefined; //Why when the edge(s,t) is not defined, we return Undefined?

}

}

public int findEdge(int s, int t) {

//System.out.println("\t\t\tpublic int findEdge(int s="+Integer.toString(s)+", int t="+Integer.toString(t)+") **");

boolean edgeExists = false;

int i;

for (i = 0; i < nEdges; i++)

if (edge.s == s && edge.t == t ||

edge.s == t && edge.t == s) {

edgeExists = true;

break;

}

if (edgeExists){

//System.out.println("\t\t\tedgeExists=true => i="+Integer.toString(i));

return i;

}

else{

//System.out.println("\t\t\tedgeExists=false => i=Undefined="+Integer.toString(Triangulation.Undefined));

return Undefined;

}

}

/*

* Update the left face of an edge.

* For what matter do we need to update the left face of an edge?

*/

public void updateLeftFace(int eI, int s, int t, int f) {

//System.out.println("** public void updateLeftFace(int eI, int s, int t, int f) **");

if (! ( (edge[eI].s == s && edge[eI].t == t) ||

(edge[eI].s == t && edge[eI].t == s)))

Panic.panic("updateLeftFace: adj. matrix and edge table mismatch");

if (edge[eI].s == s && edge[eI].l == Triangulation.Undefined){

edge[eI].l = f;

System.out.println("\t\t\tLEFT edge["+Integer.toString(eI)+"]=("+Integer.toString(s)+","+Integer.toString(t)+","+Integer.toString(edge[eI].l)+","+Integer.toString(edge[eI].r)+")");

}

else

if (edge[eI].t == s && edge[eI].r == Triangulation.Undefined){

edge[eI].r = f;

System.out.println("\t\t\tRIGHT edge["+Integer.toString(eI)+"]=("+Integer.toString(s)+","+Integer.toString(t)+","+Integer.toString(edge[eI].l)+","+Integer.toString(edge[eI].r)+")");

}

else

Panic.panic("updateLeftFace: attempt to overwrite edge info");

//System.out.println("== public void updateLeftFace(int eI, int s, int t, int f) ==");

}

public void draw(RealWindowGraphics rWG, Color pC, Color eC) {

drawPoints(rWG, pC);

drawEdges(rWG, eC);

}

public void drawPoints(RealWindowGraphics rWG, Color c) {

for (int i = 0; i < nPoints; i++)

rWG.drawPoint(point, c);

}

public void drawEdges(RealWindowGraphics rWG, Color c) {

for (int i = 0; i < nEdges; i++)

drawEdge(rWG, edge, c);

}

public void drawEdge(RealWindowGraphics rWG, Edge e, Color c) {

rWG.drawLine(point[e.s], point[e.t], c);

}

public void print(PrintStream p) {//for what reason did we use that method?

printPoints(p);

printEdges(p);

}

public void printPoints(PrintStream p) {

for (int i = 0; i < nPoints; i++)

{p.println(String.valueOf(point.x) + " " + String.valueOf(point.y));

System.out.println(String.valueOf(point.x) + " " + String.valueOf(point.y));}

}

public void printEdges(PrintStream p) {

for (int i = 0; i < nEdges; i++)

{p.println(String.valueOf(edge.s) + " " + String.valueOf(edge.t));

System.out.println(String.valueOf(edge.s) + " " + String.valueOf(edge.t));

}

}

}

/*

* Rectangle class. Need rectangles for window to viewport mapping.

*/

class RealRectangle {

RealPoint ll;

RealPoint ur;

RealRectangle() { }

RealRectangle (RealRectangle r) {

this.ll = new RealPoint(r.ll);//What's he doing? the RealPoint r.ll isn't already created!

this.ur = new RealPoint(r.ur);//likewise...NO, JE DELIRE!!! It can work proprely... Ashool

}

RealRectangle (RealPoint ll, RealPoint ur) {

this.ll = new RealPoint(ll);

this.ur = new RealPoint(ur);

}

RealRectangle(float xMin, float yMin, float xMax, float yMax) {

this.ll = new RealPoint(xMin, yMin);

this.ur = new RealPoint(xMax, yMax);

}

public float width() { return ur.x() - ll.x(); }

public float height() { return ur.y() - ll.y(); }

public RealPoint ll() { return ll; }

public RealPoint ur() { return ur; }

public float xMin() { return ll.x; }

public float yMin() { return ll.y; }

public float xMax() { return ur.x; }

public float yMax() { return ur.y; }

}

/*

* A window is essentially a rectangle.

* I don't see the utility of creating that class?

*/

class RealWindow extends RealRectangle {

RealWindow() {}

RealWindow(float xMin, float yMin, float xMax, float yMax) {

super(xMin, yMin, xMax, yMax);

}

RealWindow(RealWindow w){

super(w.ll(), w.ur());

}

}

/*

* RealWindowGraphics class. Has a window, a viewport and a

* graphics context into which to draw. The graphics context

* is only set after calls to repaint result in calls to update.

* Contains drawing operations, drawTriangle for example, needed

* elsewhere.

*/

class RealWindowGraphics {

RealWindow w = null;// window

Dimension v = null;// viewport => Why dimension is called viewport?

Graphics g = null;

float scale = 1.0f;

static final float realPointRadius = 0.04f;

static final int pixelPointRadius = 4;

static final int halfPixelPointRadius = 2;

RealWindowGraphics(RealWindow w) {

this.w = new RealWindow(w);

}

RealWindowGraphics(RealWindow w, Dimension d, Graphics g) {

this.w = new RealWindow(w);

this.v = new Dimension(d.width, d.height);

this.g = g;

calculateScale();

}

public void setWindow(RealWindow w) {

this.w = new RealWindow(w);

calculateScale();

}

public void setViewport(Dimension d) {

this.v = new Dimension(d.width, d.height);

calculateScale();

}

public void setGraphics(Graphics g) {

this.g = g;

}

public Graphics getGraphics(Graphics g) {// Is he kidding with me?

return g;

}

public void calculateScale() {

float sx, sy;

sx = v.width / w.width();

sy = v.height / w.height();

if (sx < sy)

scale = sx;

else

scale = sy;

}

public void drawTriangle(RealPoint p1,

RealPoint p2,

RealPoint p3,

Color c) {

drawLine(p1, p2, c);

drawLine(p2, p3, c);

drawLine(p3, p1, c);

}

public void drawLine(RealPoint p1, RealPoint p2, Color c) {

int x1, y1, x2, y2;

g.setColor(c);

x1 = (int)(p1.x() * scale);

y1 = (int)(p1.y() * scale);

x2 = (int)(p2.x() * scale);

y2 = (int)(p2.y() * scale);

g.drawLine(x1, y1, x2, y2);

}

public void drawPoint(RealPoint p, Color c) {

g.setColor(c);

/*g.fillOval((int)(scale * p.x()) - halfPixelPointRadius,

(int)(scale * p.y()) - halfPixelPointRadius,

pixelPointRadius, pixelPointRadius);*/

g.fillRect((int)(scale * p.x()) - halfPixelPointRadius,

(int)(scale * p.y()) - halfPixelPointRadius,

pixelPointRadius, pixelPointRadius);

}

public void drawCircle(Circle circle, Color c) {

drawCircle(circle.center().x(), circle.center().y(), circle.radius(), c);

}

public void drawCircle(RealPoint p, float r, Color c) {

drawCircle(p.x(), p.y(), r, c);

}

public void drawCircle(float x, float y, float r, Color c) {

g.setColor(c);

g.drawOval((int)(scale * (x - r)), (int)(scale * (y - r)),

(int)(2.0f * r * scale), (int)(2.0f * r * scale));

}

public void fillCircle(float x, float y, float r, Color c) {

g.setColor(c);

g.fillOval((int)(scale * (x - r)), (int)(scale * (y - r)),

(int)(2.0f * r * scale), (int)(2.0f * r * scale));

}

}

/*

* AlgorithmUIHeading class. Provides a heading for part of the user

* interface.

*/

class AlgorithmUIHeading extends Panel {

public AlgorithmUIHeading() {

// Headings.

setLayout(new GridLayout(0,7));

add(new Label("Algorithm", Label.LEFT));

add(new Label("Run", Label.LEFT));

add(new Label("Points", Label.LEFT));

add(new Label("Triangles", Label.LEFT));

add(new Label("Circles", Label.LEFT));

add(new Label("Points", Label.LEFT));

add(new Label("Pause (mS)", Label.LEFT));

}

}

/*

* TriangulationCanvas class. Each of the triangulation algorithms

* needs a canvas to draw into.

*/

class TriangulationCanvas extends Canvas {

Triangulation t;

RealWindowGraphics rWG;// Does the actual drawing thanks to rWG.g

boolean needToClear = false;

boolean newPoints = false;

TriangulationAlgorithm alg;// The algorithm which uses this canvas.

TriangulationCanvas(Triangulation t,

RealWindow w,

TriangulationAlgorithm alg) {

this.t = t;

rWG = new RealWindowGraphics(w);

this.alg = alg;

}

public Insets insets() {

return new Insets(2,10,2,15);//this is spacing in pixel used for some thing I don't understand?

}

public void paint(Graphics g) {

if (needToClear) {

g.clearRect(0, 0, size().width, size().height);

needToClear = false;

}

g.drawRect(0, 0, size().width-1, size().height-1);

rWG.setGraphics(g);

rWG.setViewport(size());

alg.draw(rWG, t);

}

public void update(Graphics g) {

paint(g);

}

}

/*

* AlgorithmUI class. Each algorithm has a set of user interface

* controls. This class provides them.

*/

class AlgorithmUI extends Panel {

TextField nPointsTextField;

Checkbox animateCheckBox[];

Checkbox runCheckBox;

TextField pauseTextField;

TriangulationAlgorithm algorithm; // Algorithm which uses this UI.

public AlgorithmUI(TriangulationAlgorithm algorithm,

String label, int nPoints, int pause) {

this.algorithm = algorithm;

// One set of controls per algorithm.

setLayout(new GridLayout(0,7));

add(new Label(label, Label.LEFT));

add(runCheckBox = new Checkbox(null, null, true));

add(nPointsTextField = new TextField(String.valueOf(nPoints), 5));

animateCheckBox = new Checkbox[AnimateControl.nEntities];

animateCheckBox[AnimateControl.triangles] = new Checkbox(null, null, true);

add(animateCheckBox[AnimateControl.triangles]);//I don't see what's AnimateControl?

animateCheckBox[AnimateControl.circles] = new Checkbox(null, null, true);

add(animateCheckBox[AnimateControl.circles]);

animateCheckBox[AnimateControl.points] = new Checkbox(null, null, true);

add(animateCheckBox[AnimateControl.points]);

pauseTextField = new TextField(String.valueOf(pause), 5);

add(pauseTextField);

}

public void setAlgorithm(TriangulationAlgorithm algorithm) {

this.algorithm = algorithm;

}

// Gets the current value in a text field.

int getValue(TextField tF) {

int i;

try {

i = Integer.valueOf(tF.getText()).intValue();

} catch (java.lang.NumberFormatException e) {

i = 0;

}

return i;

}

public boolean handleEvent(Event evt) {

if (evt.id == Event.ACTION_EVENT) {

if (evt.target == runCheckBox) {

algorithm.control().setRun(((Boolean)evt.arg).booleanValue());

return true;

} else if (evt.target == animateCheckBox[AnimateControl.triangles]) {

algorithm.control().setAnimate(AnimateControl.triangles,

((Boolean)evt.arg).booleanValue());

return true;

} else if (evt.target == animateCheckBox[AnimateControl.circles]) {

algorithm.control().setAnimate(AnimateControl.circles,

((Boolean)evt.arg).booleanValue());

return true;

} else if (evt.target == animateCheckBox[AnimateControl.points]) {

algorithm.control().setAnimate(AnimateControl.points,

((Boolean)evt.arg).booleanValue());

return true;

} else if (evt.target == pauseTextField) {

algorithm.control().setPause(getValue(pauseTextField));

return true;

} else if (evt.target == nPointsTextField) {

algorithm.control().nPoints = getValue(nPointsTextField);

return true;

}

}

return false;

}

}

/*

* AnimateControl class. Each algorithm animation has various entities

* which can be displayed. This class provides the state which controls

* what is being displayed. It is manipulated by AlgorithmUI and

* accessed by the animation routines in each algorithm.

*/

class AnimateControl {

TriangulationAlgorithm triAlg;

static final int automatic = 0;

static final int manual = 1;

int animateMode = automatic;

int pause = 10;

static final int algorithm = 0;//static final <=> const in C/C++

static final int triangles = 1;

static final int points = 2;

static final int circles = 3;

static final int nEntities = 4;//It means we have only 3 algorithms (*)

boolean run;

boolean animate[];

int nPoints;

AnimateControl(TriangulationAlgorithm algorithm) {

triAlg = algorithm;

animate = new boolean[nEntities];

for (int i = 0; i < nEntities; i++)//(*)

animate = true;

run = true;

}

AnimateControl(TriangulationAlgorithm algorithm, int nPoints) {

this(algorithm);//instruction to understand?

this.nPoints = nPoints;

}

public void setAnimate(int entity, boolean v) {

animate[entity] = v;

if (!v)

triAlg.canvas().needToClear = true;

}

public boolean animate(int entity) {

return animate[entity];

}

public int mode() {

return animateMode;

}

public void setManualAnimateMode() {

animateMode = manual;

}

public void setAutomaticAnimateMode() {

animateMode = automatic;

}

public int getPause() {

return pause;

}

public void setPause(int p) {

pause = p;

}

public int getNPoints() {

return nPoints;

}

public void setNPoints(int n) {

nPoints = n;

}

public void setRun(boolean v) {

run = v;

}

public boolean getRun() {

return run;

}

}

/*

* TriangulationAlgorithm class. Absract. Superclass for

* actual algorithms. Has several abstract function members -

* including the triangulation member which actually computes

* the triangulation.

*/

abstract class TriangulationAlgorithm {

String algName;

TriangulationCanvas triCanvas;

AnimateControl aniControl;

AlgorithmUI algorithmUI;

RealWindow w;

RealWindowGraphics rWG;

// Variables and constants for animation state.

final int nStates = 5;

boolean state[] = new boolean[nStates];

static final int triangulationState = 0;

static final int pointState = 1;

static final int triangleState = 2;

static final int insideState = 4;

static final int edgeState = 5;

public TriangulationAlgorithm(Triangulation t, RealWindow w,

String name, int nPoints) {

algName = name;

aniControl = new AnimateControl(this, nPoints);

algorithmUI = new AlgorithmUI(this, name, nPoints, aniControl.getPause());

triCanvas = new TriangulationCanvas(t, w, this);

for (int s = 0; s < nStates; s++)

state[s] = false;

triCanvas.needToClear = true;

}

public void setCanvas(TriangulationCanvas tc) {

triCanvas = tc;

}

public AnimateControl control() {

return aniControl;

}

public AlgorithmUI algorithmUI() {

return algorithmUI;

}

public TriangulationCanvas canvas() {

return triCanvas;

}

public void setAlgorithmState(int stateVar, boolean value) {

state[stateVar] = value;

}

public void pause() {

if (aniControl.mode() == AnimateControl.automatic)

try {

wait(aniControl.getPause());

} catch (InterruptedException e){}

else

try {wait();} catch (InterruptedException e){}

}

public void animate(int state) {

if ((aniControl.animate(AnimateControl.triangles) ||

aniControl.animate(AnimateControl.circles)) &&

state == triangulationState)

triCanvas.needToClear = true;

setAlgorithmState(state, true);

triCanvas.repaint();

pause();

setAlgorithmState(state, false);

}

public void reset() {

for (int s = 0; s < nStates; s++)

state[s] = false;

triCanvas.needToClear = true;

}

public synchronized void nextStep() {

notify();

//System.out.println("public synchronized void nextStep() { notify();}");

}

abstract public void triangulate(Triangulation t);//synchronized

abstract public void draw(RealWindowGraphics rWG, Triangulation t);//synchronized

}

/*

* QuarticAlgorithm class. O(n^4) algorithm. The most brute-force

* of the algorithms.

*/

class QuarticAlgorithm extends TriangulationAlgorithm {

int i, j, k, l;

Circle c = new Circle();

final static String algName = "O(n^4)";

public QuarticAlgorithm(Triangulation t, RealWindow w, int nPoints) {

super(t, w, algName, nPoints);

}

public void reset() {

i = j = k = l = 0;

super.reset();

}

public void draw(RealWindowGraphics rWG, Triangulation t) {

if (state[triangleState]) {

if (aniControl.animate(AnimateControl.triangles))

rWG.drawTriangle(t.point, t.point[j], t.point[k], Color.green);

if (aniControl.animate(AnimateControl.circles))

rWG.drawCircle(c, Color.green);

} else if (state[pointState]) {

if (aniControl.animate(AnimateControl.points))

rWG.drawPoint(t.point[l], Color.orange);

} else if (state[insideState]) {

if (aniControl.animate(AnimateControl.triangles))

rWG.drawTriangle(t.point, t.point[j], t.point[k], Color.red);

if (aniControl.animate(AnimateControl.circles))

rWG.drawCircle(c, Color.red);

if (aniControl.animate(AnimateControl.points))

rWG.drawPoint(t.point[l], Color.red);

} else if (state[triangulationState]) {

t.draw(rWG, Color.black, Color.black);

} else {

t.draw(rWG, Color.black, Color.black);

}

}

public synchronized void triangulate(Triangulation t) {

boolean pointFree;

int n = t.nPoints;

RealPoint p[] = t.point;

for (i = 0; i < n-2; i++)

for (j = i + 1; j < n-1; j++)

if (j != i)

for (k = j + 1; k < n; k++)

if (k != i && k != j)

{

c.circumCircle(p, p[j], p[k]);

animate(triangleState);

pointFree = true;

for (l = 0; l < n; l++)

if (l != i && l != j && l != k) {

animate(pointState);

if (c.inside(p[l])) {

animate(insideState);

pointFree = false;

break;

}

}

if (pointFree)

t.addTriangle(i, j, k);

animate(triangulationState);

}

}

}

/*

* CubicAlgorithm class. O(n^3) algorithm.

*/

class CubicAlgorithm extends TriangulationAlgorithm {

int s, t, u, i;

Circle bC = new Circle();

final static String algName = "O(n^3)";

int nFaces;

public CubicAlgorithm(Triangulation t, RealWindow w, int nPoints) {

super(t, w, algName, nPoints);

}

public void reset() {

nFaces = 0;

triCanvas.needToClear = true;

super.reset();

}

public void draw(RealWindowGraphics rWG, Triangulation tri) {

if (state[triangleState]) {

if (aniControl.animate(AnimateControl.triangles)) {

rWG.drawTriangle(tri.point[s], tri.point[t], tri.point,

Color.green);

rWG.drawLine(tri.point[s], tri.point[t], Color.blue);

}

if (aniControl.animate(AnimateControl.circles))

rWG.drawCircle(bC, Color.green);

} else if (state[pointState]) {

if (aniControl.animate(AnimateControl.points))

rWG.drawPoint(tri.point, Color.orange);

} else if (state[insideState]) {

if (aniControl.animate(AnimateControl.triangles)) {

rWG.drawTriangle(tri.point[s], tri.point[t], tri.point, Color.red);

rWG.drawLine(tri.point[s], tri.point[t], Color.blue);

}

if (aniControl.animate(AnimateControl.circles))

rWG.drawCircle(bC, Color.red);

if (aniControl.animate(AnimateControl.points))

rWG.drawPoint(tri.point[s], Color.red);

} else if (state[triangulationState]) {

tri.draw(rWG, Color.black, Color.black);

} else {

tri.draw(rWG, Color.black, Color.black);

}

}

public synchronized void triangulate(Triangulation tri) {

System.out.println("(4)- triangulate O(n^3)");

System.out.println("\tpublic synchronized void triangulate(Triangulation tri) **");

int seedEdge, currentEdge;

int nFaces;

Int s, t;

// Initialise.

System.out.println("(4.1)- Initialise.");

System.out.println("\tnFaces=0, s=t=0.");

nFaces = 0;

s = new Int();

t = new Int();

// Find closest neighbours and add edge to triangulation.

System.out.println("(4.2)- Find closest neighbours and add edge to triangulation.");

System.out.println("\tfindClosestNeighbours(tri.point, "+Integer.toString(tri.nPoints)+","+Integer.toString(s.getValue())+","+Integer.toString(t.getValue())+");");

findClosestNeighbours(tri.point, tri.nPoints, s, t);

// Create seed edge and add it to the triangulation.

//System.out.println("\t###s="+Integer.toString(s.getValue())+",t="+Integer.toString(t.getValue())+")");

System.out.println("\t###> seedEdge=?=tri.addEdge("+Integer.toString(s.getValue())+

","+Integer.toString(t.getValue())+","+

Integer.toString(Triangulation.Undefined)+","+

Integer.toString(Triangulation.Undefined)+")");

seedEdge = tri.addEdge(s.getValue(), t.getValue(),

Triangulation.Undefined,

Triangulation.Undefined);

System.out.println("\t###> seedEdge="+Integer.toString(seedEdge)+

" = tri.addEdge("+Integer.toString(s.getValue())+

","+Integer.toString(t.getValue())+","+

Integer.toString(Triangulation.Undefined)+","+

Integer.toString(Triangulation.Undefined)+")");

currentEdge = 0;

while (currentEdge < tri.nEdges) {

System.out.println("\twhile (currentEdge=" + Integer.toString(currentEdge) +

"< tri.nEdges=" + Integer.toString(tri.nEdges) + ")");

if (tri.edge[currentEdge].l == Triangulation.Undefined) {

System.out.println("\t\tLEFT tri.edge[" + Integer.toString(currentEdge) +

"].l == Triangulation.Undefined");

System.out.println("\t\tcompleteFacet(" + Integer.toString(currentEdge) +

", tri, " + Integer.toString(nFaces) + ")");

completeFacet(currentEdge, tri, nFaces);

animate(triangulationState);

}

if (tri.edge[currentEdge].r == Triangulation.Undefined) {

System.out.println("\t\tRIGHT tri.edge[" + Integer.toString(currentEdge) +

"].r == Triangulation.Undefined");

System.out.println("\t\tcompleteFacet(" + Integer.toString(currentEdge) +

", tri, " + Integer.toString(nFaces) + ")");

completeFacet(currentEdge, tri, nFaces);

animate(triangulationState);

}

currentEdge++;

}

for (int m = 0; m < tri.nEdges; m++) {

System.out.println("=>edge[" + Integer.toString(m) + "]=(" +

Integer.toString(tri.edge[m].s) + "," +

Integer.toString(tri.edge[m].t) + "," +

Integer.toString(tri.edge[m].l) + "," +

Integer.toString(tri.edge[m].r) + ")");

}

}

// Find the two closest points.

public void findClosestNeighbours(RealPoint p[], int nPoints,

Int u, Int v) {

/*System.out.println("\t\tfindClosestNeighbours(RealPoint p[], int "+

Integer.toString(nPoints)+","+

Integer.toString(u.getValue())+","+Integer.toString(v.getValue())+")");*/

int i, j;

float d, min;

int s1, t1;

s1 = t1 = 0;

min = Float.MAX_VALUE;

for (i = 0; i < nPoints-1; i++)

for (j = i+1; j < nPoints; j++)

{

d = p.distanceSq(p[j]);

if (d < min)

{

s1 = i;

t1 = j;

min = d;

}

}

u.setValue(s1);

v.setValue(t1);

System.out.println("\t\t==>(u="+Integer.toString(u.getValue())+",v="+Integer.toString(v.getValue())+")");

}

/*

* Complete a facet by looking for the circle free point to the left

* of the edge "e_i". Add the facet to the triangulation.

*

* This function is a bit long and may be better split.

*/

public void completeFacet(int eI, Triangulation tri, int nFaces) {

float cP;

boolean pointFree;

Edge e[] = tri.edge;

RealPoint p[] = tri.point;

System.out.println("\t\t\tCache s and t.");

// Cache s and t.

if (e[eI].l == Triangulation.Undefined) {

s = e[eI].s;

t = e[eI].t;

System.out.println("\t\t\t e[" + Integer.toString(eI) + "].l==-1");

System.out.println("\t\t\t (s=" + Integer.toString(s) + ",t=" +

Integer.toString(t) + ")");

}

else if (e[eI].r == Triangulation.Undefined) {

s = e[eI].t;

t = e[eI].s;

System.out.println("\t\t\t e[" + Integer.toString(eI) + "].r==-1");

System.out.println("\t\t\t (s=" + Integer.toString(s) + ",t=" +

Integer.toString(t) + ")");

}

else {

// Edge already completed.

System.out.println("\t\t\t Edge " + Integer.toString(eI) +

" already completed.");

return;

}

// Find point free circumcircle to the left.

System.out.println("\t\t\tFind point free circumcircle to the left.");

for (u = 0; u < tri.nPoints; u++) {

System.out.println("\t\t\t (s=" + Integer.toString(s) + ",t=" +

Integer.toString(t) + ",u=" + Integer.toString(u) +

")");

if (u != s && u != t) {

System.out.println(

"\t\t\t ==>(u != s && u != t) and now the crossProduct.");

if (Vector.crossProduct(p[s], p[t], p) > 0.0) {

System.out.println("\t\t\tVector.crossProduct(p[" +

Integer.toString(s) + "], p[" + Integer.toString(t) +

"], p[" + Integer.toString(u) + "]) > 0.0)");

bC.circumCircle(p[s], p[t], p);

animate(triangleState);

pointFree = true;

for (i = 0; i < tri.nPoints; i++) {

System.out.println("\t\t\ti=" + Integer.toString(i));

if (i != s && i != t && i != u) {

System.out.println("\t\t\t(s=" + Integer.toString(s) +

",t=" + Integer.toString(t) + ",u=" +

Integer.toString(u) + ",i=" +

Integer.toString(i) + ")");

animate(pointState);

cP = Vector.crossProduct(p[s], p[t], p);

if (cP > 0.0)

if (bC.inside(p)) {

animate(insideState);

System.out.println("\t\t\t==>p[" + Integer.toString(i) +

"] is inside");

pointFree = false;

break;

}

}

}

animate(triangulationState);

if (pointFree)

break;

}

}

}

// Add new triangle or update edge info if s-t is on hull.

System.out.println(

"\t\t\tAdd new triangle or update edge info if s-t is on hull.");

System.out.println("\t\t\t (u=" + Integer.toString(u) + ",tri.nPoints=" +

Integer.toString(tri.nPoints) + ")");

if (u < tri.nPoints) {

System.out.println("\t\t\t ==>u=" + Integer.toString(u) +

"<tri.nPoints=" + Integer.toString(tri.nPoints));

int bP = u;

System.out.println("\t\t\t bP=" + Integer.toString(bP));

// Update face information of edge being completed.

System.out.println(

"\t\t\t Update face information of edge being completed.");

System.out.println("\t\t\t tri.updateLeftFace(eI=" + Integer.toString(eI) +

"," + " s=" + Integer.toString(s) + "," + " t=" +

Integer.toString(t) + ", nFaces=" +

Integer.toString(nFaces) + ")");

tri.updateLeftFace(eI, s, t, nFaces);

System.out.println("\t\t\t nFaces=" + Integer.toString(nFaces + 1));

nFaces++;

System.out.println("\t\t\t ==>nFaces++; SO nFaces="+Integer.toString(nFaces));

// Add new edge or update face info of old edge.

System.out.println("\t\t\tAdd new edge or update face info of old edge.");

System.out.println("\t\t\t eI=?=tri.findEdge(bP=" + Integer.toString(bP) +

", s=" + Integer.toString(s) + ")");

eI = tri.findEdge(bP, s);

if (eI == Triangulation.Undefined) {

// New edge.

System.out.println("\t\t\tNew edge");

eI = tri.addEdge(bP, s, nFaces, Triangulation.Undefined);

}

else {

// Old edge.

System.out.println("\t\t\tOld edge");

System.out.println("\t\t\ttri.updateLeftFace(eI=" +

Integer.toString(eI) + ", bP=" + Integer.toString(bP) +

",s,nFaces=" + Integer.toString(nFaces) + ")");

tri.updateLeftFace(eI, bP, s, nFaces);

}

// Add new edge or update face info of old edge.

System.out.println("\t\t\t eI=?=tri.findEdge(t=" + Integer.toString(t) +

",bP=" + Integer.toString(bP) + ")");

eI = tri.findEdge(t, bP);

if (eI == Triangulation.Undefined) {

// New edge.

System.out.println("\t\t\tNew edge");

eI = tri.addEdge(t, bP, nFaces, Triangulation.Undefined);

}

else {

// Old edge.

System.out.println("\t\t\tOld edge");

System.out.println("\t\t\t tri.updateLeftFace(eI=" +

Integer.toString(eI) + "," + " s=" +

Integer.toString(s) + "," + " t, nFaces=" +

Integer.toString(nFaces) + ")");

tri.updateLeftFace(eI, t, bP, nFaces);

}

}

else {

System.out.println("\t\t\ttri.updateLeftFace(eI=" +

Integer.toString(eI) + ", s=" + Integer.toString(s) +

",t=" + Integer.toString(s) +

",Triangulation.Universe)");

tri.updateLeftFace(eI, s, t, Triangulation.Universe);

}

}

}

/*

* QuadraticAlgorithm class. O(n^2) algorithm.

*/

class QuadraticAlgorithm extends TriangulationAlgorithm {

int s, t, u, bP;

Circle bC = new Circle();

final static String algName = "O(n^2)";

int nFaces;

public QuadraticAlgorithm(Triangulation t, RealWindow w, int nPoints) {

super(t, w, algName, nPoints);

}

public void reset() {

nFaces = 0;

triCanvas.needToClear = true;

super.reset();

}

public void draw(RealWindowGraphics rWG, Triangulation tri) {

if (state[triangleState]) {

if (aniControl.animate(AnimateControl.triangles)) {

rWG.drawTriangle(tri.point[s], tri.point[t], tri.point[bP],

Color.green);

rWG.drawLine(tri.point[s], tri.point[t], Color.blue);

}

if (aniControl.animate(AnimateControl.circles))

rWG.drawCircle(bC, Color.green);

} else if (state[pointState]) {

if (aniControl.animate(AnimateControl.points))

rWG.drawPoint(tri.point, Color.orange);

} else if (state[insideState]) {

if (aniControl.animate(AnimateControl.triangles)) {

rWG.drawTriangle(tri.point[s], tri.point[t], tri.point[bP], Color.red);

rWG.drawLine(tri.point[s], tri.point[t], Color.blue);

}

if (aniControl.animate(AnimateControl.circles))

rWG.drawCircle(bC, Color.red);

if (aniControl.animate(AnimateControl.points))

rWG.drawPoint(tri.point[s], Color.red);

} else if (state[triangulationState]) {

tri.draw(rWG, Color.black, Color.black);

} else {

tri.draw(rWG, Color.black, Color.black);

}

}

public synchronized void triangulate(Triangulation tri) {

int seedEdge, currentEdge;

int nFaces;

Int s, t;

System.out.println("(4)- triangulate O(n^2)");

System.out.println("\tpublic synchronized void triangulate(Triangulation tri) **");

// Initialise.

System.out.println("(4.1)- Initialise.");

System.out.println("\tnFaces=0, s=t=0.");

nFaces = 0;

s = new Int();

t = new Int();

// Find closest neighbours and add edge to triangulation.

System.out.println("(4.2)- Find closest neighbours and add edge to triangulation.");

System.out.println("\tfindClosestNeighbours(tri.point, "+Integer.toString(tri.nPoints)+","+Integer.toString(s.getValue())+","+Integer.toString(t.getValue())+");");

findClosestNeighbours(tri.point, tri.nPoints, s, t);

// Create seed edge and add it to the triangulation.

System.out.println("\t###> seedEdge=?=tri.addEdge("+Integer.toString(s.getValue())+

","+Integer.toString(t.getValue())+","+

Integer.toString(Triangulation.Undefined)+","+

Integer.toString(Triangulation.Undefined)+")");

seedEdge = tri.addEdge(s.getValue(), t.getValue(),

Triangulation.Undefined,

Triangulation.Undefined);

System.out.println("\t###> seedEdge="+Integer.toString(seedEdge)+

" = tri.addEdge("+Integer.toString(s.getValue())+

","+Integer.toString(t.getValue())+","+

Integer.toString(Triangulation.Undefined)+","+

Integer.toString(Triangulation.Undefined)+")");

currentEdge = 0;

while (currentEdge < tri.nEdges) {

System.out.println("\twhile (currentEdge=" + Integer.toString(currentEdge) +

"< tri.nEdges=" + Integer.toString(tri.nEdges) + ")");

if (tri.edge[currentEdge].l == Triangulation.Undefined) {

System.out.println("\t\tLEFT tri.edge[" + Integer.toString(currentEdge) +

"].l == Triangulation.Undefined");

System.out.println("\t\tcompleteFacet(" + Integer.toString(currentEdge) +

", tri, " + Integer.toString(nFaces) + ")");

completeFacet(currentEdge, tri, nFaces);

animate(triangulationState);

}

if (tri.edge[currentEdge].r == Triangulation.Undefined) {

System.out.println("\t\tRIGHT tri.edge[" + Integer.toString(currentEdge) +

"].r == Triangulation.Undefined");

System.out.println("\t\tcompleteFacet(" + Integer.toString(currentEdge) +

", tri, " + Integer.toString(nFaces) + ")");

completeFacet(currentEdge, tri, nFaces);

animate(triangulationState);

}

currentEdge++;

}

for (int m = 0; m < tri.nEdges; m++) {

System.out.println("=>edge[" + Integer.toString(m) + "]=(" +

Integer.toString(tri.edge[m].s) + "," +

Integer.toString(tri.edge[m].t) + "," +

Integer.toString(tri.edge[m].l) + "," +

Integer.toString(tri.edge[m].r) + ")");

}

}

// Find the two closest points.

public void findClosestNeighbours(RealPoint p[], int nPoints,

Int u, Int v) {

int i, j;

float d, min;

int s, t;

s = t = 0;

min = Float.MAX_VALUE;

for (i = 0; i < nPoints-1; i++)

for (j = i+1; j < nPoints; j++)

{

d = p.distanceSq(p[j]);

if (d < min)

{

s = i;

t = j;

min = d;

}

}

u.setValue(s);

v.setValue(t);

}

/*

* Complete a facet by looking for the circle free point to the left

* of the edge "e_i". Add the facet to the triangulation.

*

* This function is a bit long and may be better split.

*/

public void completeFacet(int eI, Triangulation tri, int nFaces) {

float cP;

int i;

Edge e[] = tri.edge;

RealPoint p[] = tri.point;

// Cache s and t.

System.out.println("\t\t\t(a)Cache s and t.");

if (e[eI].l == Triangulation.Undefined) {

s = e[eI].s;

t = e[eI].t;

System.out.println("\t\t\t e[" + Integer.toString(eI) + "].l==-1");

System.out.println("\t\t\t (s=" + Integer.toString(s) + ",t=" +

Integer.toString(t) + ")");

}

else if (e[eI].r == Triangulation.Undefined) {

s = e[eI].t;

t = e[eI].s;

System.out.println("\t\t\t e[" + Integer.toString(eI) + "].r==-1");

System.out.println("\t\t\t (s=" + Integer.toString(s) + ",t=" +

Integer.toString(t) + ")");

}

else {

// Edge already completed.

System.out.println("\t\t\t (!a)Edge[" + Integer.toString(eI) +

"] already completed.");

return;

}

// Find a point on left of edge.

System.out.println("\t\t\t(b)Find a point on left of edge.");

for (u = 0; u < tri.nPoints; u++) {

System.out.println("\t\t\t u =" + Integer.toString(u));

if (u == s || u == t) {

System.out.println("\t\t\t =>continue (u =" + Integer.toString(u) +

"== s=" + Integer.toString(s)

+ " || u =" + Integer.toString(u)

+ "== t=" + Integer.toString(t) + ")");

continue;

}

if (Vector.crossProduct(p[s], p[t], p) > 0.0) {

System.out.println("\t\t\t ==>(s=" + Integer.toString(s) + ",t=" +

Integer.toString(t) + ",u=" + Integer.toString(u) +

")are distinct && crossProduct is OK.");

break;

}

}

// Find best point on left of edge.

System.out.println("\t\t\t(c)Find best point on left of edge.");

bP = u;

System.out.println("\t\t\t bP=u=" + Integer.toString(bP));

if (bP < tri.nPoints) {

System.out.println("\t\t\tbP=" + Integer.toString(bP) +

" < tri.nPoints=" + Integer.toString(tri.nPoints));

bC.circumCircle(p[s], p[t], p[bP]);

System.out.println("\t\t\tbC.circumCircle(p[s=" + Integer.toString(s) +

"], p[t=" + Integer.toString(t) + "], p[bP=" +

Integer.toString(bP) + "])");

animate(triangleState);

System.out.println("\t\t\tBegining from bP+1");

for (u = bP + 1; u < tri.nPoints; u++) {

System.out.println("\t\t\tu=" + Integer.toString(u));

if (u == s || u == t) {

System.out.println("\t\t\t=>continue (u =" + Integer.toString(u) +

"== s=" + Integer.toString(s)

+ " || u =" + Integer.toString(u)

+ "== t=" + Integer.toString(t) + ")");

continue;

}

animate(pointState);

System.out.println("\t\t\t=>cP = Vector.crossProduct(p[s=" +

Integer.toString(s)

+ "], p[t=" + Integer.toString(t) + "], p[u=" +

Integer.toString(u) + "])");

cP = Vector.crossProduct(p[s], p[t], p);

if (cP > 0.0)

if (bC.inside(p)) {

animate(insideState);

System.out.println("\t\t\t=>p inside of (p[s=" +

Integer.toString(s) + "], p[t=" +

Integer.toString(u) + "], p[bP=" +

Integer.toString(bP) + "])");

bP = u;

bC.circumCircle(p[s], p[t], p);

animate(triangleState);

}

}

}

// Add new triangle or update edge info if s-t is on hull.

System.out.println(

"\t\t\t(d)Add new triangle or update edge info if s-t is on hull.");

if (bP < tri.nPoints) {

// Update face information of edge being completed.

System.out.println(

"\t\t\t (d1)Update face information of edge being completed.");

System.out.println("\t\t\ttri.updateLeftFace(eI=" +

Integer.toString(eI) + ",s=" + Integer.toString(s) +

",t=" + Integer.toString(t) + ", nFaces=" +

Integer.toString(nFaces) + ")");

tri.updateLeftFace(eI, s, t, nFaces);

nFaces++;

System.out.println("\t\t\t==>nFaces++; SO nFaces="+Integer.toString(nFaces));

System.out.println("\t\t\tnFaces=" + Integer.toString(nFaces));

// Add new edge or update face info of old edge.

System.out.println(

"\t\t\t (d2)Add new edge or update face info of old edge.");

eI = tri.findEdge(bP, s);

if (eI == Triangulation.Undefined) {

// New edge.

System.out.println("\t\t\t(d2.1)New edge.");

//System.out.println("\t\t\t-1=tri.findEdge(bP="+Integer.toString(bP)+",s="+Integer.toString(s)+")");

eI = tri.addEdge(bP, s, nFaces, Triangulation.Undefined);

System.out.println("\t\t\teI="+Integer.toString(eI)+" = tri.addEdge(bP="+Integer.toString(bP)+",s="+Integer.toString(s)+", nFaces"+Integer.toString(nFaces)+",-1)");

}

else {

// Old edge.

System.out.println("\t\t\t(d2.1)Old edge.");

tri.updateLeftFace(eI, bP, s, nFaces);

System.out.println("\t\t\ttri.updateLeftFace(eI="+Integer.toString(eI)+

", bP="+Integer.toString(bP)+", s="+Integer.toString(s)+

", nFaces="+Integer.toString(nFaces)+")");

}

// Add new edge or update face info of old edge.

System.out.println(

"\t\t\t (d3)Add new edge or update face info of old edge.");

eI = tri.findEdge(t, bP);

if (eI == Triangulation.Undefined) {

// New edge.

System.out.println("\t\t\t(d3.1)New edge.");

eI = tri.addEdge(t, bP, nFaces, Triangulation.Undefined);

System.out.println("\t\t\teI="+Integer.toString(eI)+" = tri.addEdge(t="+Integer.toString(t)+",bP="+Integer.toString(bP)+", nFaces="+Integer.toString(nFaces)+",-1)");

}

else {

// Old edge.

System.out.println("\t\t\t(d2.1)Old edge.");

tri.updateLeftFace(eI, t, bP, nFaces);

System.out.println("\t\t\ttri.updateLeftFace(eI="+Integer.toString(eI)+

", t="+Integer.toString(t)+", bP="+Integer.toString(bP)+

", nFaces="+Integer.toString(nFaces)+")");

}

}

else {

System.out.println("\t\t\t(!d)tri.updateLeftFace(eI="+Integer.toString(eI)+", s="+Integer.toString(s)+", t="+Integer.toString(t)+", Triangulation.Universe)");

tri.updateLeftFace(eI, s, t, Triangulation.Universe);

}

}

}

/*

* AppletUI class. Provides most of the user interface for the applet.

*/

class AppletUI extends Panel {

AlgorithmUI AlgorithmUI[];

public AppletUI(TriangulationAlgorithm algorithm[]) {

Label l;

Panel p;

setLayout(new BorderLayout());

// Per algorithm controls.

p = new Panel();

p.setLayout(new GridLayout(0,1));

// Headings for algorithm controls.

p.add(new AlgorithmUIHeading());

// One set of controls per algorithm.

for (int i = 0; i < algorithm.length; i++)

p.add(algorithm.algorithmUI());

// Add panel to controls.

add("Center", p);

// Applet controls.

p = new Panel();

p.setLayout(new GridLayout(0,1));

p.add(new Button("Start"));

p.add(new Button("Stop"));

p.add(new Button("New"));

p.add(new Label("Step Mode", Label.CENTER));

Choice c = new Choice();

c.addItem("Auto");

c.addItem("Manual");

p.add(c);

// Add panel to controls.

add("East", p);

}

}

/*

* TriangulationApplet class. "Main Class"

*/

public class TriangulationApplet extends Applet implements Runnable {

Thread triangulateThread[];

int nPoints = 4;

Triangulation triangulation[];

TriangulationAlgorithm algorithm[];

RealWindow w;

RealWindowGraphics rWG;

AppletUI appUI;

public static final int On2 = 0;

public static final int On3 = 1;

public static final int On4 = 2;

Panel canvases;

static final int nAlgorithms = 3;

public void init() {

setBackground(Color.lightGray);

resize(600,350);

// Create a rectangle in the real plane for points.

w = new RealWindow(0.0f, 0.0f, 1.0f, 1.0f);

// Create array of triangulations, including random points.

triangulation = new Triangulation[nAlgorithms];

triangulation[0] = new Triangulation(nPoints);

triangulation[0].randomPoints(w);

for (int i = 1; i < nAlgorithms; i++) {

triangulation = new Triangulation(nPoints);

triangulation.copyPoints(triangulation[0]);

}

// Create an array of triangulation algorithms.

algorithm = new TriangulationAlgorithm[nAlgorithms];

algorithm[0] = new QuadraticAlgorithm(triangulation[0], w, nPoints);

algorithm[1] = new CubicAlgorithm(triangulation[1], w, nPoints);

algorithm[2] = new QuarticAlgorithm(triangulation[2], w, nPoints);

// Array of thread references (one for each algorithm).

triangulateThread = new Thread[nAlgorithms];

// Create user interface.

Panel heading = new Panel();

heading.setLayout(new BorderLayout());

heading.add("Center", new Label("The Triangulator", Label.CENTER));

Panel algHeadings = new Panel();

algHeadings.setLayout(new GridLayout(0, nAlgorithms));

for (int i = 0; i < nAlgorithms; i++)

algHeadings.add(new Label(algorithm.algName, Label.CENTER));

heading.add("South", algHeadings);

canvases = new Panel();

canvases.setLayout(new GridLayout(0, nAlgorithms));

for (int i = 0; i < nAlgorithms; i++)

canvases.add(algorithm.canvas());

setLayout(new BorderLayout());

add("North", heading);

add("Center", canvases);

appUI = new AppletUI(algorithm);

add("South", appUI);

}

/*

* Called for each algorithm thread when started.

*/

public void run() {

int algNo;

String threadName;

// Work out which algorithm to run from the thread name.

threadName = Thread.currentThread().getName();

algNo = Integer.parseInt(threadName.substring(threadName.length()-1));

algorithm[algNo].triangulate(triangulation[algNo]);

}

public Insets insets() {

// Right offset is more than left, due to Choice bug.

return new Insets(5,10,5,15);

}

/*

* Actually start the triangulation algorithms running.

*/

private synchronized void startTriangulate() {

for (int i = 0; i < triangulateThread.length; i++)

if (triangulateThread != null && triangulateThread.isAlive()) {

stop();

}

for (int i = 0; i < triangulateThread.length; i++) {

if (algorithm.control().getRun()) {

triangulateThread = new Thread(this, "Triangulation-" + String.valueOf(i));

triangulateThread.setPriority(Thread.MIN_PRIORITY);

triangulateThread.start();

}

}

}

/*

* Generate new points for the algorithms.

*/

private synchronized void newPoints() {

int max, alg;

stop();

// Find algorithm with max points.

max = 0;

alg = -1;

for (int i = 0; i < nAlgorithms; i++)

if (algorithm.control().getRun() &&

algorithm.control().getNPoints() > max) {

max = algorithm.control().getNPoints();

alg = i;

}

// Generate maximum number of points.

if (alg != -1) {

triangulation[alg].setNPoints(algorithm[alg].control().getNPoints());

triangulation[alg].randomPoints(w);

}

/* Now copy points into other algorithms. This has the effect

* that algorithms with the same number of points wind up with

* the same points.

*/

for (int i = 0; i < nAlgorithms; i++)

if (algorithm.control().getRun() && i != alg) {

triangulation.setNPoints(algorithm.control().getNPoints());

triangulation.copyPoints(triangulation[alg]);

}

for (int i = 0; i < nAlgorithms; i++)

if (algorithm.control().getRun()) {

algorithm.reset();

algorithm.canvas().repaint();

}

}

/*

* Stop the applet. Kill the triangulation algorithm if

* still triangulating.

*/

public synchronized void stop() {

for (int i = 0; i < triangulateThread.length; i++) {

if (triangulateThread != null) {

try {

triangulateThread.stop();

} catch (IllegalThreadStateException e) {}

triangulateThread = null;

}

}

}

/*

* Gets the current value in a text field.

*/

int getValue(TextField tF) {

int i;

try {

i = Integer.valueOf(tF.getText()).intValue();

} catch (java.lang.NumberFormatException e) {

i = 0;

}

return i;

}

/*

* Handle main level events.

*/

public boolean handleEvent(Event evt) {

if (evt.id == Event.ACTION_EVENT) {

if ("Start".equals(evt.arg)) {

startTriangulate();

return true;

} else if ("Stop".equals(evt.arg)) {