Coding for Streaming Delaunay
I propose to use this page as a place to record observations and progress. I'll start with some general ones, and ask you to fill in specifics.
Feel free to delete from this page, too.
One of the best things you could do is to rewrite any criticism of old code as positive reminders of what to do using new code as good examples.
Java Programming
Comments or questions on Java programming...
- this is not needed to refer to variables of a class within that class unless they have been redefined. Thus, the compiler gives you no error message for what is clearly a copy/paste error (see it?):
public TVector multScalar(double s) {
return new TVector(this.x*s, this.y*y);
}
- Integer vs int: The difference between getID and getKey in Triangle is that the latter allocates memory for an instance of Integer. Is there a benefit of doing so? If you were going to create a special type of triangle key, then the class would tell you what the integer meant, but for a generic integer, you might as well use the primitive type. If you need a reference to a class to put in a Map, can't you use the Triangle instead of its ID?
I think at some point, I was going to use the Triangle itself as the key, but I wanted the index into a list or something. I was planning to rethink the data structures used/needed.
--
TyniaYang - 20 May 2005
Todd suggested (and loaned) reading
Effective Java.
--
TyniaYang - 22 May 2005
Refactoring
From “Refactoring: Improving the Design of Existing Code,” by Martin Fowler, Kent Beck, John Brant, William Opdyke, and Don Roberts.
Refactoring is the process of changing a software system in such a way that it does
not alter the external behavior of the code yet improves its internal structure. It is a
disciplined way to clean up code that minimizes the chances of introducing bugs. In
essence when you refactor you are improving the design of the code after it has been
written.
“Improving the design after it has been written.”
--
JackSnoeyink - 19 May 2005
Comments on version 2
You should never tell me that there is no hurry for something...
I set it aside and never get back to it.
It is nice that this runs; congrats.
Here are a few comments on the design; the most important is that you have all three types of representations of planar graphs: edge-based, vertex-based, and face-based.
X_Comparator.java
public class X_Comparator implements Comparator {
// comparator for vertices, sorted on x-coordinate
public int compare(Vert arg0, Vert arg1) {
if (arg0 == arg1) {
return 0;
}
// break ties with Y
if (arg0.getX() == arg1.getX()) {
return (arg0.getY() < arg1.getY() ? -1 : 1);
} else {
return (arg0.getX() < arg1.getX() ? -1 : 1);
}
}
}
Should break ties on y. (Sort routines could go into an infinite loop if two points have the same x coordinate.)
ok.--
TyniaYang - 28 Jul 2005
Vertex.java
Vertex has lots of things that deal with (frontier) edges;
I wonder if these should be in an edge class?
private ArrayList halfedges; // A list of halfedges that starts at this
The halfedges attached to a vertex
must be in a special order (ccw? cw?), which is not reflected in the comments or the construction within Vert; this is a property of how construction is called. It would be far better to have this be an invariant
that is maintained within a given class.
Actually, the halfedges aren't in any particular order. Halfedges are linked in CCW order around a Face, but that is maintained by the Next and Prev pointers inside Halfedge. --
TyniaYang - 28 Jul 2005
Instead of storing the halfedges that come out of each vertex, I could also just store one halfedge, and get the rest by using the halfedge's next/prev/opp pointers. For instance, the next outgoing halfedge would be this halfedge->opp->next. Or, if this halfedge is a frontier edge (and has no opp), the next outgoing halfedge would be this halfedge->prev->opp. The problem with this that if the vertex is on the frontier, and the halfedge stored is an interior edge, I have to traverse in two directions to make sure I collect all of the outgoing halfedges. So I think I should make an invariant that says the stored halfedge IS a frontier edge, until the Vertex no longer lies on the frontier.
/**
* Goes through the halfedges that originate at this Vert and finds the previous halfedge. (basically, looks for halfedges for which this Vert is a destination vertex)
* If the previous halfedge is a frontier edge, returns. Otherwise, throw an exception
*/
public Halfedge findPrevFrontierEdge() {
What does prev mean here?
I traverse the frontier in CCW direction. findPrevFrontierEdge means looking for the frontier edge in the CW direction. I wanted this so that I wouldn't have to go around the whole frontier to find my previous halfedge. --
TyniaYang - 28 Jul 2005
Face.java Halfedge.java
Interesting (unnecessary) to have vertex, edge, and face data structures all contain information for the ordered lists of edges.
You can get by with one of these 3.
Are all 3 consistent? (good audit test)
There is not much on streaming here; most of it is straight Delaunay. Perhaps this could be partitioned into two classes...
You can avoid the
KDtree, which is costly to your performance, since you insert points in sorted x coordinate order, you can always start with the last point that was inseted in place of the closest point.
You're right, I thought that by picking the closest point, I would save time, but I wind up working my way around the whole frontier anyways. I got rid of the kdtree
What other things keep you from running this on 2000 or 20,000 data points? I suspect that there are quadratic time data structure manipulations; can you show me wrong?
This function
clearly belongs to the vertex class.
public double[] makeKDKey(Vert v) {
return new double[]{v.getX(), v.getY()};
}
Older comments...
The Driver ?
public class StreamingDelaunay {
public TreeSet vertices;
public KDTree frontier;
public ArrayListedgeQueue;
public StreamingDelaunay() {
vertices = new TreeSet(new X_Comparator());
frontier = new KDTree(2);
edgeQueue = new ArrayList();
}
/**
* @param v: Vert in question. Make a new Face from v and the endpoints of currEdge, and then legalize.
* @param currEdge: The halfedge which will make up one side of the new Face.
* @param currVert
*
* Essentially, processing a Vert means making a new Face, and putting the shared edge in the Edgequeue.
* v is then legalized against the edges in the edgequeue. Each new edgeflip results in more edges to be checked.
*
*/
public void processVertex(Vert v, Halfedge currEdge, Vert currVert) {
if (currEdge.seesVertex(v) && currVert != v) {
// make a new face
Face newFace = new Face(v,currEdge.getOrigVert(),currEdge.getDestVert());
System.out.println("made face"+newFace);
Vert dest = currEdge.getDestVert();
Halfedge currOpp = newFace.getHalfedge(dest);
currEdge.setOpp(currOpp);
currOpp.setOpp(currEdge);
// then add currEdge to the edgeQueue
edgeQueue.add(currEdge);
// System.out.println("==1currVert's frontier edge "+currVert.findFrontierEdge());
// edgeQueue holds suspect edges, which may result in cascading due to edge flips
while (!edgeQueue.isEmpty()) {
Halfedge e = edgeQueue.remove(0);
System.out.println("processing "+e);
if (!e.isFrontier()) {
e.legalize(v,edgeQueue);
}
}
}
}
public static void main(String[] args) {
StreamingDelaunay SD = new StreamingDelaunay();
FileWriter fw = null;
try {
fw = new FileWriter("streamingd.txt");
} catch (IOException e1) {
e1.printStackTrace();
}
// make lots of new vertices
for (int i=0; i<20; i++){
Vert vert = new Vert(Math.random()*20, Math.random()*20);
SD.vertices.add(vert);
}
// write vertices out to file, so I can plot them in Matlab
for (Vert v : SD.vertices) {
String vstr = v.toString();
try {
fw.write(vstr);
fw.write("\n");
} catch (IOException e) {
e.printStackTrace();
}
}
try {
fw.close();
} catch (IOException e1) {
e1.printStackTrace();
}
// grab first three, put into frontier
for (int i=0; i<3; i++) {
Vert first = SD.vertices.first();
SD.vertices.remove(first);
SD.addVertToFrontier(first);
}
// now make a face from these first three vertices
Vert[] first3 = SD.grabNFromFrontier(3);
Face f = new Face(first3[0],first3[1],first3[2]);
System.out.println("-- first face "+f);
// and now process the remaining vertices
for (Vert v : SD.vertices) {
System.out.println(v);
// get the closest vertex from the frontier
Vert closest = SD.getNearestVertsFromFrontier(v,1)[0];
Vert currVert = closest;
// the last vertex marks when to stop marching
Vert lastVert = (closest.findPrevFrontierEdge()).getOrigVert();
System.out.println("LASTVERT "+lastVert);
Halfedge currEdge = currVert.findFrontierEdge();
while (currVert != lastVert) {
System.out.println("--Current Edge: "+currEdge);
SD.processVertex(v, currEdge, currVert);
// and march to the next frontier edge
Halfedge nextFrontier = (currVert.isInterior() ? v.findFrontierEdge() : currVert.findFrontierEdge());
currVert = nextFrontier.getDestVert();
currEdge = nextFrontier;
System.out.println("-- nextVert "+currVert);
}
System.out.println("~~~~~~~~~~ CURRENT VERT "+currVert);
System.out.println("CURRENT EDGE "+currEdge);
SD.processVertex(v, currEdge, currVert);
// now get the frontier edge coming out of lastVert
currEdge = (currVert.isInterior() ? currEdge.getNext() : currVert.findFrontierEdge());
SD.processVertex(v, currEdge, currVert);
// now add the newly added Vertex to the frontier
SD.addVertToFrontier(v);
}
}
/**
* @param n
* @return : grabs n Verts from the frontier
*/
public Vert[] grabNFromFrontier(int n) {
// just grab n vertices
double[] key = {0,0};
try {
Vert[] toReturn = new Vert[n];
int found = 0;
while (found < n) {
found = 0;
Object[] objs = frontier.nearest(key,n);
for (int i=0; i
Data structures
To refactor, start with the data. Ask what objects do we need and what properties we need them to have after the computing is done. (Note that this is not asking what computing steps we do to get those properties; that will come fairly easily once we know the data.)
I want unique vertices and faces, which I can get by implementing Comparable for those classes. This lets me define compareTo functions, which means I can sort my vertices by x-coordinate and still put them into hashtables and other data structures, keying by the references themselves.
to define a comparator: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Comparator.html
to define a comparable object: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Comparable.html
-- TyniaYang - 08 Jun 2005
TreeSet vertices;
A binary tree that sorts the vertices on their x-coordinate. I expect to just iterate through the leaves to get my next vertex.
Uses the following Comparator to sort on x-coordinate.
public class X_Comparator implements Comparator {
// comparator for vertices, sorted on x-coordinate
public int compare(Vert arg0, Vert arg1) {
if (arg0 == arg1) {
return 0;
}
return (arg0.getX() < arg1.getX() ? -1 : 1);
}
}
-- TyniaYang - 08 Jun 2005
Half-Edge
A half-edge is oriented, so there are two half-edges per edge. A face has three half-edges running counter-clockwise around it, so each half-edge knows the next half-edge around the face, as well as the previous one. These form a loop. A half-edge should also know which vertex it originates from, and the face its looping around (it will be on the half-edge's left). It should also know about the half-edge that is oriented in the opposite direction, and consequently, its destination vertex (opposite's origin).
The existence of an opposite half-edge can be used as a test for whether a halfedge is a boundary edge or not. If a half-edge doesn't have an oppositely oriented half-edge, then it has to be a boundary edge because the adjacent face is the infinite face. Like in the case of a single triangle, all of the half-edges will run CCW around the triangle. But each half-edge's adjacent face is the unbounded infinite face. When I add a vertex and connect it to two of the old vertices, that creates a new face and three new half-edges, one of which will run opposite an original half-edge. So I can use the opposite half-edge to test for boundary edges. The frontier must be composed entirely of boundary edges. Otherwise, there would be a face on both sides of the edge and the new face would overlap an old one. So all new half-edges start out as potential frontier edges, but once I add the opposite half-edge, I can remove that edge from the list of frontier edges and add the newly created half-edges. In this way, I think I can grow my frontier.
-- TyniaYang - 30 Jun 2005
public class Halfedge {
private Halfedge opp; // oppositely oriented half-edge
private Face face; // the face that this halfedge walks around
private Vert vert; // vertex at the origin of the edge
private Halfedge heNext; // next edge around the face
private Halfedge hePrev; // prev edge around the face
// half edge needs a vertex origin
public Halfedge(Vert vert) {
this.vert = vert;
vert.addHalfedge(this);
heNext = null;
hePrev = null;
opp = null;
face = null;
}
public boolean isFrontier() { return opp==null;}
/*
* Tests to see if Vert v is inside circumscribing circle. If so, performs edgeflip and adds affected halfedges to edgeQueue to be processed. If not, simply returns
*/
public void legalize(Vert vnew, ArrayList queue) {
System.out.println("++legalizing "+vnew+" against "+this);
System.out.println("which belongs to this face "+getFace());
if (face.containsVertex(vnew)) {
// perform an edge flip
Halfedge oldPrev = getPrev();
Halfedge oldNext = getNext();
Vert v1 = getOrigVert();
Vert v2 = getDestVert();
Vert v3 = oldNext.getDestVert();
Face face123 = getFace();
Face newface = opp.getFace();
Halfedge vEdge = newface.getHalfedge(vnew);
Halfedge vOpp = newface.getHalfedge(v2);
Halfedge voldPrev = vOpp.getPrev();
Halfedge voldNext = vOpp.getNext();
System.out.println("Edge flipping from "+face+" and "+vEdge.getFace());
v1.removeHalfedge(this);
v2.removeHalfedge(vOpp);
// set this face's next/prev pointers
oldPrev.setNext(voldNext);
oldPrev.setPrev(this);
voldNext.setNext(this);
voldNext.setPrev(oldPrev);
setNext(oldPrev);
setPrev(voldNext);
vnew.addHalfedge(this);
setVert(vnew);
// now set the other face's pointers
oldNext.setNext(vOpp);
oldNext.setPrev(voldPrev);
vOpp.setNext(voldPrev);
vOpp.setPrev(oldNext);
voldPrev.setNext(oldNext);
voldPrev.setPrev(vOpp);
v3.addHalfedge(vOpp);
vOpp.setVert(v3);
// assign "new" halfedges to original face
ArrayList edges123 = new ArrayList();
edges123.add(getPrev());
edges123.add(this);
edges123.add(getNext());
face123.setHalfedges(edges123);
(getPrev()).setFace(face123);
// assign "new" halfedges to new face
ArrayList edgesN = new ArrayList();
edgesN.add(vOpp.getPrev());
edgesN.add(vOpp);
edgesN.add(vOpp.getNext());
newface.setHalfedges(edgesN);
(vOpp.getPrev()).setFace(newface);
System.out.println("to "+face+" and "+vEdge.getFace());
// add remaining two old edges to edgeQueue (cascading edge flips)
Halfedge susp1 = this.getNext();
Halfedge susp2 = vOpp.getPrev();
if (!susp1.isFrontier()) {
queue.add(susp1.getOpp());
System.out.println("adding to queue: "+susp1.getOpp());
}
if (!susp2.isFrontier()) {
queue.add(susp2.getOpp());
System.out.println("adding to queue: "+susp2.getOpp());
}
setOpp(vOpp);
vOpp.setOpp(this);
}
}
/**
* @param v : Tests if v is visible from this Halfedge
* visible means the vertex is on the right-hand-side of this Halfedge
*/
public boolean seesVertex(Vert v) {
if (v == getOrigVert() || v == getDestVert()) {
return false;
}
return !Vert.testCCW(getOrigVert(),getDestVert(),v);
}
public void setVert(Vert v) {
vert = v;
}
public void setFace(Face face) {
this.face = face;
}
public void setNext(Halfedge next) {
heNext = next;
}
public void setPrev(Halfedge prev) {
hePrev = prev;
}
public void setOpp(Halfedge opp) {
this.opp = opp;
}
public Face getFace() { return face;}
public Halfedge getNext() { return heNext;}
public Halfedge getPrev() { return hePrev;}
public Halfedge getOpp() { return opp;}
public Vert getOrigVert() { return vert;}
public Vert getDestVert() { return heNext.getOrigVert();}
public String toString() {
return "HE: ("+getOrigVert()+" to "+getDestVert()+")";
}
}
ArrayList? EdgeQueue?
I need this for edge flips, which can result in cascading edge flips. If I sort the vertices by their x-coordinate, then I don't think I will ever have to split a triangle. But new vertices can end up in an existing face's circumcircle. This would result in 2 new edges plus an edge flip. The remaining two edges (the two older, unflipped edges) now have to be checked. So I will put them in this EdgeQueue? and process the edge flips after each new insertion. This may result in more edges that have to be checked, so this continues until the EdgeQueue? is empty.
-- TyniaYang - 08 Jun 2005
KDTree frontier
I store Vertices on the frontier. Each Vertex must have a halfedge that does not have an opposite (it is on the boundary). When a Vertex becomes an interior Vertex, I will remove it from the kdtree.
Vertex
For now, since I'm working in 2D, Vertex should have an X and Y coordinate. Vertices have a unique ID which I use for debugging and tracing. Vertices should know about all of the half-edges that originate from it. I have a lot of accessor functions for finding frontier edges from a Vertex. This helps for marching along the frontier.
-- TyniaYang - 30 Jun 2005
public class Vert {
private static int numVerts = 0;
private int ID;
// coordinates
private double x;
private double y;
private ArrayList halfedges; // A list of halfedges that starts at this vertex
public Vert(double x, double y) {
ID = numVerts++;
this.x = x;
this.y = y;
halfedges = new ArrayList();
}
public double getX() { return x;}
public double getY() { return y;}
public void addHalfedge(Halfedge he) {
halfedges.add(he);
}
public void removeHalfedge(Halfedge he) {
if (halfedges.contains(he)) {
halfedges.remove(he);
}
}
/**
* If a Vert has frontier edges coming out of it, it lies on the frontier and is therefore, not interior.
* If it has no outgoing halfedges, it is still not an interior vertex.
* So returns True if there are outgoing halfedges, but none of them are on the frontier
*/
public boolean isInterior() {
if (halfedges.isEmpty()) {
return false;
}
for (Halfedge he: halfedges) {
if (he.isFrontier()) {
return false;
}
}
return true;
}
/**
* Counts the number of outgoing frontier edges
*/
public int numFrontierEdges() {
int num=0;
for (Halfedge he : halfedges) {
if (he.isFrontier()) {
num++;
}
}
return num;
}
/**
* Instead of just returning any outgoing frontier edge, returns all of them
*/
public ArrayList getAllFrontierEdges() {
ArrayList frontiers = new ArrayList();
for (Halfedge he: halfedges) {
if (he.isFrontier()) {
frontiers.add(he);
}
}
return frontiers;
}
/**
* Goes through the halfedges that originate at this Vert and picks the first one that is one the frontier
*/
public Halfedge findFrontierEdge() {
for (Halfedge he : halfedges) {
if (he.isFrontier()) {
return he;
}
}
throw new IllegalStateException("Vertex has no frontier edge");
}
/**
* Goes through the halfedges that originate at this Vert and finds the previous halfedge. (basically, looks for halfedges for which this Vert is a destination vertex)
* If the previous halfedge is a frontier edge, returns. Otherwise, throw an exception
*/
public Halfedge findPrevFrontierEdge() {
for (Halfedge he : halfedges) {
Halfedge prev = he.getPrev();
if (prev.isFrontier()) {
return prev;
}
}
throw new IllegalStateException("Vertex has no previous frontier edge");
}
public String toString() {
return "V["+ID+"]: "+String.format("%1$f, %2$f ",x, y);
}
/**
* @param v1 Given these three vertices, ordered v1,v2,v3, if they are counterclockwise, the determinant will be positive
* @param v2
* @param v3
* @return
*/
public static boolean testCCW(Vert v1, Vert v2, Vert v3) {
double[] row1 = {1.0, v1.getX(), v1.getY()};
double[] row2 = {1.0, v2.getX(), v2.getY()};
double[] row3 = {1.0, v3.getX(), v3.getY()};
Matrix mat = new Matrix(new double[][] {row1,row2,row3},3,3);
return mat.det() > 0;
}
}
Face
I want a Face to have 3 Vertices, ordered counter-clockwise around the face. A Face should be able to calculate its circumscribing circle, to test for Vertex inside-ness. Faces should not have any interior vertices, nor should neighboring vertices be inside the triangle's circumcircle. So when I add a new Vertex, if it's inside a Face or its circumcircle, I'll have to do an edge flip.
If a Face keeps track of the loop of half-edges running counter-clockwise around it, it will have access to the vertices (also in order) and neighboring faces (by looking at the half-edges' opposites and getting their faces). So when I add a Vertex, I will create a new Face. The new Face will share an edge with an old Face, so I should set the shared edge's Halfedges to be each other's opposite. From there, I can test whether my new Vertex is inside the old Face's circumcircle, and edge flip. I now have a flipped edge, two old edges, and two new edges. I'll have to update the next/prev pointers of the Halfedges, and then add the old edges to my EdgeQueue? for the cascading edge flips. It seems simplest if I just keep track of the Triangles' half-edges.
-- TyniaYang - 30 Jun 2005
public class Face {
public static int numFaces = 0;
private ArrayList halfedges; // list of halfedges that run ccw around face
private int ID;
// face must receive 3 vertices
public Face(Vert va, Vert vb, Vert vc) {
ID = numFaces++;
makeHalfedges(va,vb,vc);
}
/**
* @param hedges: resets this face's Halfedges. Next/Prev/Opp pointers should have already been set.
*/
public void setHalfedges(ArrayList hedges) {
Vert v1 = (hedges.get(0)).getOrigVert();
Vert v2 = (hedges.get(1)).getOrigVert();
Vert v3 = (hedges.get(2)).getOrigVert();
if (Vert.testCCW(v1, v2, v3)) {
halfedges = hedges;
} else {
ArrayList reverse = new ArrayList();
reverse.add(hedges.get(2));
reverse.add(hedges.get(1));
reverse.add(hedges.get(0));
halfedges = reverse;
}
}
/**
* @param v1
* @param v2
* @param v3
* Three vertices v1,v2,v3 are input. If they are oriented CCW, Halfedge are created for each of them and connected in a ring around this Face.
* If they are oriented CW, Halfedges are created for the reversed vertices.
* Each Halfedge must have its next and previous pointers set, as well as opposites, if this Face is adjacent to others
*/
private void makeHalfedges(Vert v1, Vert v2, Vert v3) {
halfedges = new ArrayList(3);
if (Vert.testCCW(v1,v2,v3)) {
halfedges.add(new Halfedge(v1));
halfedges.add(new Halfedge(v2));
halfedges.add(new Halfedge(v3));
} else {
halfedges.add(new Halfedge(v3));
halfedges.add(new Halfedge(v2));
halfedges.add(new Halfedge(v1));
}
// for all the half-edges in the edges list, set the next and prev pointers
for (Halfedge he : halfedges) {
int index = halfedges.indexOf(he);
Halfedge next = (index < halfedges.size()-1 ? halfedges.get(index+1) : halfedges.get(0));
he.setNext(next);
next.setPrev(he);
// and set the face
he.setFace(this);
}
// also check for opposites
for (Halfedge he : halfedges) {
// also check for opposites
Vert orig = he.getOrigVert();
Vert dest = he.getDestVert();
if (dest.hasFrontierEdge()) {
ArrayListdestfrontiers = dest.getAllFrontierEdges();
for (Halfedge destf : destfrontiers) {
if (destf.getDestVert() == orig) {
he.setOpp(destf);
destf.setOpp(he);
break;
}
}
}
}
}
/**
* @param v: Vertex v
* @return: true, if v is inside the circumcircle described by this face's vertices (CCW)
* if determinant is negative, the point is outside the circle and function returns false
*/
public boolean containsVertex(Vert v) {
ArrayListvertices = getVertices();
Vert v1 = vertices.get(0);
Vert v2 = vertices.get(1);
Vert v3 = vertices.get(2);
double x1,y1,x2,y2,x3,y3;
x1 = v1.getX();
y1 = v1.getY();
x2 = v2.getX();
y2 = v2.getY();
x3 = v3.getX();
y3 = v3.getY();
Matrix M11 = new Matrix(new double[][] {
{x1, y1, (x1*x1)+(y1*y1),1},
{x2, y2, (x2*x2)+(y2*y2),1},
{x3, y3, (x3*x3)+(y3*y3),1},
{v.getX(), v.getY(), (v.getX()*v.getX())+(v.getY()*v.getY()),1}
});
// if point is inside or on the circle, determinant will be pos or equal zero
return M11.det() >= 0;
}
public ArrayList getHalfedges() { return halfedges;}
/**
* @param v: Given a Vertex v
* @return: The halfedge around this face that starts at v
*/
public Halfedge getHalfedge(Vert v) {
for (Halfedge he : halfedges) {
if (he.getOrigVert() == v) {
return he;
}
}
throw new IllegalStateException("Face doesn't have edge at "+v);
}
/**
* @return Goes around the Halfedges and collects their originating vertex
*/
public ArrayList getVertices() {
ArrayList vertices = new ArrayList(3);
for (Halfedge he : halfedges) {
vertices.add(he.getOrigVert());
}
return vertices;
}
public String toString() {
ArrayListverts = getVertices();
String toreturn = "Face["+ID+"]--";
for (Vert v : verts) {
toreturn = toreturn + v;
}
return toreturn;
}
}
-- TyniaYang - 08 Jun 2005
Bad smells
Make a list, with examples, of "bad smells" from the Refactoring book that you find in your code.
- A minor one from the Edge constructor: duplicated conditional code is easy to get wrong on cut/paste and less efficient.
public Edge(Vertex v1, Vertex v2) {
// want v1 to be lower y-value than v2
this.v1 = (v1.y - v2.y < 0.0 ? v1 : v2);
this.v2 = (v1.y - v2.y < 0.0 ? v2 : v1);
}
- Similar example from Triangle. While getting things to work is first priority, you should note that calling getKey 3 times creates memory for 3 copies of the id.
v1.addFace(this.getKey());
v2.addFace(this.getKey());
v3.addFace(this.getKey());
Other things to do
Refactoring says I should have a set of self-checking tests for my code.
-- TyniaYang - 21 May 2005
Yes, but first decide clearly what each class is supposed to maintain so that you know what to test. -- JackSnoeyink - 22 May 2005
Algorithm correctness
Here are some reasons why your current implementation of StreamingDelaunay will give you trouble. -- JackSnoeyink - 24 May 2005
Adding points outside the hull
- Circumcenters need not be in triangles.
Your search for the closest triangle to a point outside the convex hull actually finds the triangle with closest circumcircle center. This point may be far outside the triangle (and usually is for skinny triangles near the convex hull, which have huge circumcircles). Thus, your getClosestFace routine would skip over such triangles to return one that is not the closest.
public Triangle getClosestFace(Vertex v) {
Triangle result = null;
synchronized(faces.values()) {
Iterator fIter = faces.values().iterator();
double minDist = Double.POSITIVE_INFINITY;
while (fIter.hasNext()) {
Triangle tri = (Triangle)fIter.next();
double d = tri.distToCircle(v);
if (d < minDist) {
minDist = d;
result = tri;
}
}
}
return result;
- You add only one triangle.
addVertexToGraph(Vertex v) has lots of problems. It has no option to loop or flip. You may need many triangles because the new point may shield many former convex hull edges; you'll want a triangle to each former hull edge.
Edge flips
Your edgeFlip(Vertex v,int f) routine flips only the closest edge. On average you need to flip 3 edges and create 3.
It may be that this edge should not even be flipped. Flips must be applied to every edge whose circumcircle contains the new point, and to no other edges. (They should also be done in the right order; Look at the Guibas Stolfi paper on the web site.)
Brute force searches
This is not a correctness issue, but the exhaustive search for containing triangles, closest edges, closest centers, etc will make this algorithm run in at least quadratic time in all cases. You won't want to use this on large models or terrain.
Questions
Going around the entire hull, or figuring out the endpoints and staying on visible side
Given a new Vertex and a boundary Halfedge, I can use the determinant test to see if the Vertex is on the interior or exterior of my triangulation. I also know that I can march around the boundary by picking Vertices that have a frontier halfedge that originates from them. Because I store the boundary vertices in a kdtree, I can do a nearest-point query and get the closest Vertex that is on the boundary. This should be a frontier vertex. Is it easier to just go around the entire boundary, and skip over the half-edges that fail the determinant test, or does it make more sense to start at the nearest point and go upwards (CCW) until I am no longer on the frontier (relative to the new point) and then work downwards (CW) and do the same?
Searching for closest point instead of closest halfedge
When I add a new vertex, I want to find the closest edge and start there with the "check if inside circle" thing and adding a new face. Except I think it is easier to define the distance between two points instead of distance from a point to a line. So I would like to put my frontier vertices in a tree and search through those for the closest Vertex to my new point. From there, I could get the frontier half-edge that originates at the closest Vertex.
Randomized Incremental vs Sorted
If I add points in sorted order, I don't think the new point will ever be inside another triangle. It seems like they might be inside a circumcircle (thus, edge flip) but I don't think I will wind up splitting a triangle other than the very large triangle formed by the special points... -- TyniaYang? - 26 May 2005
True. Of course the consequence is that you can't prove O(n log n) expected time, so you may want a hybrid where you add points in strips, but randomize within the strips. But you don't have to worry about that at the moment. -- JackSnoeyink? - 26 May 2005
Bounding triangle?
In the book, the randomized incremental algorithm starts with 3 points, p_-1, p_-2, p_-3 such that the resulting triangle contains all of the points inside. But if the points are streamed, I won't know what the bounds are and can't really pick p_-1, p_-2, p_-3. The book refers to these points as "special points" so can I just make a special point class and just pick very large coordinates for them?
From the lecture notes on 3D Delaunay, you mention using a point at infinity to avoid special-casing the convex hull. -- TyniaYang? - 26 May 2005
_Or decide that you don't need them, since they are just to make sure that even points outside the convex hull start in a single triangle. If you add the point in sorted order, then the convex hull is already special -- it is the only case that happens.
Or just use one infinite point, at x=+infty. Or... There are lots of options.
Leo has been looking at the different options for handling points at infinity, and is writing a paper on them. -- JackSnoeyink? - 26 May 2005_
to top