private void repairVertexes ( ) { // System.out.println("######## Repair"); for ( int idxV = 0 ; idxV < dirtyVertexes . size ( ) ; idxV ++ ) { final Vertex v = dirtyVertexes . get ( idxV ) ; // System.out.println(" dirty="+v.index); bestSolution . clear ( ) ; for ( int idxE = 0 ; idxE < v . perpendicular . size ( ) ; idxE ++ ) { // Assume this edge is in the solutions Edge e = v . perpendicular . get ( idxE ) ; // only can connect new modified vertexes or ones already connected too if ( ! ( e . dst . marked || - 1 != v . connections . find ( e . dst ) ) ) { continue ; } // System.out.println(" e[0].dst = "+e.dst.index); solution . clear ( ) ; solution . add ( e ) ; // search for connections until there's no more to be found for ( int count = 0 ; count < 3 ; count ++ ) { // Find the an edge which is about to 90 degrees CCW of the previous edge 'v' Vertex va = null ; double dir90 = UtilAngle . bound ( e . direction + Math . PI / 2.0 ) ; for ( int i = 0 ; i < e . dst . connections . size ( ) ; i ++ ) { Edge ei = e . dst . connections . get ( i ) ; if ( UtilAngle . dist ( ei . direction , dir90 ) < Math . PI / 3 ) { va = ei . dst ; break ; } } // Search for an edge in v which has a connection to 'va' and is ccw of 'e' boolean matched = false ; for ( int i = 0 ; i < v . perpendicular . size ( ) ; i ++ ) { Edge ei = v . perpendicular . get ( i ) ; if ( e == ei ) continue ; // angle test double ccw = UtilAngle . distanceCCW ( e . direction , ei . direction ) ; if ( ccw > Math . PI * 0.9 ) continue ; if ( ! ( ei . dst . marked || - 1 != v . connections . find ( ei . dst ) ) ) { continue ; } // connection test if ( ei . dst . connections . find ( va ) != - 1 ) { // System.out.println(" e[i].dst = "+ei.dst.index+" va="+va.index); e = ei ; solution . add ( ei ) ; matched = true ; break ; } } if ( ! matched ) break ; } if ( solution . size ( ) > bestSolution . size ( ) ) { bestSolution . clear ( ) ; bestSolution . addAll ( solution ) ; } } if ( bestSolution . size ( ) > 1 ) { // See if any connection that was there before is now gone. If that's the case the destination // will need to be checked for mutual matches for ( int i = 0 ; i < v . connections . edges . size ( ) ; i ++ ) { if ( ! bestSolution . contains ( v . connections . edges . get ( i ) ) ) { v . connections . edges . get ( i ) . dst . marked = true ; break ; } } // Save the new connections v . connections . edges . clear ( ) ; v . connections . edges . addAll ( bestSolution ) ; } } }
Given the current graph attempt to replace edges from vertexes which lost them in an apparent bad decision . This is a very simple algorithm and gives up if the graph around the current node is less than perfect .