Geometry-Based Edge Clustering
 All Classes Functions
CanvasPanel.java
1 import javax.swing.JPanel;
2 
3 import org.jdelaunay.delaunay.ConstrainedMesh;
4 import org.jdelaunay.delaunay.error.DelaunayError;
5 import org.jdelaunay.delaunay.geometries.DEdge;
6 import org.jdelaunay.delaunay.geometries.DPoint;
7 
8 import java.awt.BasicStroke;
9 import java.awt.Color;
10 import java.awt.Graphics;
11 import java.awt.Graphics2D;
12 import java.awt.event.MouseEvent;
13 import java.awt.event.MouseListener;
14 import java.awt.event.MouseMotionListener;
15 import java.awt.geom.Line2D;
16 import java.awt.geom.Rectangle2D;
17 import java.awt.image.BufferedImage;
18 import java.util.ArrayList;
19 
26 public class CanvasPanel extends JPanel {
27 
28  private boolean bundlingActive;
29  private int mousePosX, mousePosY;
30  private int radius = 5;
31  private ArrayList<Edge> edges;
32  private ArrayList<Edge> meshEdges;
33  private ArrayList<Node> meshNodes;
34  private ArrayList<Node> nodes;
35  private MainWindow window;
36  private Node selectedNode;
37 
41  public CanvasPanel(MainWindow window) {
42  this.window = window;
43  setBackground(Color.WHITE);
44 
45  edges = new ArrayList<Edge>();
46  meshEdges = new ArrayList<Edge>();
47  meshNodes = new ArrayList<Node>();
48  nodes = new ArrayList<Node>();
49  bundlingActive = false;
50  addListeners();
51  }
52 
56  private void addListeners(){
57  addMouseListener(new MouseListener() {
58 
59  @Override
60  public void mouseReleased(MouseEvent e) {
61  // Create or move a Node of the graph.
62  if(window.getMouseMode() == MouseMode.GRAPHNODE){
63  if(selectedNode != null){
64  boolean occupied = false;
65  for(Node node : nodes){
66  if(clickedNode(e, node) && !node.equals(selectedNode)){
67  occupied = true;
68  break;
69  }
70  }
71  if(!occupied)
72  selectedNode.setCoords(mousePosX, mousePosY);
73  selectedNode = null;
74  }
75  else
76  nodes.add(new Node(e.getX(), e.getY()));
77  }
78  // Create an Edge of the graph.
79  if(window.getMouseMode() == MouseMode.GRAPHEDGE){
80  for(Node node : nodes){
81  if(clickedNode(e, node)){
82  if(!node.equals(selectedNode)){
83  edges.add(new Edge(selectedNode, node));
84  break;
85  }
86  }
87  }
88  selectedNode = null;
89  }
90  // Delete a Node or Edge of the graph.
91  if(window.getMouseMode() == MouseMode.GRAPHDELETE){
92  for(Node node : nodes){
93  if(clickedNode(e, node)){
94  nodes.remove(node);
95  ArrayList<Edge> edgesToDelete = new ArrayList<Edge>();
96  for(Edge edge : edges){
97  if(edge.isIncident(node))
98  edgesToDelete.add(edge);
99  }
100  edges.removeAll(edgesToDelete);
101  break;
102  }
103  }
104  if(!bundlingActive){
105  for(Edge edge : edges){
106  if(clickedEdge(e, edge)){
107  edges.remove(edge);
108  break;
109  }
110  }
111  }
112  }
113  // Create or move a Node of the control mesh.
114  if(window.getMouseMode() == MouseMode.MESHNODE){
115  if(selectedNode != null){
116  boolean occupied = false;
117  for(Node node : meshNodes){
118  if(clickedNode(e, node) && !node.equals(selectedNode)){
119  occupied = true;
120  break;
121  }
122  }
123  if(!occupied)
124  selectedNode.setCoords(mousePosX, mousePosY);
125  selectedNode = null;
126  }
127  else
128  meshNodes.add(new Node(e.getX(), e.getY()));
129  }
130  // Create an Edge of the control mesh.
131  if(window.getMouseMode() == MouseMode.MESHEDGE){
132  for(Node node : meshNodes){
133  if(clickedNode(e, node)){
134  if(!node.equals(selectedNode)){
135  meshEdges.add(new Edge(selectedNode, node));
136  break;
137  }
138  }
139  }
140  selectedNode = null;
141  }
142  // Delete a Node or Edge of the control mesh.
143  if(window.getMouseMode() == MouseMode.MESHDELETE){
144  for(Node node : meshNodes){
145  if(clickedNode(e, node)){
146  meshNodes.remove(node);
147  ArrayList<Edge> edgesToDelete = new ArrayList<Edge>();
148  for(Edge edge : meshEdges){
149  if(edge.isIncident(node))
150  edgesToDelete.add(edge);
151  }
152  meshEdges.removeAll(edgesToDelete);
153  break;
154  }
155  }
156  for(Edge edge : meshEdges){
157  if(clickedEdge(e, edge)){
158  meshEdges.remove(edge);
159  break;
160  }
161  }
162  }
163  if(bundlingActive)
164  bundleEdges();
165  paintComponent(getGraphics());
166  }
167 
168  @Override
169  public void mousePressed(MouseEvent e) {
170  // Let the user create an Edge of the graph.
171  if(window.getMouseMode() == MouseMode.GRAPHEDGE){
172  for(Node node : nodes){
173  if(clickedNode(e, node)){
174  selectedNode = node;
175  break;
176  }
177  }
178  }
179  // Let the user move a Node of the graph.
180  if(window.getMouseMode() == MouseMode.GRAPHNODE){
181  for(Node node : nodes){
182  if(clickedNode(e, node)){
183  selectedNode = node;
184  break;
185  }
186  }
187  }
188  // Let the user create an Edge of the control mesh.
189  if(window.getMouseMode() == MouseMode.MESHEDGE){
190  for(Node node : meshNodes){
191  if(clickedNode(e, node)){
192  selectedNode = node;
193  break;
194  }
195  }
196  }
197  // Let the user move a Node of the control mesh.
198  if(window.getMouseMode() == MouseMode.MESHNODE){
199  for(Node node : meshNodes){
200  if(clickedNode(e, node)){
201  selectedNode = node;
202  break;
203  }
204  }
205  }
206  }
207 
208  @Override
209  public void mouseExited(MouseEvent e) {
210  }
211 
212  @Override
213  public void mouseEntered(MouseEvent e) {
214  }
215 
216  @Override
217  public void mouseClicked(MouseEvent e) {
218  }
219  });
220 
221  addMouseMotionListener(new MouseMotionListener() {
222 
223  @Override
224  public void mouseMoved(MouseEvent e) {
225  }
226 
227  @Override
228  // Draw the Edge or Node that the user is holding.
229  public void mouseDragged(MouseEvent e) {
230  if(selectedNode != null){
231  mousePosX = e.getX();
232  mousePosY = e.getY();
233  paintComponent(getGraphics());
234  }
235  }
236  });
237  }
238 
239  @Override
240  public void paintComponent(Graphics g){
241  super.paintComponent(g);
242  BufferedImage bimg = new BufferedImage(getSize().width, getSize().width,
243  BufferedImage.TYPE_INT_ARGB);
244  Graphics2D g2d = bimg.createGraphics();
245 
246  // Draw the Edges of the graph.
247  g2d.setColor(new Color(0, 0, 0, 0.10f));
248  g2d.setStroke(new BasicStroke(3));
249  for(Edge edge : edges){
250  if(bundlingActive){
251  ArrayList<Node> pathNodes = new ArrayList<Node>();
252  ArrayList<Node> remainingNodes = new ArrayList<Node>(edge.getSubNodes());
253  remainingNodes.add(edge.getEndNode());
254  Node currentNode = edge.getStartNode();
255  while(currentNode != edge.getEndNode()){
256  pathNodes.add(currentNode);
257  Node minNode = null;
258  double minDist = Double.POSITIVE_INFINITY;
259  for(Node node : remainingNodes){
260  if(currentNode.distance(node) < minDist){
261  minDist = currentNode.distance(node);
262  minNode = node;
263  }
264  }
265  if(minNode != null){
266  remainingNodes.remove(minNode);
267  currentNode = minNode;
268  }
269  else
270  break;
271  }
272  pathNodes.add(currentNode);
273  int[] subNodesX = new int[pathNodes.size()];
274  int[] subNodesY = new int[pathNodes.size()];
275  for(int i=0; i<pathNodes.size(); i++){
276  subNodesX[i] = pathNodes.get(i).getXInt();
277  subNodesY[i] = pathNodes.get(i).getYInt();
278  }
279  g2d.drawPolyline(subNodesX, subNodesY, pathNodes.size());
280  }
281  else
282  g2d.drawLine(edge.getStartNode().getXInt(), edge.getStartNode().getYInt(),
283  edge.getEndNode().getXInt(), edge.getEndNode().getYInt());
284  }
285  // Color the Edges of the graph.
286  int[] pixels = bimg.getRGB(0, 0, getSize().width, getSize().height, null, 0, getSize().width);
287  for(int p=0; p < getSize().width*getSize().height; p++){
288  int alpha = pixels[p]>>24 & 255;
289  if(alpha > 0)
290  pixels[p] = alpha<<24 | alpha<<16 | (255-alpha);
291  }
292  bimg.setRGB(0, 0, getSize().width, getSize().height, pixels, 0, getSize().width);
293 
294  // Draw the Nodes of the graph.
295  g2d.setColor(Color.BLACK);
296  for(Node node : nodes){
297  if(node.equals(selectedNode)){
298  if(window.getMouseMode() == MouseMode.GRAPHNODE)
299  g2d.fillOval(mousePosX-radius, mousePosY-radius, radius*2, radius*2);
300  else{
301  g2d.fillOval(node.getXInt()-radius, node.getYInt()-radius, radius*2, radius*2);
302  g2d.drawLine(node.getXInt(), node.getYInt(), mousePosX, mousePosY);
303  }
304  }
305  else
306  g2d.fillOval(node.getXInt()-radius, node.getYInt()-radius, radius*2, radius*2);
307  }
308 
309  // Draw the Nodes and Edges of the control mesh.
310  if(window.isMeshSelected()){
311  g2d.setColor(Color.GREEN);
312  for(Edge edge : meshEdges){
313  g2d.drawLine(edge.getStartNode().getXInt(), edge.getStartNode().getYInt(),
314  edge.getEndNode().getXInt(), edge.getEndNode().getYInt());
315  }
316  for(Node node : meshNodes){
317  if(node.equals(selectedNode)){
318  if(window.getMouseMode() == MouseMode.MESHNODE)
319  g2d.fillOval(mousePosX-radius, mousePosY-radius, radius*2, radius*2);
320  else{
321  g2d.fillOval(node.getXInt()-radius, node.getYInt()-radius, radius*2, radius*2);
322  g2d.drawLine(node.getXInt(), node.getYInt(), mousePosX, mousePosY);
323  }
324  }
325  else
326  g2d.fillOval(node.getXInt()-radius, node.getYInt()-radius, radius*2, radius*2);
327  }
328  }
329  this.getGraphics().drawImage(bimg, 0, 0, null);
330  }
331 
337  public void addEdge(int startNodeIndex, int endNodeIndex){
338  edges.add(new Edge(nodes.get(startNodeIndex), nodes.get(endNodeIndex)));
339  }
340 
346  public void addNode(int x, int y){
347  nodes.add(new Node(x, y));
348  }
349 
354  public ArrayList<Edge> getEdges(){
355  return edges;
356  }
357 
362  public ArrayList<Node> getNodes(){
363  return nodes;
364  }
365 
369  public void bundleEdges(){
370  for(Edge edge : edges)
371  edge.deleteSubNodes();
372 
373  // Intersect the graph and the control mesh and calculate control points.
374  for(Edge m : meshEdges){
375  ArrayList<Node> sNodes = new ArrayList<Node>();
376  ArrayList<Edge> sEdges = new ArrayList<Edge>();
377  double sumX = 0;
378  double sumY = 0;
379  for(Edge e : edges){
380  Node s = m.intersection(e);
381  if(s != null){
382  sNodes.add(s);
383  sEdges.add(e);
384  }
385  }
386  if(sNodes.size() > 0){
387  for(Node n : sNodes){
388  sumX += n.getX();
389  sumY += n.getY();
390  }
391  Node control = new Node(sumX/sNodes.size(), sumY/sNodes.size());
392  for(Edge e : sEdges)
393  e.addSubNode(control);
394  }
395  }
396 
397  bundlingActive = true;
398  paintComponent(getGraphics());
399  }
400 
404  public void clearAll(){
405  nodes.clear();
406  edges.clear();
407  meshNodes.clear();
408  meshEdges.clear();
409  paintComponent(getGraphics());
410  }
411 
415  public void clearMesh(){
416  meshNodes.clear();
417  meshEdges.clear();
418  paintComponent(getGraphics());
419  }
420 
424  public void connectAll(){
425  edges.clear();
426  for(int i=0; i<nodes.size(); i++)
427  for(int j=i+1; j<nodes.size(); j++)
428  edges.add(new Edge(nodes.get(i), nodes.get(j)));
429  paintComponent(getGraphics());
430  }
431 
437  public void createMesh(int dx, int dy){
438  int width = getSize().width/dx + 1;
439  int height = getSize().height/dy + 1;
440 
441  // Create constraints if the user didn't draw them.
442  if(meshEdges.size() == 0){
443  // Create the regular grid.
444  GridCell[][] cellArray = new GridCell[width][height];
445  for(int x=0; x<width; x++)
446  for(int y=0; y<height; y++)
447  cellArray[x][y] = createCell(x, y, dx, dy);
448 
449  // Merge the cells to form regions and create constraints.
450  ArrayList<GridRegion> regions = createRegions(width, height, cellArray);
451  meshEdges = createConstraints(regions);
452  }
453 
454  // Perform Constrained Delaunay Triangulation.
455  ConstrainedMesh mesh = new ConstrainedMesh();
456  for(Edge e : meshEdges){
457  try {
458  mesh.addConstraintEdge(e.toDEdge());
459  } catch (DelaunayError e1) {
460  System.out.println("Could not add constraint.");
461  }
462  }
463  try {
464  mesh.processDelaunay();
465  meshEdges.clear();
466  meshNodes.clear();
467  ArrayList<DPoint> meshPoints = new ArrayList<DPoint>();
468  for(DPoint p : mesh.getPoints()){
469  meshPoints.add(p);
470  meshNodes.add(new Node(p));
471  }
472  for(DEdge e : mesh.getEdges()){
473  Node startNode = meshNodes.get(meshPoints.indexOf(e.getStartPoint()));
474  Node endNode = meshNodes.get(meshPoints.indexOf(e.getEndPoint()));
475  meshEdges.add(new Edge(startNode, endNode));
476  }
477  } catch (DelaunayError e1) {
478  System.out.println("Could not process Delaunay. Using original constraints instead.");
479  }
480  }
481 
485  public void unbundleEdges(){
486  bundlingActive = false;
487  for(Edge edge: edges)
488  edge.deleteSubNodes();
489  paintComponent(getGraphics());
490  }
491 
498  private boolean clickedEdge(MouseEvent e, Edge edge){
499  return (Line2D.ptSegDist(edge.getStartNode().getX(), edge.getStartNode().getY(),
500  edge.getEndNode().getX(), edge.getEndNode().getY(), e.getX(), e.getY()) < 2.0);
501  }
502 
509  private boolean clickedNode(MouseEvent e, Node node){
510  return (e.getX() >= node.getX()-radius && e.getX() <= node.getX()+radius &&
511  e.getY() >= node.getY()-radius && e.getY() <= node.getY()+radius);
512  }
513 
519  private double gaussProb(double x){
520  return Math.exp(-Math.pow(x, 2)/2)/Math.sqrt(2*Math.PI);
521  }
522 
528  private ArrayList<Double> kde(ArrayList<Double> angles){
529  ArrayList<Double> density = new ArrayList<Double>();
530  double h = 1.06*Math.pow(angles.size(), -1/5);
531  for(int j=0; j<1800; j++){
532  double x = (double)j/10;
533  double sum = 0;
534  for(int i=0; i<angles.size(); i++){
535  double difference = x-angles.get(i);
536  if(difference > 90)
537  difference = 180 - difference;
538  else if(difference < -90)
539  difference = -180 - difference;
540  sum += gaussProb(difference/h);
541  }
542  density.add(sum/(h*angles.size()));
543  }
544  return density;
545  }
546 
553  private ArrayList<Edge> createConstraints(ArrayList<GridRegion> regions){
554  ArrayList<Edge> constraints = new ArrayList<Edge>();
555  for(GridRegion r : regions){
556  double normalAngle = r.getPrimaryAngle() + 90;
557  if(normalAngle >= 180)
558  normalAngle -= 180;
559  Edge normal = new Edge(r.center(), normalAngle);
560  double nodeX = r.center().getX();
561  double nodeY = r.center().getY();
562  while(r.contains(new Node(nodeX, nodeY))){
563  nodeX += normal.dx();
564  nodeY += normal.dy();
565  }
566  Node nStart = new Node(nodeX, nodeY);
567  nodeX = r.center().getX();
568  nodeY = r.center().getY();
569  while(r.contains(new Node(nodeX, nodeY))){
570  nodeX -= normal.dx();
571  nodeY -= normal.dy();
572  }
573  Node nEnd = new Node(nodeX, nodeY);
574  constraints.add(new Edge(nStart, nEnd));
575  }
576  return constraints;
577  }
578 
586  private ArrayList<GridRegion> createRegions(int width, int height, GridCell[][] cellArray){
587  ArrayList<GridRegion> regions = new ArrayList<GridRegion>();
588  for(int x=0; x<width; x++){
589  for(int y=0; y<height; y++){
590  if(cellArray[x][y].getPrimaryAngle() > -1){
591  double minDiff = Double.POSITIVE_INFINITY;
592  int minDiffRegion = -1;
593  if(x > 0){
594  int regionIndex = cellArray[x-1][y].getRegionIndex();
595  if(regionIndex >= 0){
596  double diff = cellArray[x][y].getPrimaryAngle()
597  - regions.get(regionIndex).getPrimaryAngle();
598  if(Math.abs(diff) > 90)
599  diff = 180-Math.abs(diff);
600  else
601  diff = Math.abs(diff);
602  if(diff < minDiff){
603  minDiff = diff;
604  minDiffRegion = regionIndex;
605  }
606  }
607  }
608  if(y > 0){
609  int regionIndex = cellArray[x][y-1].getRegionIndex();
610  if(regionIndex >= 0){
611  double diff = cellArray[x][y].getPrimaryAngle()
612  - regions.get(regionIndex).getPrimaryAngle();
613  if(Math.abs(diff) > 90)
614  diff = 180-Math.abs(diff);
615  else
616  diff = Math.abs(diff);
617  if(diff < minDiff){
618  minDiff = diff;
619  minDiffRegion = regionIndex;
620  }
621  }
622  }
623  if(minDiff <= 10 && minDiffRegion >= 0){
624  cellArray[x][y].setRegionIndex(minDiffRegion);
625  regions.get(minDiffRegion).addCell(cellArray[x][y]);
626  }
627  else{
628  cellArray[x][y].setRegionIndex(regions.size());
629  GridRegion region = new GridRegion(cellArray[x][y].getPrimaryAngle());
630  region.addCell(cellArray[x][y]);
631  regions.add(region);
632  }
633  }
634  }
635  }
636  return regions;
637  }
638 
647  private GridCell createCell(int x, int y, int dx, int dy){
648  // Get the angles to the x-axis of all Edges intersecting the cell.
649  GridCell cell = new GridCell(dx*x, dy*y, dx, dy);
650  Rectangle2D bounds = cell.bounds();
651  ArrayList<Double> angles = new ArrayList<Double>();
652  for(Edge e : edges){
653  if(bounds.intersectsLine(e.getStartNode().getX(), e.getStartNode().getY(),
654  e.getEndNode().getX(), e.getEndNode().getY()))
655  angles.add(e.angleXAxis());
656  }
657  if(angles.size() == 0)
658  return cell;
659 
660  // Calculate the dominant direction of the intersecting Edges.
661  ArrayList<Double> density = kde(angles);
662  int maxIndex = -1;
663  double maxDensity = 0;
664  for(int d=0; d<1800; d++){
665  if(density.get(d) > maxDensity){
666  maxDensity = density.get(d);
667  maxIndex = d;
668  }
669  }
670  if(maxIndex == -1)
671  return cell;
672  double densitySum = 0;
673  for(int d=maxIndex-100; d<maxIndex+100; d++){
674  int i = d;
675  if(i < 0)
676  i = 1800+i;
677  else if(i >= 1800)
678  i = i-1800;
679  densitySum += density.get(i);
680  }
681  if(densitySum > 5)
682  cell.setPrimaryAngle((double)maxIndex/10);
683 
684  return cell;
685  }
686 }