Toxiclibs Voronoi graph implementation

asmith33

Found this post http://forum.processing.org/one/topic/toxiclib-voronoi-example-sketch.html where toxi writes a graph implementation for someone about a year ago. After running the code he wrote:

/**
 * Demonstration of a simple undirected graph implementation
 * for navigating voronoi regions (or connected points in general).
 *
 * Move mouse to select vertices and see their related edges:
 * 1st degree - magenta
 * 2nd degree - green
 *
 * (c) 2012 Karsten Schmidt // LGPL licensed
 *
 * Requires toxiclibs-0020 or later..
 */
import toxi.geom.*;
import toxi.geom.mesh2d.*;
import toxi.processing.*;

Voronoi voronoi = new Voronoi();
UndirectedGraph graph=new UndirectedGraph();
ToxiclibsSupport gfx;

Vec2D selectedVertex=null;
float snapDist = 5*5;

void setup() {
  size(400,400);
  smooth();
  PolygonClipper2D clip=new SutherlandHodgemanClipper(new Rect(10,10,width-20,height-20));
  for(int i=0; i<25; i++) {
    voronoi.addPoint(new Vec2D(random(width),random(height)));
  }
  for (Polygon2D poly : voronoi.getRegions()) {
      poly=clip.clipPolygon(poly);
      // add all edges of the polygon to the graph (duplicates are ignored automatically)
      for(int i=0,num=poly.vertices.size(); i<num; i++) {
        graph.addEdge(poly.vertices.get(i),poly.vertices.get((i+1)%num));
      }
  }
  gfx=new ToxiclibsSupport(this);
  noLoop();
}

void draw() {
  background(255);
  stroke(0);
  strokeWeight(1);
  for(Edge e : graph.getEdges()) {
    gfx.line(e.a,e.b);
  }
  if (selectedVertex!=null) {
    strokeWeight(3);
    // show related edges for selected vertex
    for(Edge e1 : graph.getEdgesForVertex(selectedVertex)) {
      stroke(255,0,255);
      gfx.line(e1.a,e1.b);
      stroke(0,255,0);
      // now get 2nd degree relationships
      for(Edge e2 : graph.getEdgesForVertex(e1.getOtherEndFor(selectedVertex))) {
        if (e2!=e1) {
          gfx.line(e2.a,e2.b);
        }
      }
    }
    noStroke();
    fill(0,255,255);
    gfx.circle(selectedVertex,8);
  }
}

void mouseMoved() {
  selectedVertex=null;
  Vec2D mousePos=new Vec2D(mouseX,mouseY);
  for(Vec2D v : graph.getVertices()) {
    if (mousePos.distanceToSquared(v) < snapDist) {
      selectedVertex=v;
      break;
    }
  }
  redraw();
}

/**
 * This class implements a undirected vertex graph and provides basic connectivity information.
 * Vertices can only be added by defining edges, ensuring there're no isolated nodes
 * (but allowing for subgraphs/clusters).
 */
public class UndirectedGraph {

  // use vertex position as unique keys and a list of edges as its value
  private final Map<Vec2D, List<Edge>> vertexEdgeIndex = new HashMap<Vec2D, List<Edge>>();

  // set of all edges in the graph
  private final Set<Edge> edges = new HashSet<Edge>();

  // attempts to add new edge for the given vertices
  // if successful also add vertices to index and associate edge with each
  public void addEdge(Vec2D a, Vec2D b) {
    if (!a.equals(b)) {
      Edge e = new Edge(a, b);
      if (edges.add(e)) {
        addEdgeForVertex(a, e);
        addEdgeForVertex(b, e);
      }
    }
  }

  private void addEdgeForVertex(Vec2D a, Edge e) {
    List<Edge> vertEdges = vertexEdgeIndex.get(a);
    if (vertEdges == null) {
      vertEdges = new ArrayList<Edge>();
      vertexEdgeIndex.put(a, vertEdges);
    }
    vertEdges.add(e);
  }

  public Set<Edge> getEdges() {
    return edges;
  }

  // get list of edges for the given vertex (or null if vertex is unknown)
  public List<Edge> getEdgesForVertex(ReadonlyVec2D v) {
    return vertexEdgeIndex.get(v);
  }

  public Set<Vec2D> getVertices() {
    return vertexEdgeIndex.keySet();
  }
}

/**
 * A single immutable, undirected connection between two vertices.
 * Provides equals() & hashCode() implementations to ignore direction.
 */
public class Edge {

  public final ReadonlyVec2D a, b;

  public Edge(ReadonlyVec2D a, ReadonlyVec2D b) {
    this.a = a;
    this.b = b;
  }

  public boolean equals(Object o) {
    if (o != null && o instanceof Edge) {
      Edge e = (Edge) o;
      return
        (a.equals(e.a) && b.equals(e.b)) ||
        (a.equals(e.b) && b.equals(e.a));
    }
    return false;
  }

  public Vec2D getDirectionFrom(ReadonlyVec2D p) {
    Vec2D dir = b.sub(a);
    if (p.equals(b)) {
      dir.invert();
    }
    return dir;
  }

  public ReadonlyVec2D getOtherEndFor(ReadonlyVec2D p) {
    return p.equals(a) ? b : a;
  }

  public int hashCode() {
    return a.hashCode() + b.hashCode();
  }

  public String toString() {
    return a.toString() + " <-> " + b.toString();
  }
}

I get a null point exception error after moving my cursor cursor around for awhile. It doesn't happen right away, it generally takes hovering over 10-20 nodes before it occurs, but it does happen every time, after enough cursor movement. It seems to not like this section:

public ReadonlyVec2D getOtherEndFor(ReadonlyVec2D p) {
    return p.equals(a) ? b : a;
  }

From what he was saying in the post, it sounds like he kind of made this on the fly, but mentioned a demo for a future release.

"Now, to turn this into a proper graph, I've taken this as an opportunity to create a new demo for the next release, pasted below."

I can't find this demo in his library. I was hoping he might have noticed the bug sometime after this forum exchanged happened and updated the code in that demo. Anyone aware of this demo? Or know what might be throwing this flag? One thing I did notice is that the nodes (not including corner cases) don't always have 3 edges. If thats the case, then the error would probably have happened before the quoted section above. Somewhere in the edge creation process I'm guessing. Anyway, I'll dig into it, but there is a lot for me to learn here so it may be awhile. Again, if someone is aware of this demo please let me know.

amnon

Well, it's not in the repository, so I guess a final/fixed example was never added.

You can add some null checks in the code to find and protect against NPE's.