Application: gvSIG desktop

package org.gvsig.jts.voronoi.chen;

/**

 * Voronoi diagram

 *

 * Copyright(c) 1998 Ping-Che Chen

 *

 * This program defines the segemnt.

 *

 */

public class Segment {

  public Coord p1, p2;

  public boolean i1, i2;    // true if not the end of a segment

  public String toString() {

    return p1 + "-" + p2;

  }

  public static Segment getMidNormal(final Segment l) {

    if(l.i1 || l.i2) {

      return null;

    }

    Segment s = new Segment();

    s.p1 = new Coord();

    s.p2 = new Coord();

    s.i1 = s.i2 = true;

    if(l.p1.y == l.p2.y) {

      s.p1.x = s.p2.x = (l.p1.x + l.p2.x) / 2;

      s.p1.y = l.p1.y - 1;

      s.p2.y = l.p1.y + 1;

    }

    else {

      double x = (l.p2.x + l.p1.x) / 2;

      double y = (l.p2.y + l.p1.y) / 2;

      double m = (l.p1.x - l.p2.x) / (l.p2.y - l.p1.y);

      double b = y - m * x;

      s.p1.x = l.p1.x;

      s.p2.x = l.p2.x;

      if(s.p1.x == s.p2.x) {

	s.p2.x += 1;

      }

      s.p1.y = m * s.p1.x + b;

      s.p2.y = m * s.p2.x + b;

    }

    return s;

  }

  public static Coord getIntersect(final Segment l1, final Segment l2) {

    double m1, m2, b1, b2;

    Coord result = new Coord();

    l1.normalize();

    l2.normalize();

    if(l1.p2.x == l1.p1.x) {

      if(l2.p2.x == l2.p1.x) {

	return null;

      }

      else {

	m2 = (l2.p2.y - l2.p1.y) / (l2.p2.x - l2.p1.x);

	b2 = l2.p1.y - m2 * l2.p1.x;

	result.x = l1.p1.x;

	result.y = l1.p1.x * m2 + b2;

      }

    }

    else if(l2.p2.x == l2.p1.x) {

      if(l1.p2.x == l1.p1.x) {

	return null;

      }

      else {

	m1 = (l1.p2.y - l1.p1.y) / (l1.p2.x - l1.p1.x);

	b1 = l1.p1.y - m1 * l1.p1.x;

	result.x = l2.p1.x;

	result.y = l2.p1.x * m1 + b1;

      }

    }

    else {

      m1 = (l1.p2.y - l1.p1.y) / (l1.p2.x - l1.p1.x);

      m2 = (l2.p2.y - l2.p1.y) / (l2.p2.x - l2.p1.x);

      b1 = l1.p1.y - m1 * l1.p1.x;

      b2 = l2.p1.y - m2 * l2.p1.x;

      if(m1 == m2) {

	return null;

      }

      result.x = (b2 - b1) / (m1 - m2);

      result.y = (m1 * b2 - m2 * b1) / (m1 - m2);

    }

    if(!l1.i1) {

      if(result.x < l1.p1.x)

	return null;

      if(result.x == l1.p1.x && result.y < l1.p1.y)

	return null;

    }

    if(!l1.i2) {

      if(result.x > l1.p2.x)

	return null;

      if(result.x == l1.p2.x && result.y > l1.p2.y)

	return null;

    }

    if(!l2.i1) {

      if(result.x < l2.p1.x)

	return null;

      if(result.x == l2.p1.x && result.y < l2.p1.y)

	return null;

    }

    if(!l2.i2) {

      if(result.x > l2.p2.x)

	return null;

      if(result.x == l2.p2.x && result.y > l2.p2.y)

	return null;

    }

    return result;

  }

  public void normalize() {

    if(p1.x > p2.x || (p1.x == p2.x && p1.y > p2.y)) {

      Coord t;

      t = p1;

      p1 = p2;

      p2 = t;

      boolean t2;

      t2 = i1;

      i1 = i2;

      i2 = t2;

    }

  }

}

package org.gvsig.jts.voronoi.chen;

/**

 * Voronoi diagram

 *

 * Copyright(c) 1998 Ping-Che Chen

 *

 * This is the main program.

 *

 */

import java.applet.Applet;

import java.awt.Color;

import java.awt.Graphics;

import java.awt.event.MouseAdapter;

import java.awt.event.MouseEvent;

import java.util.Enumeration;

import java.util.Random;

public class Main extends Applet {

  List vertices;

  int status = 1;

  int v = 0;

  Vertex[] diagram;

  String message;

  public void init() {

    vertices = new List();

    addMouseListener(new MyMouseListener());

  }

  public void paint(Graphics g) {

    g.setColor(Color.red);

    g.fillRect(0, 0, 10, 10);

    g.setColor(Color.green);

    g.fillRect(10, 0, 10, 10);

    g.setColor(Color.blue);

    g.fillRect(20, 0, 10, 10);

    g.setColor(Color.white);

    g.fillRect(30, 0, 10, 10);

    g.setColor(Color.black);

    Enumeration i = vertices.elements();

    while(i.hasMoreElements()) {

      Coord p = (Coord)i.nextElement();

      g.fillArc((int)p.x - 1, (int)(-p.y) - 1, 3, 3, 0, 360);

    }

    if(status == 2) {

      for(int j = 0; j < diagram.length; j++) {

	i = diagram[j].edges.elements();

	while(i.hasMoreElements()) {

	  VoronoiSegment s = (VoronoiSegment)i.nextElement();

	  if(s.floating) {

	    continue;

	  }

	  int x1, y1, x2, y2;

	  int rx1, ry1, rx2, ry2;

	  double dx = s.p2.x - s.p1.x;

	  double dy = s.p2.y - s.p1.y;

	  double m = dy / dx;

	  double b = s.p1.y - m * s.p1.x;

	  if(dx > 0) {

	    rx1 = 0;

	    rx2 = getSize().width;

	  }

	  else {

	    rx1 = getSize().width;

	    rx2 = 0;

	  }

	  if(dy > 0) {

	    ry1 = 0;

	    ry2 = getSize().height;

	  }

	  else {

	    ry1 = getSize().height;

	    ry2 = 0;

	  }

	  x1 = (int)s.p1.x;

	  y1 = -(int)s.p1.y;

	  x2 = (int)s.p2.x;

	  y2 = -(int)s.p2.y;

	  if(s.i1) {

	    if(dx == 0) {

	      y1 = ry1;

	    }

	    else {

	      x1 = rx1;

	      y1 = -(int)(m * rx1 + b);

	    }

	  }

	  if(s.i2) {

	    if(dx == 0) {

	      y2 = ry2;

	    }

	    else {

	      x2 = rx2;

	      y2 = -(int)(m * rx2 + b);

	    }

	  }

	  g.setColor(Color.black);

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

	}

      }

    }

    else if(status == 3) {

      for(int j = 0; j < diagram.length; j++) {

	i = diagram[j].edges.elements();

	while(i.hasMoreElements()) {

	  VoronoiSegment s = (VoronoiSegment)i.nextElement();

	  if(s.floating)

	    continue;

	  int x1 = (int)s.v1.x;

	  int y1 = -(int)s.v1.y;

	  int x2 = (int)s.v2.x;

	  int y2 = -(int)s.v2.y;

	  g.setColor(Color.black);

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

	}

      }

    }

  }

  public void update(Graphics g) {

    Color old = g.getColor();

    g.setColor(Color.lightGray);

    g.fillRect(0, 0, getSize().width, getSize().height);

    g.setColor(old);

    paint(g);

  }

  class MyMouseListener extends MouseAdapter {

    public void mouseClicked(MouseEvent e) {

      if(e.getX() < 30 && e.getX() >= 20 && e.getY() < 10) {

	status = 1;

	vertices.removeAll();

	v = 0;

	repaint();

      }

      else if(status < 2) {

	if(e.getX() < 20 && e.getX() >= 10 && e.getY() < 10) {

	  Random r = new Random();

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

	    int x = Math.abs(r.nextInt()) % getSize().width;

	    int y = Math.abs(r.nextInt()) % getSize().height;

	    Coord p = new Coord();

	    p.x = x;

	    p.y = -y;

	    vertices.insertTail(p);

	  }

	  v += 10;

	  repaint();

	}

	else if(e.getX() < 10 && e.getY() < 10) {

	  status++;

	  Coord[] t = new Coord[v];

	  Enumeration p = vertices.elements();

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

	    t[i] = (Coord)p.nextElement();

	  }

	  Voronoi.g = getGraphics();

	  Voronoi.row = 1;

	  diagram = Voronoi.generate(t);

	  repaint();

	}

	else {

	  Coord p = new Coord();

	  p.x = e.getX();

	  p.y = -e.getY();

	  vertices.insertTail(p);

	  v++;

	  repaint();

	}

      }

      else if(e.getX() < 40 && e.getX() >= 30 && e.getY() < 10) {

	if(status == 2)

	  status = 3;

	else

	  status = 2;

	repaint();

      }

    }

  }

}

package org.gvsig.jts.voronoi.chen;

/**

 * Voronoi Diagram

 *

 * Copyright(c) 1998 Ping-Che Chen

 *

 * This is the definition of the coordinate system.

 *

 */

public class Coord {

  public double x, y;

  public String toString() {

    return "(" + x + "," + y + ")";

  }

  public boolean equals(final Coord p) {

    if(Math.abs(p.x - x) < 1E-5 && Math.abs(p.y - y) < 1E-5)

      return true;

    else

      return false;

  }

}

package org.gvsig.jts.voronoi.chen;

/**

 * Voronoi diagram

 *

 * Copyright(c) 1998 Ping-Che Chen

 *

 * This program deals with the convex hull in the Voronoi problem.

 */

public class ConvexHull {

  public Coord[] points;

  private static class NewCoord {

    public Coord point;

    public double angle;

    public int group;

  }

  /** calculates (one of) the supporting line

   *  note: no optimized version, need O(N log N) time

   */

  public static Segment[] getSupportLine(final ConvexHull ch1, final ConvexHull ch2, ConvexHull newch) {

    NewCoord[] a = new NewCoord[ch1.points.length + ch2.points.length];

    Coord o = new Coord();

    int[] c = new int[ch1.points.length + ch2.points.length];

    if(ch1.points[0].y < ch2.points[0].y) {

      o = ch1.points[0];

    }

    else {

      o = ch2.points[0];

    }

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

      a[i] = new NewCoord();

      a[i].point = ch1.points[i];

      a[i].angle = angle(o, ch1.points[i]);

      a[i].group = 1;

    }

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

      a[i + ch1.points.length] = new NewCoord();

      a[i + ch1.points.length].point = ch2.points[i];

      a[i + ch1.points.length].angle = angle(o, ch2.points[i]);

      a[i + ch1.points.length].group = 2;

    }

    sort(a, 0, a.length);

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

      c[i] = -1;

    }

    c[0] = 0;

    c[1] = 1;

    int j = 2;

    for(int i = 2; i < c.length; i++) {

      while(ccw(a[c[j-2]].point, a[c[j-1]].point, a[i].point) < 0) {

	j--;

      }

      c[j++] = i;

    }

    Segment[] s = new Segment[2];

    j = 1;

    while(j < c.length && c[j] >= 0) {

      if(a[c[j]].group != a[c[j-1]].group) {

	break;

      }

      j++;

    }

    s[0] = new Segment();

    s[0].p1 = a[c[j-1]].point;

    s[0].p2 = a[c[j]].point;

    j++;

    while(j < c.length && c[j] >= 0) {

      if(a[c[j]].group != a[c[j-1]].group) {

	break;

      }

      j++;

    }

    if(j < c.length && c[j] >= 0) {

      s[1] = new Segment();

      s[1].p1 = a[c[j-1]].point;

      s[1].p2 = a[c[j]].point;

    }

    else if(a[c[j-1]].group != a[c[0]].group) {

      s[1] = new Segment();

      s[1].p1 = a[c[j-1]].point;

      s[1].p2 = a[c[0]].point;

    }

    else {

      s[1] = null;

    }

    if(s[1] != null && s[1].p1 == s[0].p1 && s[1].p2 == s[0].p2) {

      s[1] = null;

    }

    if(newch != null) {

      int i = 0;

      while(i < c.length && c[i] >= 0) i++;

      newch.points = new Coord[i];

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

	newch.points[k] = a[c[k]].point;

      }

    }

    return s;

  }

  private static int ccw(final Coord p1, final Coord p2, final Coord p3) {

    double a, b, x, y;

    x = p2.x - p1.x;

    y = p2.y - p1.y;

    a = p3.x - p1.x;

    b = p3.y - p1.y;

    double t = b * x - a * y;

    if(t > 0)

      return 1;

    else if(t < 0)

      return -1;

    else

      return 0;

  }

  /** compute the 'angle' which is not truly the angle */

  private static double angle(final Coord p1, final Coord p2) {

    double x, y;

    x = p2.x - p1.x;

    y = p2.y - p1.y;

    if(x == 0 && y == 0)

      return -1;

    double t = y / (Math.abs(x) + Math.abs(y));

    if(x < 0) {

      t = 2 - t;

    }

    else if(y < 0) {

      t = 4 + t;

    }

    return t;

  }

  /** sort */

  private static void sort(NewCoord[] s, int start, int end) {

    if(end - start > 1) {

      sort(s, start, (start + end) / 2);

      sort(s, (start + end) / 2, end);

      NewCoord[] t = new NewCoord[end - start];

      int i = start;

      int j = (start + end) / 2;

      int k = 0;

      while(i < (start + end) / 2 && j < end) {

	if(s[i].angle < s[j].angle) {

	  t[k++] = s[i++];

	}

	else {

	  t[k++] = s[j++];

	}

      }

      while(i < (start + end) / 2) {

	t[k++] = s[i++];

      }

      while(j < end) {

	t[k++] = s[j++];

      }

      for(k = start; k < end; k++) {

	s[k] = t[k - start];

      }

    }

  }

}

package org.gvsig.jts.voronoi.chen;

/**

 * Voronoi diagram

 *

 * Copyright(c) 1998 Ping-Che Chen

 *

 * Linked List

 *

 */

import java.util.Enumeration;

import java.util.NoSuchElementException;

public class List {

  static class Node {

    Object p;

    Node next;

    Node prev;

  }

  public static class ForwardEnumeration implements Enumeration {

    private Node current;

    ForwardEnumeration(Node n) {

      current = n;

    }

    public boolean hasMoreElements() {

      return current != null;

    }

    public Object nextElement() {

      if(current != null) {

	Object p = current.p;

	current = current.next;

	return p;

      }

      else {

	throw new NoSuchElementException();

      }

    }

  }

  public static class BackwardEnumeration implements Enumeration {

    private Node current;

    BackwardEnumeration(Node n) {

      current = n;

    }

    public boolean hasMoreElements() {

      return current != null;

    }

    public Object nextElement() {

      if(current != null) {

	Object p = current.p;

	current = current.prev;

	return p;

      }

      else {

	throw new NoSuchElementException();

      }

    }

  }

  private Node head, tail;

  public List() {

    head = tail = null;

  }

  public void insertHead(Object p) {

    Node n = new Node();

    n.p = p;

    n.next = head;

    n.prev = null;

    if(head != null)

      head.prev = n;

    head = n;

    if(tail == null) {

      tail = n;

    }

  }

  public void insertTail(Object p) {

    Node n = new Node();

    n.p = p;

    n.next = null;

    n.prev = tail;

    if(tail != null)

      tail.next = n;

    tail = n;

    if(head == null) {

      head = n;

    }

  }

  public boolean isEmpty() {

    return head == null;

  }

  public Object firstElement() throws NoSuchElementException {

    if(head == null)

      throw new NoSuchElementException();

    return head.p;

  }

  public Object lastElement() throws NoSuchElementException {

    if(tail == null)

      throw new NoSuchElementException();

    return tail.p;

  }

  public boolean contains(Object p) {

    Node n = head;

    while(n != null) {

      if(n.p == p)

	return true;

      else

	n = n.next;

    }

    return false;

  }

  public boolean remove(Object p) {

    Node n = head;

    while(n != null) {

      if(n.p == p) {

	if(n.prev != null) {

	  n.prev.next = n.next;

	}

	if(n.next != null) {

	  n.next.prev = n.prev;

	}

	return true;

      }

      else {

	n = n.next;

      }

    }

    return false;

  }

  public void removeAll() {

    head = tail = null;

  }

  public Enumeration elements() {

    return new ForwardEnumeration(head);

  }

  public Enumeration elementsR() {

    return new BackwardEnumeration(tail);

  }

}

package org.gvsig.jts.voronoi.chen;

/**

 * Voronoi diagram

 *

 * Copyright(c) 1998 Ping-Che Chen

 *

 * This programs contains the main part of the Voronoi diagram

 * generators.

 */

import java.awt.Graphics;

import java.util.Enumeration;

public class Voronoi {

  private static class CompoundLine {

    public Coord point;

    public Segment line;

  }

  public static Graphics g;

  public static int row;

  /** generate the Voronoi diagram */

  public static Vertex[] generate(final Coord[] points) {

    Vertex[] v = new Vertex[points.length];

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

      v[i] = new Vertex();

      v[i].x = points[i].x;

      v[i].y = points[i].y;

      v[i].originalOrder = i;

    }

    sort(v, 0, v.length);

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

      v[i].number = i;

    }

    internal(v, 0, v.length);

    return v;

  }

  /** the internal help-function */

  private static ConvexHull internal(Vertex[] points, int start, int end) {

    if(end - start > 1) {

      ConvexHull ch1 = internal(points, start, (start + end) / 2);

      ConvexHull ch2 = internal(points, (start + end) / 2, end);

      return merge(points, ch1, ch2, start, (start + end) / 2, end);

    }

    else {

      ConvexHull ch = new ConvexHull();

      ch.points = new Coord[1];

      ch.points[0] = points[start];

      return ch;

    }

  }

  /** merges two adjacent exclusive Voronoi diagrams */

  private static ConvexHull merge(Vertex[] points, ConvexHull ch1, ConvexHull ch2, int start, int mid, int end) { 

    ConvexHull ch = new ConvexHull();

    Segment[] supports = ConvexHull.getSupportLine(ch1, ch2, ch);

    Segment support = supports[0];

    Segment line = Segment.getMidNormal(support);

    List intersects;

    intersects = getAllIntersects(line, support);

    CompoundLine p = findFirstPoint(line, intersects, support);

    Vertex v1 = (Vertex)support.p1;

    Vertex v2 = (Vertex)support.p2;

    VoronoiSegment l = new VoronoiSegment(v1, v2);

    l.p1 = line.p1;

    l.p2 = line.p2;

    l.i1 = line.i1;

    l.i2 = line.i2;

    v1.edges.insertTail(l);

    v2.edges.insertTail(l);

    while(p != null) {

      if(supports[1] != null && support.p1 == supports[1].p2 && support.p2 == supports[1].p1) {

	break;

      }

      support = findSupportLine(p, v1, v2);

      line = Segment.getMidNormal(support);

      cutLine(line, p, support);

      cutOldLine(v1, v2, p);

      intersects = getAllIntersects(line, support);

      p = findNextPoint(line, intersects, support);

      v1 = (Vertex)support.p1;

      v2 = (Vertex)support.p2;

      l = new VoronoiSegment(v1, v2);

      l.p1 = line.p1;

      l.p2 = line.p2;

      l.i1 = line.i1;

      l.i2 = line.i2;

      v1.edges.insertTail(l);

      v2.edges.insertTail(l);

    }

    return ch;

  }

  private static void cutOldLine(Vertex v1, Vertex v2, CompoundLine p) {

    VoronoiSegment l = (VoronoiSegment)p.line;

    Vertex O, A;

    double dx, dy;

    if(v1 == l.v1 || v2 == l.v1) {

      O = l.v1;

    }

    else {

      O = l.v2;

    }

    if(v1 == O) {

      A = v2;

    }

    else {

      A = v1;

    }

    dx = l.p1.x - l.p2.x;

    dy = l.p1.y - l.p2.y;

    if(l.i1) {

      l.p1.x = p.point.x + dx;

      l.p1.y = p.point.y + dy;

    }

    if(l.i2) {

      l.p2.x = p.point.x - dx;

      l.p2.y = p.point.y - dy;

    }

    double dx1, dy1, dx2, dy2;

    dx1 = l.p1.x - O.x;

    dy1 = l.p1.y - O.y;

    dx2 = l.p1.x - A.x;

    dy2 = l.p1.y - A.y;

    Coord oldp = null;

    if(dx1 * dx1 + dy1 * dy1 < dx2 * dx2 + dy2 * dy2) {

      if(!l.i2) {

	oldp = l.p2;

      }

      l.p2 = p.point;

      l.i2 = false;

    }

    else {

      if(!l.i1) {

	oldp = l.p1;

      }

      l.p1 = p.point;

      l.i1 = false;

    }

    if(oldp != null && oldp != p.point) {

      removeOldLines(oldp, O);

    }

  }

  /** remove "floating" lines */

  private static void removeOldLines(Coord p, Vertex v) {

    Coord oldp = null;

    while(oldp != p) {

      oldp = p;

      Enumeration i = v.edges.elements();

      while(i.hasMoreElements()) {

	VoronoiSegment s = (VoronoiSegment)i.nextElement();

	if(s.floating)

	  continue;

	if(!s.i1 && s.p1 == p) {

	  s.floating = true;

	  if(!s.i2) {

	    p = s.p2;

	  }

	  break;

	}

	else if(!s.i2 && s.p2 == p) {

	  s.floating = true;

	  if(!s.i1) {

	    p = s.p1;

	  }

	  break;

	}

      }

    }

  }

  /** Cut the mid-normal line */

  private static Segment cutLine(final Segment line, CompoundLine p, Segment s) {

    double dx, dy;

    dx = line.p1.x - line.p2.x;

    dy = line.p1.y - line.p2.y;

    line.p1 = p.point;

    line.i1 = false;

    if(s.p1.x > s.p2.x) {

      if(dy < 0) {

	dy = -dy;

	dx = -dx;

      }

      line.p2 = new Coord();

      line.p2.x = line.p1.x - dx;

      line.p2.y = line.p1.y - dy;

    }

    else if(s.p1.x < s.p2.x) {

      if(dy < 0) {

	dy = -dy;

	dx = -dx;

      }

      line.p2 = new Coord();

      line.p2.x = line.p1.x + dx;

      line.p2.y = line.p1.y + dy;

    }

    else if(s.p1.y < s.p2.y) {

      if(dx < 0) {

	dx = -dx;

	dy = -dy;

      }

      line.p2 = new Coord();

      line.p2.x = line.p1.x - dx;

      line.p2.y = line.p1.y - dy;

    }

    else {

      if(dx < 0) {

	dx = -dx;

	dy = -dy;

      }

      line.p2 = new Coord();

      line.p2.x = line.p1.x + dx;

      line.p2.y = line.p1.y + dy;

    }

    return line;

  }

  /** find next supporting line */

  private static Segment findSupportLine(CompoundLine p, Vertex v1, Vertex v2) {

    VoronoiSegment s = (VoronoiSegment)p.line;

    Segment r = new Segment();

    if(s.v1 == v1) {

      r.p1 = s.v2;

      r.p2 = v2;

    }

    else if(s.v1 == v2) {

      r.p1 = v1;

      r.p2 = s.v2;

    }

    else if(s.v2 == v1) {

      r.p1 = s.v1;

      r.p2 = v2;

    }

    else {

      r.p1 = v1;

      r.p2 = s.v1;

    }

    return r;

  }

  /** get all intersects */

  private static List getAllIntersects(final Segment l, final Segment s) {

    List intersects = new List();

    Vertex v1 = (Vertex)s.p1;

    Vertex v2 = (Vertex)s.p2;

    Segment t = new Segment();

    t.p1 = l.p1;

    t.p2 = l.p2;

    t.i1 = l.i1;

    t.i2 = l.i2;

    Enumeration i;

    i = v1.edges.elements();

    while(i.hasMoreElements()) {

      VoronoiSegment ss = (VoronoiSegment)i.nextElement();

      Segment sss = new Segment();

      sss.p1 = ss.p1;

      sss.p2 = ss.p2;

      sss.i1 = ss.i1;

      sss.i2 = ss.i2;

      Coord p = Segment.getIntersect(sss, t);

      if(p != null) {

	CompoundLine ll = new CompoundLine();

	ll.point = p;

	ll.line = ss;

	intersects.insertTail(ll);

      }

    }

    i = v2.edges.elements();

    while(i.hasMoreElements()) {

      VoronoiSegment ss = (VoronoiSegment)i.nextElement();

      Segment sss = new Segment();

      sss.p1 = ss.p1;

      sss.p2 = ss.p2;

      sss.i1 = ss.i1;

      sss.i2 = ss.i2;

      Coord p = Segment.getIntersect(sss, t);

      if(p != null) {

	CompoundLine ll = new CompoundLine();

	ll.point = p;

	ll.line = ss;

	intersects.insertTail(ll);

      }

    }

    return intersects;

  } 

  /** find first point */

  private static CompoundLine findFirstPoint(Segment line, final List intersects, final Segment s) {

    CompoundLine m;

    Enumeration i = intersects.elements();

    if(!i.hasMoreElements())

      return null;

    m = (CompoundLine)i.nextElement();

    double dx = line.p1.x - line.p2.x;

    double dy = line.p1.y - line.p2.y;

    if(s.p1.x > s.p2.x) {

      // find max y

      while(i.hasMoreElements()) {

	CompoundLine k = (CompoundLine)i.nextElement();

	if(k.point.y > m.point.y) {

	  m = k;

	}

      }

      if(dy < 0) {

	dx = -dx;

	dy = -dy;

      }

      line.p1 = m.point;

      line.p2.x = m.point.x + dx;

      line.p2.y = m.point.y + dy;

      line.i1 = false;

    }

    else if(s.p1.x < s.p2.x) {

      // find min y

      while(i.hasMoreElements()) {

	CompoundLine k = (CompoundLine)i.nextElement();

	if(k.point.y < m.point.y) {

	  m = k;

	}

      }

      if(dy < 0) {

	dx = -dx;

	dy = -dy;

      }

      line.p1 = m.point;

      line.p2.x = m.point.x - dx;

      line.p2.y = m.point.y - dy;

      line.i1 = false;

    }

    else if(s.p1.y < s.p2.y) {

      // find max x

      while(i.hasMoreElements()) {

	CompoundLine k = (CompoundLine)i.nextElement();

	if(k.point.x > m.point.x) {

	  m = k;

	}

      }

      if(dx < 0) {

	dx = -dx;

	dy = -dy;

      }

      line.p1 = m.point;

      line.p2.x = m.point.x + dx;

      line.p2.y = m.point.y + dy;

      line.i1 = false;

    }

    else {

      // find min x

      while(i.hasMoreElements()) {

	CompoundLine k = (CompoundLine)i.nextElement();

	if(k.point.x < m.point.x) {

	  m = k;

	}

      }

      if(dx < 0) {

	dx = -dx;

	dy = -dy;

      }

      line.p1 = m.point;

      line.p2.x = m.point.x - dx;

      line.p2.y = m.point.y - dy;

      line.i1 = false;

    }

    return m;

  }

  /** find next point */

  private static CompoundLine findNextPoint(Segment line, final List intersects, final Segment s) {

    CompoundLine m;

    Enumeration i = intersects.elements();

    if(!i.hasMoreElements())

      return null;

    do {

      if(!i.hasMoreElements())

	return null;

      m = (CompoundLine)i.nextElement();

    } while((!line.i1 && m.point.equals(line.p1)) ||

	    (!line.i2 && m.point.equals(line.p2)));

    if(s.p1.x < s.p2.x) {

      // find min y

      while(i.hasMoreElements()) {

	CompoundLine k = (CompoundLine)i.nextElement();

	if((!line.i1 && k.point.equals(line.p1)) ||

	   (!line.i2 && k.point.equals(line.p2)))

	  continue;

	if(k.point.y < m.point.y) {

	  m = k;

	}

      }

    }

    else if(s.p1.x > s.p2.x) {

      // find max y

      while(i.hasMoreElements()) {

	CompoundLine k = (CompoundLine)i.nextElement();

	if((!line.i1 && k.point.equals(line.p1)) || 

	   (!line.i2 && k.point.equals(line.p2)))

	  continue;

	if(k.point.y > m.point.y) {

	  m = k;

	}

      }

    }

    else if(s.p1.y > s.p2.y) {

      // find min x

      while(i.hasMoreElements()) {

	CompoundLine k = (CompoundLine)i.nextElement();

	if((!line.i1 && k.point.equals(line.p1)) ||

	   (!line.i2 && k.point.equals(line.p2)))

	  continue;

	if(k.point.x < m.point.x) {

	  m = k;

	}

      }

    }

    else {

      // find max x

      while(i.hasMoreElements()) {

	CompoundLine k = (CompoundLine)i.nextElement();

	if((!line.i1 && k.point.equals(line.p1)) ||

	   (!line.i2 && k.point.equals(line.p2)))

	  continue;

	if(k.point.x > m.point.x) {

	  m = k;

	}

      }

    }

    line.p2 = m.point;

    line.i2 = false;

    return m;

  }

  /** compares two points by x and y */

  private static int compare(final Coord p1, final Coord p2) {

    if(p1.x < p2.x) {

      return 1;

    }

    else if(p1.x > p2.x) {

      return -1;

    }

    else if(p1.y < p2.y) {

      return 1;

    }

    else if(p1.y > p2.y) {

      return -1;

    }

    else {

      return 0;

    }

  }

  /** sorts an array of points (by merge sort) */

  private static void sort(Coord[] points, int start, int end) {

    if(end - start > 1) {

      sort(points, start, (start + end) / 2);

      sort(points, (start + end) / 2, end);

      Coord[] t = new Coord[end - start];

      int i = start;

      int j = (start + end) / 2;

      int k = 0;

      while(i < (start + end) / 2 && j < end) {

	if(compare(points[i], points[j]) > 0) {

	  t[k++] = points[i++];

	}

	else {

	  t[k++] = points[j++];

	}

      }

      while(i < (start + end) / 2) {

	t[k++] = points[i++];

      }

      while(j < end) {

	t[k++] = points[j++];

      }

      for(k = start; k < end; k++) {

	points[k] = t[k - start];

      }

    }

  }

}

package org.gvsig.jts.voronoi.chen;

/**

 * Voronoi diagram

 *

 * Copyright(c) 1998 Ping-Che Chen

 *

 * This program defines the vertices in a voronoi diagram.

 * This is a internal data structure.

 */

public class Vertex extends Coord {

  public List edges = null;

  public int number;

  public int originalOrder;

  public Vertex() {

    edges = new List();

  }

}

package org.gvsig.jts.voronoi.chen;

/**

 * Voronoi diagram

 *

 * Copyright(c) 1998 Ping-Che Chen

 *

 * This program defines the line segment used in the Voronoi

 * diagram problem.

 *

 */

public class VoronoiSegment extends Segment {

  VoronoiSegment(Vertex v1, Vertex v2) {

    this.v1 = v1;

    this.v2 = v2;

    floating = false;

  }

  public final Vertex v1, v2;

  public boolean floating;

}