pnt.java

Voronoi图生成算法 ,Voronoi(沃洛诺依)多边形网络常常被用来做为计算机仿真模型.由于按照定义形成Voronoi多边形网络较难用程序实现,人们多采用Delauney(狄洛尼)三角形的方法完

/*
 * Copyright (c) 2005 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.
 */
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.
        coordinates = new double[coords.length];
        System.arraycopy(coords, 0, coordinates, 0, coords.length);
    }
    
    /**
     * Constructor.
     * @param coordA
     * @param coordB
     */
    public Pnt (double coordA, double coordB) {
        this(new double[] {coordA, coordB});
    }
    
    /**
     * Constructor.
     * @param coordA
     * @param coordB
     * @param coordC
     */
    public Pnt (double coordA, double coordB, double coordC) {
        this(new double[] {coordA, coordB, coordC});
    }
    
    /**
     * Create a String for this Pnt.
     * @return a String representation of this Pnt.
     */
    public String toString () {
        if (coordinates.length == 0) return "()";
        String result = "Pnt(" + coordinates[0];
        for (int i = 1; i < coordinates.length; i++)
            result = result + "," + coordinates[i];
        result = result + ")";
        return result;
    }
    
    /**
     * Equality.
     * @param other the other Object to compare to
     * @return true iff the Pnts have the same coordinates
     */
    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;
    }
    
    /**
     * HashCode.
     * @return the hashCode for this Pnt
     */
    public int hashCode () {
        int hash = 0;
        for (int i = 0; i < this.coordinates.length; i++) {
            long bits = Double.doubleToLongBits(this.coordinates[i]);
            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) {
        int dim = dimCheck(point);
        Pnt diff = this.subtract(point);
        Pnt sum = this.add(point);
        double dot = diff.dot(sum);
        return diff.extend(new double[] {-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) {
        StringBuffer buf = new StringBuffer("{");
        for (int i = 0; i < matrix.length; i++) buf.append(" " + matrix[i]);
        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())