summaryrefslogtreecommitdiffstats
path: root/delaunay
diff options
context:
space:
mode:
Diffstat (limited to 'delaunay')
-rw-r--r--delaunay/ArraySet.java104
-rw-r--r--delaunay/DelaunayAp.java429
-rw-r--r--delaunay/Graph.java108
-rw-r--r--delaunay/Pnt.java470
-rw-r--r--delaunay/Triangle.java152
-rw-r--r--delaunay/Triangulation.java281
6 files changed, 1544 insertions, 0 deletions
diff --git a/delaunay/ArraySet.java b/delaunay/ArraySet.java
new file mode 100644
index 0000000..b3fe357
--- /dev/null
+++ b/delaunay/ArraySet.java
@@ -0,0 +1,104 @@
+package delaunay;
+
+/*
+ * Copyright (c) 2007 by L. Paul Chew.
+ *
+ * Permission is hereby granted, without written agreement and without
+ * license or royalty fees, to use, copy, modify, and distribute this
+ * software and its documentation for any purpose, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+
+/**
+ * An ArrayList implementation of Set. An ArraySet is good for small sets; it
+ * has less overhead than a HashSet or a TreeSet.
+ *
+ * @author Paul Chew
+ *
+ * Created December 2007. For use with Voronoi/Delaunay applet.
+ *
+ */
+public class ArraySet<E> extends AbstractSet<E> {
+
+ private ArrayList<E> items; // Items of the set
+
+ /**
+ * Create an empty set (default initial capacity is 3).
+ */
+ public ArraySet () {
+ this(3);
+ }
+
+ /**
+ * Create an empty set with the specified initial capacity.
+ * @param initialCapacity the initial capacity
+ */
+ public ArraySet (int initialCapacity) {
+ items = new ArrayList<E>(initialCapacity);
+ }
+
+ /**
+ * Create a set containing the items of the collection. Any duplicate
+ * items are discarded.
+ * @param collection the source for the items of the small set
+ */
+ public ArraySet (Collection<? extends E> collection) {
+ items = new ArrayList<E>(collection.size());
+ for (E item: collection)
+ if (!items.contains(item)) items.add(item);
+ }
+
+ /**
+ * Get the item at the specified index.
+ * @param index where the item is located in the ListSet
+ * @return the item at the specified index
+ * @throws IndexOutOfBoundsException if the index is out of bounds
+ */
+ public E get (int index) throws IndexOutOfBoundsException {
+ return items.get(index);
+ }
+
+ /**
+ * True iff any member of the collection is also in the ArraySet.
+ * @param collection the Collection to check
+ * @return true iff any member of collection appears in this ArraySet
+ */
+ public boolean containsAny (Collection<?> collection) {
+ for (Object item: collection)
+ if (this.contains(item)) return true;
+ return false;
+ }
+
+ @Override
+ public boolean add(E item) {
+ if (items.contains(item)) return false;
+ return items.add(item);
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return items.iterator();
+ }
+
+ @Override
+ public int size() {
+ return items.size();
+ }
+
+}
diff --git a/delaunay/DelaunayAp.java b/delaunay/DelaunayAp.java
new file mode 100644
index 0000000..43fbecc
--- /dev/null
+++ b/delaunay/DelaunayAp.java
@@ -0,0 +1,429 @@
+package delaunay;
+
+/*
+ * Copyright (c) 2005, 2007 by L. Paul Chew.
+ *
+ * Permission is hereby granted, without written agreement and without
+ * license or royalty fees, to use, copy, modify, and distribute this
+ * software and its documentation for any purpose, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+import java.awt.BorderLayout;
+import java.awt.Color;
+import java.awt.Component;
+import java.awt.Graphics;
+import java.awt.Label;
+import java.awt.event.ActionEvent;
+import java.awt.event.ActionListener;
+import java.awt.event.MouseEvent;
+import java.awt.event.MouseListener;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+
+import javax.swing.AbstractButton;
+import javax.swing.ButtonGroup;
+import javax.swing.JButton;
+import javax.swing.JCheckBox;
+import javax.swing.JFrame;
+import javax.swing.JLabel;
+import javax.swing.JPanel;
+import javax.swing.JRadioButton;
+import javax.swing.SwingUtilities;
+
+/**
+ * The Delauany applet.
+ *
+ * Creates and displays a Delaunay Triangulation (DT) or a Voronoi Diagram
+ * (VoD). Has a main program so it is an application as well as an applet.
+ *
+ * @author Paul Chew
+ *
+ * Created July 2005. Derived from an earlier, messier version.
+ *
+ * Modified December 2007. Updated some of the Triangulation methods. Added the
+ * "Colorful" checkbox. Reorganized the interface between DelaunayAp and
+ * DelaunayPanel. Added code to find a Voronoi cell.
+ *
+ */
+@SuppressWarnings("serial")
+public class DelaunayAp extends javax.swing.JApplet
+ implements Runnable, ActionListener, MouseListener {
+
+ private boolean debug = false; // Used for debugging
+ private Component currentSwitch = null; // Entry-switch that mouse is in
+
+ private static String windowTitle = "Voronoi/Delaunay Window";
+ private JRadioButton voronoiButton = new JRadioButton("Voronoi Diagram");
+ private JRadioButton delaunayButton =
+ new JRadioButton("Delaunay Triangulation");
+ private JButton clearButton = new JButton("Clear");
+ private JCheckBox colorfulBox = new JCheckBox("More Colorful");
+ private DelaunayPanel delaunayPanel = new DelaunayPanel(this);
+ private JLabel circleSwitch = new JLabel("Show Empty Circles");
+ private JLabel delaunaySwitch = new JLabel("Show Delaunay Edges");
+ private JLabel voronoiSwitch = new JLabel("Show Voronoi Edges");
+
+ /**
+ * Main program (used when run as application instead of applet).
+ */
+ public static void main (String[] args) {
+ DelaunayAp applet = new DelaunayAp(); // Create applet
+ applet.init(); // Applet initialization
+ JFrame dWindow = new JFrame(); // Create window
+ dWindow.setSize(700, 500); // Set window size
+ dWindow.setTitle(windowTitle); // Set window title
+ dWindow.setLayout(new BorderLayout()); // Specify layout manager
+ dWindow.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
+ // Specify closing behavior
+ dWindow.add(applet, "Center"); // Place applet into window
+ dWindow.setVisible(true); // Show the window
+ }
+
+ /**
+ * Initialize the applet.
+ * As recommended, the actual use of Swing components takes place in the
+ * event-dispatching thread.
+ */
+ public void init () {
+ try {SwingUtilities.invokeAndWait(this);}
+ catch (Exception e) {System.err.println("Initialization failure");}
+ }
+
+ /**
+ * Set up the applet's GUI.
+ * As recommended, the init method executes this in the event-dispatching
+ * thread.
+ */
+ public void run () {
+ setLayout(new BorderLayout());
+
+ // Add the button controls
+ ButtonGroup group = new ButtonGroup();
+ group.add(voronoiButton);
+ group.add(delaunayButton);
+ JPanel buttonPanel = new JPanel();
+ buttonPanel.add(voronoiButton);
+ buttonPanel.add(delaunayButton);
+ buttonPanel.add(clearButton);
+ buttonPanel.add(new JLabel(" ")); // Spacing
+ buttonPanel.add(colorfulBox);
+ this.add(buttonPanel, "North");
+
+ // Add the mouse-entry switches
+ JPanel switchPanel = new JPanel();
+ switchPanel.add(circleSwitch);
+ switchPanel.add(new Label(" ")); // Spacing
+ switchPanel.add(delaunaySwitch);
+ switchPanel.add(new Label(" ")); // Spacing
+ switchPanel.add(voronoiSwitch);
+ this.add(switchPanel, "South");
+
+ // Build the delaunay panel
+ delaunayPanel.setBackground(Color.gray);
+ this.add(delaunayPanel, "Center");
+
+ // Register the listeners
+ voronoiButton.addActionListener(this);
+ delaunayButton.addActionListener(this);
+ clearButton.addActionListener(this);
+ colorfulBox.addActionListener(this);
+ delaunayPanel.addMouseListener(this);
+ circleSwitch.addMouseListener(this);
+ delaunaySwitch.addMouseListener(this);
+ voronoiSwitch.addMouseListener(this);
+
+ // Initialize the radio buttons
+ voronoiButton.doClick();
+ }
+
+ /**
+ * A button has been pressed; redraw the picture.
+ */
+ public void actionPerformed(ActionEvent e) {
+ if (debug)
+ System.out.println(((AbstractButton)e.getSource()).getText());
+ if (e.getSource() == clearButton) delaunayPanel.clear();
+ delaunayPanel.repaint();
+ }
+
+ /**
+ * If entering a mouse-entry switch then redraw the picture.
+ */
+ public void mouseEntered(MouseEvent e) {
+ currentSwitch = e.getComponent();
+ if (currentSwitch instanceof JLabel) delaunayPanel.repaint();
+ else currentSwitch = null;
+ }
+
+ /**
+ * If exiting a mouse-entry switch then redraw the picture.
+ */
+ public void mouseExited(MouseEvent e) {
+ currentSwitch = null;
+ if (e.getComponent() instanceof JLabel) delaunayPanel.repaint();
+ }
+
+ /**
+ * If mouse has been pressed inside the delaunayPanel then add a new site.
+ */
+ public void mousePressed(MouseEvent e) {
+ if (e.getSource() != delaunayPanel) return;
+ Pnt point = new Pnt(e.getX(), e.getY());
+ if (debug ) System.out.println("Click " + point);
+ delaunayPanel.addSite(point);
+ delaunayPanel.repaint();
+ }
+
+ /**
+ * Not used, but needed for MouseListener.
+ */
+ public void mouseReleased(MouseEvent e) {}
+ public void mouseClicked(MouseEvent e) {}
+
+ /**
+ * @return true iff the "colorful" box is selected
+ */
+ public boolean isColorful() {
+ return colorfulBox.isSelected();
+ }
+
+ /**
+ * @return true iff doing Voronoi diagram.
+ */
+ public boolean isVoronoi() {
+ return voronoiButton.isSelected();
+ }
+
+ /**
+ * @return true iff within circle switch
+ */
+ public boolean showingCircles() {
+ return currentSwitch == circleSwitch;
+ }
+
+ /**
+ * @return true iff within delaunay switch
+ */
+ public boolean showingDelaunay() {
+ return currentSwitch == delaunaySwitch;
+ }
+
+ /**
+ * @return true iff within voronoi switch
+ */
+ public boolean showingVoronoi() {
+ return currentSwitch == voronoiSwitch;
+ }
+
+}
+
+/**
+ * Graphics Panel for DelaunayAp.
+ */
+@SuppressWarnings("serial")
+class DelaunayPanel extends JPanel {
+
+ public static Color voronoiColor = Color.magenta;
+ public static Color delaunayColor = Color.green;
+ public static int pointRadius = 3;
+
+ private DelaunayAp controller; // Controller for DT
+ private Triangulation dt; // Delaunay triangulation
+ private Map<Object, Color> colorTable; // Remembers colors for display
+ private Triangle initialTriangle; // Initial triangle
+ private static int initialSize = 10000; // Size of initial triangle
+ private Graphics g; // Stored graphics context
+ private Random random = new Random(); // Source of random numbers
+
+ /**
+ * Create and initialize the DT.
+ */
+ public DelaunayPanel (DelaunayAp controller) {
+ this.controller = controller;
+ initialTriangle = new Triangle(
+ new Pnt(-initialSize, -initialSize),
+ new Pnt( initialSize, -initialSize),
+ new Pnt( 0, initialSize));
+ dt = new Triangulation(initialTriangle);
+ colorTable = new HashMap<Object, Color>();
+ }
+
+ /**
+ * Add a new site to the DT.
+ * @param point the site to add
+ */
+ public void addSite(Pnt point) {
+ dt.delaunayPlace(point);
+ }
+
+ /**
+ * Re-initialize the DT.
+ */
+ public void clear() {
+ dt = new Triangulation(initialTriangle);
+ }
+
+ /**
+ * Get the color for the spcified item; generate a new color if necessary.
+ * @param item we want the color for this item
+ * @return item's color
+ */
+ private Color getColor (Object item) {
+ if (colorTable.containsKey(item)) return colorTable.get(item);
+ Color color = new Color(Color.HSBtoRGB(random.nextFloat(), 1.0f, 1.0f));
+ colorTable.put(item, color);
+ return color;
+ }
+
+ /* Basic Drawing Methods */
+
+ /**
+ * Draw a point.
+ * @param point the Pnt to draw
+ */
+ public void draw (Pnt point) {
+ int r = pointRadius;
+ int x = (int) point.coord(0);
+ int y = (int) point.coord(1);
+ g.fillOval(x-r, y-r, r+r, r+r);
+ }
+
+ /**
+ * Draw a circle.
+ * @param center the center of the circle
+ * @param radius the circle's radius
+ * @param fillColor null implies no fill
+ */
+ public void draw (Pnt center, double radius, Color fillColor) {
+ int x = (int) center.coord(0);
+ int y = (int) center.coord(1);
+ int r = (int) radius;
+ if (fillColor != null) {
+ Color temp = g.getColor();
+ g.setColor(fillColor);
+ g.fillOval(x-r, y-r, r+r, r+r);
+ g.setColor(temp);
+ }
+ g.drawOval(x-r, y-r, r+r, r+r);
+ }
+
+ /**
+ * Draw a polygon.
+ * @param polygon an array of polygon vertices
+ * @param fillColor null implies no fill
+ */
+ public void draw (Pnt[] polygon, Color fillColor) {
+ int[] x = new int[polygon.length];
+ int[] y = new int[polygon.length];
+ for (int i = 0; i < polygon.length; i++) {
+ x[i] = (int) polygon[i].coord(0);
+ y[i] = (int) polygon[i].coord(1);
+ }
+ if (fillColor != null) {
+ Color temp = g.getColor();
+ g.setColor(fillColor);
+ g.fillPolygon(x, y, polygon.length);
+ g.setColor(temp);
+ }
+ g.drawPolygon(x, y, polygon.length);
+ }
+
+ /* Higher Level Drawing Methods */
+
+ /**
+ * Handles painting entire contents of DelaunayPanel.
+ * Called automatically; requested via call to repaint().
+ * @param g the Graphics context
+ */
+ public void paintComponent (Graphics g) {
+ super.paintComponent(g);
+ this.g = g;
+
+ // Flood the drawing area with a "background" color
+ Color temp = g.getColor();
+ if (!controller.isVoronoi()) g.setColor(delaunayColor);
+ else if (dt.contains(initialTriangle)) g.setColor(this.getBackground());
+ else g.setColor(voronoiColor);
+ g.fillRect(0, 0, this.getWidth(), this.getHeight());
+ g.setColor(temp);
+
+ // If no colors then we can clear the color table
+ if (!controller.isColorful()) colorTable.clear();
+
+ // Draw the appropriate picture
+ if (controller.isVoronoi())
+ drawAllVoronoi(controller.isColorful(), true);
+ else drawAllDelaunay(controller.isColorful());
+
+ // Draw any extra info due to the mouse-entry switches
+ temp = g.getColor();
+ g.setColor(Color.white);
+ if (controller.showingCircles()) drawAllCircles();
+ if (controller.showingDelaunay()) drawAllDelaunay(false);
+ if (controller.showingVoronoi()) drawAllVoronoi(false, false);
+ g.setColor(temp);
+ }
+
+ /**
+ * Draw all the Delaunay triangles.
+ * @param withFill true iff drawing Delaunay triangles with fill colors
+ */
+ public void drawAllDelaunay (boolean withFill) {
+ for (Triangle triangle : dt) {
+ Pnt[] vertices = triangle.toArray(new Pnt[0]);
+ draw(vertices, withFill? getColor(triangle) : null);
+ }
+ }
+
+ /**
+ * Draw all the Voronoi cells.
+ * @param withFill true iff drawing Voronoi cells with fill colors
+ * @param withSites true iff drawing the site for each Voronoi cell
+ */
+ public void drawAllVoronoi (boolean withFill, boolean withSites) {
+ // Keep track of sites done; no drawing for initial triangles sites
+ HashSet<Pnt> done = new HashSet<Pnt>(initialTriangle);
+ for (Triangle triangle : dt)
+ for (Pnt site: triangle) {
+ if (done.contains(site)) continue;
+ done.add(site);
+ List<Triangle> list = dt.surroundingTriangles(site, triangle);
+ Pnt[] vertices = new Pnt[list.size()];
+ int i = 0;
+ for (Triangle tri: list)
+ vertices[i++] = tri.getCircumcenter();
+ draw(vertices, withFill? getColor(site) : null);
+ if (withSites) draw(site);
+ }
+ }
+
+ /**
+ * Draw all the empty circles (one for each triangle) of the DT.
+ */
+ public void drawAllCircles () {
+ // Loop through all triangles of the DT
+ for (Triangle triangle: dt) {
+ // Skip circles involving the initial-triangle vertices
+ if (triangle.containsAny(initialTriangle)) continue;
+ Pnt c = triangle.getCircumcenter();
+ double radius = c.subtract(triangle.get(0)).magnitude();
+ draw(c, radius, null);
+ }
+ }
+
+}
diff --git a/delaunay/Graph.java b/delaunay/Graph.java
new file mode 100644
index 0000000..c56df74
--- /dev/null
+++ b/delaunay/Graph.java
@@ -0,0 +1,108 @@
+package delaunay;
+
+/*
+ * Copyright (c) 2007 by L. Paul Chew.
+ *
+ * Permission is hereby granted, without written agreement and without
+ * license or royalty fees, to use, copy, modify, and distribute this
+ * software and its documentation for any purpose, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Straightforward undirected graph implementation.
+ * Nodes are generic type N.
+ *
+ * @author Paul Chew
+ *
+ * Created November, December 2007. For use in Delaunay/Voronoi code.
+ *
+ */
+public class Graph<N> {
+
+ private Map<N, Set<N>> theNeighbors = // Node -> adjacent nodes
+ new HashMap<N, Set<N>>();
+ private Set<N> theNodeSet = // Set view of all nodes
+ Collections.unmodifiableSet(theNeighbors.keySet());
+
+ /**
+ * Add a node. If node is already in graph then no change.
+ * @param node the node to add
+ */
+ public void add (N node) {
+ if (theNeighbors.containsKey(node)) return;
+ theNeighbors.put(node, new ArraySet<N>());
+ }
+
+ /**
+ * Add a link. If the link is already in graph then no change.
+ * @param nodeA one end of the link
+ * @param nodeB the other end of the link
+ * @throws NullPointerException if either endpoint is not in graph
+ */
+ public void add (N nodeA, N nodeB) throws NullPointerException {
+ theNeighbors.get(nodeA).add(nodeB);
+ theNeighbors.get(nodeB).add(nodeA);
+ }
+
+ /**
+ * Remove node and any links that use node. If node not in graph, nothing
+ * happens.
+ * @param node the node to remove.
+ */
+ public void remove (N node) {
+ if (!theNeighbors.containsKey(node)) return;
+ for (N neighbor: theNeighbors.get(node))
+ theNeighbors.get(neighbor).remove(node); // Remove "to" links
+ theNeighbors.get(node).clear(); // Remove "from" links
+ theNeighbors.remove(node); // Remove the node
+ }
+
+ /**
+ * Remove the specified link. If link not in graph, nothing happens.
+ * @param nodeA one end of the link
+ * @param nodeB the other end of the link
+ * @throws NullPointerException if either endpoint is not in graph
+ */
+ public void remove (N nodeA, N nodeB) throws NullPointerException {
+ theNeighbors.get(nodeA).remove(nodeB);
+ theNeighbors.get(nodeB).remove(nodeA);
+ }
+
+ /**
+ * Report all the neighbors of node.
+ * @param node the node
+ * @return the neighbors of node
+ * @throws NullPointerException if node does not appear in graph
+ */
+ public Set<N> neighbors (N node) throws NullPointerException {
+ return Collections.unmodifiableSet(theNeighbors.get(node));
+ }
+
+ /**
+ * Returns an unmodifiable Set view of the nodes contained in this graph.
+ * The set is backed by the graph, so changes to the graph are reflected in
+ * the set.
+ * @return a Set view of the graph's node set
+ */
+ public Set<N> nodeSet () {
+ return theNodeSet;
+ }
+
+}
diff --git a/delaunay/Pnt.java b/delaunay/Pnt.java
new file mode 100644
index 0000000..d9db79f
--- /dev/null
+++ b/delaunay/Pnt.java
@@ -0,0 +1,470 @@
+package delaunay;
+
+/*
+ * Copyright (c) 2005, 2007 by L. Paul Chew.
+ *
+ * Permission is hereby granted, without written agreement and without
+ * license or royalty fees, to use, copy, modify, and distribute this
+ * software and its documentation for any purpose, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+/**
+ * Points in Euclidean space, implemented as double[].
+ *
+ * Includes simple geometric operations.
+ * Uses matrices; a matrix is represented as an array of Pnts.
+ * Uses simplices; a simplex is represented as an array of Pnts.
+ *
+ * @author Paul Chew
+ *
+ * Created July 2005. Derived from an earlier, messier version.
+ *
+ * Modified Novemeber 2007. Minor clean up.
+ */
+public class Pnt {
+
+ private double[] coordinates; // The point's coordinates
+
+ /**
+ * Constructor.
+ * @param coords the coordinates
+ */
+ public Pnt (double... coords) {
+ // Copying is done here to ensure that Pnt's coords cannot be altered.
+ // This is necessary because the double... notation actually creates a
+ // constructor with double[] as its argument.
+ coordinates = new double[coords.length];
+ System.arraycopy(coords, 0, coordinates, 0, coords.length);
+ }
+
+ @Override
+ public String toString () {
+ if (coordinates.length == 0) return "Pnt()";
+ String result = "Pnt(" + coordinates[0];
+ for (int i = 1; i < coordinates.length; i++)
+ result = result + "," + coordinates[i];
+ result = result + ")";
+ return result;
+ }
+
+ @Override
+ public boolean equals (Object other) {
+ if (!(other instanceof Pnt)) return false;
+ Pnt p = (Pnt) other;
+ if (this.coordinates.length != p.coordinates.length) return false;
+ for (int i = 0; i < this.coordinates.length; i++)
+ if (this.coordinates[i] != p.coordinates[i]) return false;
+ return true;
+ }
+
+ @Override
+ public int hashCode () {
+ int hash = 0;
+ for (double c: this.coordinates) {
+ long bits = Double.doubleToLongBits(c);
+ hash = (31*hash) ^ (int)(bits ^ (bits >> 32));
+ }
+ return hash;
+ }
+
+ /* Pnts as vectors */
+
+ /**
+ * @return the specified coordinate of this Pnt
+ * @throws ArrayIndexOutOfBoundsException for bad coordinate
+ */
+ public double coord (int i) {
+ return this.coordinates[i];
+ }
+
+ /**
+ * @return this Pnt's dimension.
+ */
+ public int dimension () {
+ return coordinates.length;
+ }
+
+ /**
+ * Check that dimensions match.
+ * @param p the Pnt to check (against this Pnt)
+ * @return the dimension of the Pnts
+ * @throws IllegalArgumentException if dimension fail to match
+ */
+ public int dimCheck (Pnt p) {
+ int len = this.coordinates.length;
+ if (len != p.coordinates.length)
+ throw new IllegalArgumentException("Dimension mismatch");
+ return len;
+ }
+
+ /**
+ * Create a new Pnt by adding additional coordinates to this Pnt.
+ * @param coords the new coordinates (added on the right end)
+ * @return a new Pnt with the additional coordinates
+ */
+ public Pnt extend (double... coords) {
+ double[] result = new double[coordinates.length + coords.length];
+ System.arraycopy(coordinates, 0, result, 0, coordinates.length);
+ System.arraycopy(coords, 0, result, coordinates.length, coords.length);
+ return new Pnt(result);
+ }
+
+ /**
+ * Dot product.
+ * @param p the other Pnt
+ * @return dot product of this Pnt and p
+ */
+ public double dot (Pnt p) {
+ int len = dimCheck(p);
+ double sum = 0;
+ for (int i = 0; i < len; i++)
+ sum += this.coordinates[i] * p.coordinates[i];
+ return sum;
+ }
+
+ /**
+ * Magnitude (as a vector).
+ * @return the Euclidean length of this vector
+ */
+ public double magnitude () {
+ return Math.sqrt(this.dot(this));
+ }
+
+ /**
+ * Subtract.
+ * @param p the other Pnt
+ * @return a new Pnt = this - p
+ */
+ public Pnt subtract (Pnt p) {
+ int len = dimCheck(p);
+ double[] coords = new double[len];
+ for (int i = 0; i < len; i++)
+ coords[i] = this.coordinates[i] - p.coordinates[i];
+ return new Pnt(coords);
+ }
+
+ /**
+ * Add.
+ * @param p the other Pnt
+ * @return a new Pnt = this + p
+ */
+ public Pnt add (Pnt p) {
+ int len = dimCheck(p);
+ double[] coords = new double[len];
+ for (int i = 0; i < len; i++)
+ coords[i] = this.coordinates[i] + p.coordinates[i];
+ return new Pnt(coords);
+ }
+
+ /**
+ * Angle (in radians) between two Pnts (treated as vectors).
+ * @param p the other Pnt
+ * @return the angle (in radians) between the two Pnts
+ */
+ public double angle (Pnt p) {
+ return Math.acos(this.dot(p) / (this.magnitude() * p.magnitude()));
+ }
+
+ /**
+ * Perpendicular bisector of two Pnts.
+ * Works in any dimension. The coefficients are returned as a Pnt of one
+ * higher dimension (e.g., (A,B,C,D) for an equation of the form
+ * Ax + By + Cz + D = 0).
+ * @param point the other point
+ * @return the coefficients of the perpendicular bisector
+ */
+ public Pnt bisector (Pnt point) {
+ dimCheck(point);
+ Pnt diff = this.subtract(point);
+ Pnt sum = this.add(point);
+ double dot = diff.dot(sum);
+ return diff.extend(-dot / 2);
+ }
+
+ /* Pnts as matrices */
+
+ /**
+ * Create a String for a matrix.
+ * @param matrix the matrix (an array of Pnts)
+ * @return a String represenation of the matrix
+ */
+ public static String toString (Pnt[] matrix) {
+ StringBuilder buf = new StringBuilder("{");
+ for (Pnt row: matrix) buf.append(" " + row);
+ buf.append(" }");
+ return buf.toString();
+ }
+
+ /**
+ * Compute the determinant of a matrix (array of Pnts).
+ * This is not an efficient implementation, but should be adequate
+ * for low dimension.
+ * @param matrix the matrix as an array of Pnts
+ * @return the determinnant of the input matrix
+ * @throws IllegalArgumentException if dimensions are wrong
+ */
+ public static double determinant (Pnt[] matrix) {
+ if (matrix.length != matrix[0].dimension())
+ throw new IllegalArgumentException("Matrix is not square");
+ boolean[] columns = new boolean[matrix.length];
+ for (int i = 0; i < matrix.length; i++) columns[i] = true;
+ try {return determinant(matrix, 0, columns);}
+ catch (ArrayIndexOutOfBoundsException e) {
+ throw new IllegalArgumentException("Matrix is wrong shape");
+ }
+ }
+
+ /**
+ * Compute the determinant of a submatrix specified by starting row
+ * and by "active" columns.
+ * @param matrix the matrix as an array of Pnts
+ * @param row the starting row
+ * @param columns a boolean array indicating the "active" columns
+ * @return the determinant of the specified submatrix
+ * @throws ArrayIndexOutOfBoundsException if dimensions are wrong
+ */
+ private static double determinant(Pnt[] matrix, int row, boolean[] columns){
+ if (row == matrix.length) return 1;
+ double sum = 0;
+ int sign = 1;
+ for (int col = 0; col < columns.length; col++) {
+ if (!columns[col]) continue;
+ columns[col] = false;
+ sum += sign * matrix[row].coordinates[col] *
+ determinant(matrix, row+1, columns);
+ columns[col] = true;
+ sign = -sign;
+ }
+ return sum;
+ }
+
+ /**
+ * Compute generalized cross-product of the rows of a matrix.
+ * The result is a Pnt perpendicular (as a vector) to each row of
+ * the matrix. This is not an efficient implementation, but should
+ * be adequate for low dimension.
+ * @param matrix the matrix of Pnts (one less row than the Pnt dimension)
+ * @return a Pnt perpendicular to each row Pnt
+ * @throws IllegalArgumentException if matrix is wrong shape
+ */
+ public static Pnt cross (Pnt[] matrix) {
+ int len = matrix.length + 1;
+ if (len != matrix[0].dimension())
+ throw new IllegalArgumentException("Dimension mismatch");
+ boolean[] columns = new boolean[len];
+ for (int i = 0; i < len; i++) columns[i] = true;
+ double[] result = new double[len];
+ int sign = 1;
+ try {
+ for (int i = 0; i < len; i++) {
+ columns[i] = false;
+ result[i] = sign * determinant(matrix, 0, columns);
+ columns[i] = true;
+ sign = -sign;
+ }
+ } catch (ArrayIndexOutOfBoundsException e) {
+ throw new IllegalArgumentException("Matrix is wrong shape");
+ }
+ return new Pnt(result);
+ }
+
+ /* Pnts as simplices */
+
+ /**
+ * Determine the signed content (i.e., area or volume, etc.) of a simplex.
+ * @param simplex the simplex (as an array of Pnts)
+ * @return the signed content of the simplex
+ */
+ public static double content (Pnt[] simplex) {
+ Pnt[] matrix = new Pnt[simplex.length];
+ for (int i = 0; i < matrix.length; i++)
+ matrix[i] = simplex[i].extend(1);
+ int fact = 1;
+ for (int i = 1; i < matrix.length; i++) fact = fact*i;
+ return determinant(matrix) / fact;
+ }
+
+ /**
+ * Relation between this Pnt and a simplex (represented as an array of
+ * Pnts). Result is an array of signs, one for each vertex of the simplex,
+ * indicating the relation between the vertex, the vertex's opposite facet,
+ * and this Pnt.
+ *
+ * <pre>
+ * -1 means Pnt is on same side of facet
+ * 0 means Pnt is on the facet
+ * +1 means Pnt is on opposite side of facet
+ * </pre>
+ *
+ * @param simplex an array of Pnts representing a simplex
+ * @return an array of signs showing relation between this Pnt and simplex
+ * @throws IllegalArgumentExcpetion if the simplex is degenerate
+ */
+ public int[] relation (Pnt[] simplex) {
+ /* In 2D, we compute the cross of this matrix:
+ * 1 1 1 1
+ * p0 a0 b0 c0
+ * p1 a1 b1 c1
+ * where (a, b, c) is the simplex and p is this Pnt. The result is a
+ * vector in which the first coordinate is the signed area (all signed
+ * areas are off by the same constant factor) of the simplex and the
+ * remaining coordinates are the *negated* signed areas for the
+ * simplices in which p is substituted for each of the vertices.
+ * Analogous results occur in higher dimensions.
+ */
+ int dim = simplex.length - 1;
+ if (this.dimension() != dim)
+ throw new IllegalArgumentException("Dimension mismatch");
+
+ /* Create and load the matrix */
+ Pnt[] matrix = new Pnt[dim+1];
+ /* First row */
+ double[] coords = new double[dim+2];
+ for (int j = 0; j < coords.length; j++) coords[j] = 1;
+ matrix[0] = new Pnt(coords);
+ /* Other rows */
+ for (int i = 0; i < dim; i++) {
+ coords[0] = this.coordinates[i];
+ for (int j = 0; j < simplex.length; j++)
+ coords[j+1] = simplex[j].coordinates[i];
+ matrix[i+1] = new Pnt(coords);
+ }
+
+ /* Compute and analyze the vector of areas/volumes/contents */
+ Pnt vector = cross(matrix);
+ double content = vector.coordinates[0];
+ int[] result = new int[dim+1];
+ for (int i = 0; i < result.length; i++) {
+ double value = vector.coordinates[i+1];
+ if (Math.abs(value) <= 1.0e-6 * Math.abs(content)) result[i] = 0;
+ else if (value < 0) result[i] = -1;
+ else result[i] = 1;
+ }
+ if (content < 0) {
+ for (int i = 0; i < result.length; i++)
+ result[i] = -result[i];
+ }
+ if (content == 0) {
+ for (int i = 0; i < result.length; i++)
+ result[i] = Math.abs(result[i]);
+ }
+ return result;
+ }
+
+ /**
+ * Test if this Pnt is outside of simplex.
+ * @param simplex the simplex (an array of Pnts)
+ * @return simplex Pnt that "witnesses" outsideness (or null if not outside)
+ */
+ public Pnt isOutside (Pnt[] simplex) {
+ int[] result = this.relation(simplex);
+ for (int i = 0; i < result.length; i++) {
+ if (result[i] > 0) return simplex[i];
+ }
+ return null;
+ }
+
+ /**
+ * Test if this Pnt is on a simplex.
+ * @param simplex the simplex (an array of Pnts)
+ * @return the simplex Pnt that "witnesses" on-ness (or null if not on)
+ */
+ public Pnt isOn (Pnt[] simplex) {
+ int[] result = this.relation(simplex);
+ Pnt witness = null;
+ for (int i = 0; i < result.length; i++) {
+ if (result[i] == 0) witness = simplex[i];
+ else if (result[i] > 0) return null;
+ }
+ return witness;
+ }
+
+ /**
+ * Test if this Pnt is inside a simplex.
+ * @param simplex the simplex (an arary of Pnts)
+ * @return true iff this Pnt is inside simplex.
+ */
+ public boolean isInside (Pnt[] simplex) {
+ int[] result = this.relation(simplex);
+ for (int r: result) if (r >= 0) return false;
+ return true;
+ }
+
+ /**
+ * Test relation between this Pnt and circumcircle of a simplex.
+ * @param simplex the simplex (as an array of Pnts)
+ * @return -1, 0, or +1 for inside, on, or outside of circumcircle
+ */
+ public int vsCircumcircle (Pnt[] simplex) {
+ Pnt[] matrix = new Pnt[simplex.length + 1];
+ for (int i = 0; i < simplex.length; i++)
+ matrix[i] = simplex[i].extend(1, simplex[i].dot(simplex[i]));
+ matrix[simplex.length] = this.extend(1, this.dot(this));
+ double d = determinant(matrix);
+ int result = (d < 0)? -1 : ((d > 0)? +1 : 0);
+ if (content(simplex) < 0) result = - result;
+ return result;
+ }
+
+ /**
+ * Circumcenter of a simplex.
+ * @param simplex the simplex (as an array of Pnts)
+ * @return the circumcenter (a Pnt) of simplex
+ */
+ public static Pnt circumcenter (Pnt[] simplex) {
+ int dim = simplex[0].dimension();
+ if (simplex.length - 1 != dim)
+ throw new IllegalArgumentException("Dimension mismatch");
+ Pnt[] matrix = new Pnt[dim];
+ for (int i = 0; i < dim; i++)
+ matrix[i] = simplex[i].bisector(simplex[i+1]);
+ Pnt hCenter = cross(matrix); // Center in homogeneous coordinates
+ double last = hCenter.coordinates[dim];
+ double[] result = new double[dim];
+ for (int i = 0; i < dim; i++) result[i] = hCenter.coordinates[i] / last;
+ return new Pnt(result);
+ }
+
+ /**
+ * Main program (used for testing).
+ */
+ public static void main (String[] args) {
+ Pnt p = new Pnt(1, 2, 3);
+ System.out.println("Pnt created: " + p);
+ Pnt[] matrix1 = {new Pnt(1,2), new Pnt(3,4)};
+ Pnt[] matrix2 = {new Pnt(7,0,5), new Pnt(2,4,6), new Pnt(3,8,1)};
+ System.out.print("Results should be -2 and -288: ");
+ System.out.println(determinant(matrix1) + " " + determinant(matrix2));
+ Pnt p1 = new Pnt(1,1); Pnt p2 = new Pnt(-1,1);
+ System.out.println("Angle between " + p1 + " and " +
+ p2 + ": " + p1.angle(p2));
+ System.out.println(p1 + " subtract " + p2 + ": " + p1.subtract(p2));
+ Pnt v0 = new Pnt(0,0), v1 = new Pnt(1,1), v2 = new Pnt(2,2);
+ Pnt[] vs = {v0, new Pnt(0,1), new Pnt(1,0)};
+ Pnt vp = new Pnt(.1, .1);
+ System.out.println(vp + " isInside " + toString(vs) +
+ ": " + vp.isInside(vs));
+ System.out.println(v1 + " isInside " + toString(vs) +
+ ": " + v1.isInside(vs));
+ System.out.println(vp + " vsCircumcircle " + toString(vs) + ": " +
+ vp.vsCircumcircle(vs));
+ System.out.println(v1 + " vsCircumcircle " + toString(vs) + ": " +
+ v1.vsCircumcircle(vs));
+ System.out.println(v2 + " vsCircumcircle " + toString(vs) + ": " +
+ v2.vsCircumcircle(vs));
+ System.out.println("Circumcenter of " + toString(vs) + " is " +
+ circumcenter(vs));
+ }
+} \ No newline at end of file
diff --git a/delaunay/Triangle.java b/delaunay/Triangle.java
new file mode 100644
index 0000000..8b88a50
--- /dev/null
+++ b/delaunay/Triangle.java
@@ -0,0 +1,152 @@
+package delaunay;
+
+/*
+ * Copyright (c) 2007 by L. Paul Chew.
+ *
+ * Permission is hereby granted, without written agreement and without
+ * license or royalty fees, to use, copy, modify, and distribute this
+ * software and its documentation for any purpose, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * A Triangle is an immutable Set of exactly three Pnts.
+ *
+ * All Set operations are available. Individual vertices can be accessed via
+ * iterator() and also via triangle.get(index).
+ *
+ * Note that, even if two triangles have the same vertex set, they are
+ * *different* triangles. Methods equals() and hashCode() are consistent with
+ * this rule.
+ *
+ * @author Paul Chew
+ *
+ * Created December 2007. Replaced general simplices with geometric triangle.
+ *
+ */
+class Triangle extends ArraySet<Pnt> {
+
+ private int idNumber; // The id number
+ private Pnt circumcenter = null; // The triangle's circumcenter
+
+ private static int idGenerator = 0; // Used to create id numbers
+ public static boolean moreInfo = false; // True iff more info in toString
+
+ /**
+ * @param vertices the vertices of the Triangle.
+ * @throws IllegalArgumentException if there are not three distinct vertices
+ */
+ public Triangle (Pnt... vertices) {
+ this(Arrays.asList(vertices));
+ }
+
+ /**
+ * @param collection a Collection holding the Simplex vertices
+ * @throws IllegalArgumentException if there are not three distinct vertices
+ */
+ public Triangle (Collection<? extends Pnt> collection) {
+ super(collection);
+ idNumber = idGenerator++;
+ if (this.size() != 3)
+ throw new IllegalArgumentException("Triangle must have 3 vertices");
+ }
+
+ @Override
+ public String toString () {
+ if (!moreInfo) return "Triangle" + idNumber;
+ return "Triangle" + idNumber + super.toString();
+ }
+
+ /**
+ * Get arbitrary vertex of this triangle, but not any of the bad vertices.
+ * @param badVertices one or more bad vertices
+ * @return a vertex of this triangle, but not one of the bad vertices
+ * @throws NoSuchElementException if no vertex found
+ */
+ public Pnt getVertexButNot (Pnt... badVertices) {
+ Collection<Pnt> bad = Arrays.asList(badVertices);
+ for (Pnt v: this) if (!bad.contains(v)) return v;
+ throw new NoSuchElementException("No vertex found");
+ }
+
+ /**
+ * True iff triangles are neighbors. Two triangles are neighbors if they
+ * share a facet.
+ * @param triangle the other Triangle
+ * @return true iff this Triangle is a neighbor of triangle
+ */
+ public boolean isNeighbor (Triangle triangle) {
+ int count = 0;
+ for (Pnt vertex: this)
+ if (!triangle.contains(vertex)) count++;
+ return count == 1;
+ }
+
+ /**
+ * Report the facet opposite vertex.
+ * @param vertex a vertex of this Triangle
+ * @return the facet opposite vertex
+ * @throws IllegalArgumentException if the vertex is not in triangle
+ */
+ public ArraySet<Pnt> facetOpposite (Pnt vertex) {
+ ArraySet<Pnt> facet = new ArraySet<Pnt>(this);
+ if (!facet.remove(vertex))
+ throw new IllegalArgumentException("Vertex not in triangle");
+ return facet;
+ }
+
+ /**
+ * @return the triangle's circumcenter
+ */
+ public Pnt getCircumcenter () {
+ if (circumcenter == null)
+ circumcenter = Pnt.circumcenter(this.toArray(new Pnt[0]));
+ return circumcenter;
+ }
+
+ /* The following two methods ensure that a Triangle is immutable */
+
+ @Override
+ public boolean add (Pnt vertex) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public Iterator<Pnt> iterator () {
+ return new Iterator<Pnt>() {
+ private Iterator<Pnt> it = Triangle.super.iterator();
+ public boolean hasNext() {return it.hasNext();}
+ public Pnt next() {return it.next();}
+ public void remove() {throw new UnsupportedOperationException();}
+ };
+ }
+
+ /* The following two methods ensure that all triangles are different. */
+
+ @Override
+ public int hashCode () {
+ return (int)(idNumber^(idNumber>>>32));
+ }
+
+ @Override
+ public boolean equals (Object o) {
+ return (this == o);
+ }
+
+} \ No newline at end of file
diff --git a/delaunay/Triangulation.java b/delaunay/Triangulation.java
new file mode 100644
index 0000000..209e9e7
--- /dev/null
+++ b/delaunay/Triangulation.java
@@ -0,0 +1,281 @@
+package delaunay;
+
+/*
+ * Copyright (c) 2005, 2007 by L. Paul Chew.
+ *
+ * Permission is hereby granted, without written agreement and without
+ * license or royalty fees, to use, copy, modify, and distribute this
+ * software and its documentation for any purpose, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+import java.util.Set;
+
+/**
+ * A 2D Delaunay Triangulation (DT) with incremental site insertion.
+ *
+ * This is not the fastest way to build a DT, but it's a reasonable way to build
+ * a DT incrementally and it makes a nice interactive display. There are several
+ * O(n log n) methods, but they require that the sites are all known initially.
+ *
+ * A Triangulation is a Set of Triangles. A Triangulation is unmodifiable as a
+ * Set; the only way to change it is to add sites (via delaunayPlace).
+ *
+ * @author Paul Chew
+ *
+ * Created July 2005. Derived from an earlier, messier version.
+ *
+ * Modified November 2007. Rewrote to use AbstractSet as parent class and to use
+ * the Graph class internally. Tried to make the DT algorithm clearer by
+ * explicitly creating a cavity. Added code needed to find a Voronoi cell.
+ *
+ */
+public class Triangulation extends AbstractSet<Triangle> {
+
+ private Triangle mostRecent = null; // Most recently "active" triangle
+ private Graph<Triangle> triGraph; // Holds triangles for navigation
+
+ /**
+ * All sites must fall within the initial triangle.
+ * @param triangle the initial triangle
+ */
+ public Triangulation (Triangle triangle) {
+ triGraph = new Graph<Triangle>();
+ triGraph.add(triangle);
+ mostRecent = triangle;
+ }
+
+ /* The following two methods are required by AbstractSet */
+
+ @Override
+ public Iterator<Triangle> iterator () {
+ return triGraph.nodeSet().iterator();
+ }
+
+ @Override
+ public int size () {
+ return triGraph.nodeSet().size();
+ }
+
+ @Override
+ public String toString () {
+ return "Triangulation with " + size() + " triangles";
+ }
+
+ /**
+ * True iff triangle is a member of this triangulation.
+ * This method isn't required by AbstractSet, but it improves efficiency.
+ * @param triangle the object to check for membership
+ */
+ public boolean contains (Object triangle) {
+ return triGraph.nodeSet().contains(triangle);
+ }
+
+ /**
+ * Report neighbor opposite the given vertex of triangle.
+ * @param site a vertex of triangle
+ * @param triangle we want the neighbor of this triangle
+ * @return the neighbor opposite site in triangle; null if none
+ * @throws IllegalArgumentException if site is not in this triangle
+ */
+ public Triangle neighborOpposite (Pnt site, Triangle triangle) {
+ if (!triangle.contains(site))
+ throw new IllegalArgumentException("Bad vertex; not in triangle");
+ for (Triangle neighbor: triGraph.neighbors(triangle)) {
+ if (!neighbor.contains(site)) return neighbor;
+ }
+ return null;
+ }
+
+ /**
+ * Return the set of triangles adjacent to triangle.
+ * @param triangle the triangle to check
+ * @return the neighbors of triangle
+ */
+ public Set<Triangle> neighbors(Triangle triangle) {
+ return triGraph.neighbors(triangle);
+ }
+
+ /**
+ * Report triangles surrounding site in order (cw or ccw).
+ * @param site we want the surrounding triangles for this site
+ * @param triangle a "starting" triangle that has site as a vertex
+ * @return all triangles surrounding site in order (cw or ccw)
+ * @throws IllegalArgumentException if site is not in triangle
+ */
+ public List<Triangle> surroundingTriangles (Pnt site, Triangle triangle) {
+ if (!triangle.contains(site))
+ throw new IllegalArgumentException("Site not in triangle");
+ List<Triangle> list = new ArrayList<Triangle>();
+ Triangle start = triangle;
+ Pnt guide = triangle.getVertexButNot(site); // Affects cw or ccw
+ while (true) {
+ list.add(triangle);
+ Triangle previous = triangle;
+ triangle = this.neighborOpposite(guide, triangle); // Next triangle
+ guide = previous.getVertexButNot(site, guide); // Update guide
+ if (triangle == start) break;
+ }
+ return list;
+ }
+
+ /**
+ * Locate the triangle with point inside it or on its boundary.
+ * @param point the point to locate
+ * @return the triangle that holds point; null if no such triangle
+ */
+ public Triangle locate (Pnt point) {
+ Triangle triangle = mostRecent;
+ if (!this.contains(triangle)) triangle = null;
+
+ // Try a directed walk (this works fine in 2D, but can fail in 3D)
+ Set<Triangle> visited = new HashSet<Triangle>();
+ while (triangle != null) {
+ if (visited.contains(triangle)) { // This should never happen
+ System.out.println("Warning: Caught in a locate loop");
+ break;
+ }
+ visited.add(triangle);
+ // Corner opposite point
+ Pnt corner = point.isOutside(triangle.toArray(new Pnt[0]));
+ if (corner == null) return triangle;
+ triangle = this.neighborOpposite(corner, triangle);
+ }
+ // No luck; try brute force
+ System.out.println("Warning: Checking all triangles for " + point);
+ for (Triangle tri: this) {
+ if (point.isOutside(tri.toArray(new Pnt[0])) == null) return tri;
+ }
+ // No such triangle
+ System.out.println("Warning: No triangle holds " + point);
+ return null;
+ }
+
+ /**
+ * Place a new site into the DT.
+ * Nothing happens if the site matches an existing DT vertex.
+ * @param site the new Pnt
+ * @throws IllegalArgumentException if site does not lie in any triangle
+ */
+ public void delaunayPlace (Pnt site) {
+ // Uses straightforward scheme rather than best asymptotic time
+
+ // Locate containing triangle
+ Triangle triangle = locate(site);
+ // Give up if no containing triangle or if site is already in DT
+ if (triangle == null)
+ throw new IllegalArgumentException("No containing triangle");
+ if (triangle.contains(site)) return;
+
+ // Determine the cavity and update the triangulation
+ Set<Triangle> cavity = getCavity(site, triangle);
+ mostRecent = update(site, cavity);
+ }
+
+ /**
+ * Determine the cavity caused by site.
+ * @param site the site causing the cavity
+ * @param triangle the triangle containing site
+ * @return set of all triangles that have site in their circumcircle
+ */
+ private Set<Triangle> getCavity (Pnt site, Triangle triangle) {
+ Set<Triangle> encroached = new HashSet<Triangle>();
+ Queue<Triangle> toBeChecked = new LinkedList<Triangle>();
+ Set<Triangle> marked = new HashSet<Triangle>();
+ toBeChecked.add(triangle);
+ marked.add(triangle);
+ while (!toBeChecked.isEmpty()) {
+ triangle = toBeChecked.remove();
+ if (site.vsCircumcircle(triangle.toArray(new Pnt[0])) == 1)
+ continue; // Site outside triangle => triangle not in cavity
+ encroached.add(triangle);
+ // Check the neighbors
+ for (Triangle neighbor: triGraph.neighbors(triangle)){
+ if (marked.contains(neighbor)) continue;
+ marked.add(neighbor);
+ toBeChecked.add(neighbor);
+ }
+ }
+ return encroached;
+ }
+
+ /**
+ * Update the triangulation by removing the cavity triangles and then
+ * filling the cavity with new triangles.
+ * @param site the site that created the cavity
+ * @param cavity the triangles with site in their circumcircle
+ * @return one of the new triangles
+ */
+ private Triangle update (Pnt site, Set<Triangle> cavity) {
+ Set<Set<Pnt>> boundary = new HashSet<Set<Pnt>>();
+ Set<Triangle> theTriangles = new HashSet<Triangle>();
+
+ // Find boundary facets and adjacent triangles
+ for (Triangle triangle: cavity) {
+ theTriangles.addAll(neighbors(triangle));
+ for (Pnt vertex: triangle) {
+ Set<Pnt> facet = triangle.facetOpposite(vertex);
+ if (boundary.contains(facet)) boundary.remove(facet);
+ else boundary.add(facet);
+ }
+ }
+ theTriangles.removeAll(cavity); // Adj triangles only
+
+ // Remove the cavity triangles from the triangulation
+ for (Triangle triangle: cavity) triGraph.remove(triangle);
+
+ // Build each new triangle and add it to the triangulation
+ Set<Triangle> newTriangles = new HashSet<Triangle>();
+ for (Set<Pnt> vertices: boundary) {
+ vertices.add(site);
+ Triangle tri = new Triangle(vertices);
+ triGraph.add(tri);
+ newTriangles.add(tri);
+ }
+
+ // Update the graph links for each new triangle
+ theTriangles.addAll(newTriangles); // Adj triangle + new triangles
+ for (Triangle triangle: newTriangles)
+ for (Triangle other: theTriangles)
+ if (triangle.isNeighbor(other))
+ triGraph.add(triangle, other);
+
+ // Return one of the new triangles
+ return newTriangles.iterator().next();
+ }
+
+ /**
+ * Main program; used for testing.
+ */
+ public static void main (String[] args) {
+ Triangle tri =
+ new Triangle(new Pnt(-10,10), new Pnt(10,10), new Pnt(0,-10));
+ System.out.println("Triangle created: " + tri);
+ Triangulation dt = new Triangulation(tri);
+ System.out.println("DelaunayTriangulation created: " + dt);
+ dt.delaunayPlace(new Pnt(0,0));
+ dt.delaunayPlace(new Pnt(1,0));
+ dt.delaunayPlace(new Pnt(0,1));
+ System.out.println("After adding 3 points, we have a " + dt);
+ Triangle.moreInfo = true;
+ System.out.println("Triangles: " + dt.triGraph.nodeSet());
+ }
+} \ No newline at end of file