From 08d5f7b0a0b24c042aa5976f66bf3a1b5b754478 Mon Sep 17 00:00:00 2001 From: Richard Zahoransky Date: Mon, 7 Nov 2011 16:29:56 +0100 Subject: Localization Code. How-To will follow... --- delaunay/ArraySet.java | 104 ++++++++++ delaunay/DelaunayAp.java | 429 ++++++++++++++++++++++++++++++++++++++++ delaunay/Graph.java | 108 ++++++++++ delaunay/Pnt.java | 470 ++++++++++++++++++++++++++++++++++++++++++++ delaunay/Triangle.java | 152 ++++++++++++++ delaunay/Triangulation.java | 281 ++++++++++++++++++++++++++ 6 files changed, 1544 insertions(+) create mode 100644 delaunay/ArraySet.java create mode 100644 delaunay/DelaunayAp.java create mode 100644 delaunay/Graph.java create mode 100644 delaunay/Pnt.java create mode 100644 delaunay/Triangle.java create mode 100644 delaunay/Triangulation.java (limited to 'delaunay') 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 extends AbstractSet { + + private ArrayList 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(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 collection) { + items = new ArrayList(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 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 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(); + } + + /** + * 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 done = new HashSet(initialTriangle); + for (Triangle triangle : dt) + for (Pnt site: triangle) { + if (done.contains(site)) continue; + done.add(site); + List 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 { + + private Map> theNeighbors = // Node -> adjacent nodes + new HashMap>(); + private Set 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()); + } + + /** + * 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 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 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. + * + *
+     *   -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
+     * 
+ * + * @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 { + + 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 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 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 facetOpposite (Pnt vertex) { + ArraySet facet = new ArraySet(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 iterator () { + return new Iterator() { + private Iterator 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 { + + private Triangle mostRecent = null; // Most recently "active" triangle + private Graph 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(); + triGraph.add(triangle); + mostRecent = triangle; + } + + /* The following two methods are required by AbstractSet */ + + @Override + public Iterator 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 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 surroundingTriangles (Pnt site, Triangle triangle) { + if (!triangle.contains(site)) + throw new IllegalArgumentException("Site not in triangle"); + List list = new ArrayList(); + 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 visited = new HashSet(); + 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 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 getCavity (Pnt site, Triangle triangle) { + Set encroached = new HashSet(); + Queue toBeChecked = new LinkedList(); + Set marked = new HashSet(); + 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 cavity) { + Set> boundary = new HashSet>(); + Set theTriangles = new HashSet(); + + // Find boundary facets and adjacent triangles + for (Triangle triangle: cavity) { + theTriangles.addAll(neighbors(triangle)); + for (Pnt vertex: triangle) { + Set 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 newTriangles = new HashSet(); + for (Set 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 -- cgit v1.2.3-55-g7522