boolean findNext ( int firstIdx , EdgeSet splitterSet , EdgeSet candidateSet , double parallel , SearchResults results ) { Edge e0 = candidateSet . get ( firstIdx ) ; results . index = - 1 ; results . error = Double . MAX_VALUE ; boolean checkParallel = ! Double . isNaN ( parallel ) ; for ( int i = 0 ; i < candidateSet . size ( ) ; i ++ ) { if ( i == firstIdx ) continue ; // stop considering edges when they are more than 180 degrees away Edge eI = candidateSet . get ( i ) ; double distanceCCW = UtilAngle . distanceCCW ( e0 . direction , eI . direction ) ; if ( distanceCCW >= Math . PI * 0.9 ) // Multiplying by 0.9 helped remove a lot of bad matches continue ; // It was pairing up opposite corners under heavy perspective distortion // It should be parallel to a previously found line if ( checkParallel ) { double a = UtilAngle . boundHalf ( eI . direction ) ; double b = UtilAngle . boundHalf ( parallel ) ; double distanceParallel = UtilAngle . distHalf ( a , b ) ; if ( distanceParallel > parallelTol ) { continue ; } } // find the perpendicular corner which splits these two edges and also find the index of // the perpendicular sets which points towards the splitter. if ( ! findSplitter ( e0 . direction , eI . direction , splitterSet , e0 . dst . perpendicular , eI . dst . perpendicular , tuple3 ) ) continue ; double acute0 = UtilAngle . dist ( candidateSet . get ( firstIdx ) . direction , e0 . dst . perpendicular . get ( tuple3 . b ) . direction ) ; double error0 = UtilAngle . dist ( acute0 , Math . PI / 2.0 ) ; if ( error0 > Math . PI * 0.3 ) continue ; double acute1 = UtilAngle . dist ( candidateSet . get ( i ) . direction , eI . dst . perpendicular . get ( tuple3 . c ) . direction ) ; double error1 = UtilAngle . dist ( acute1 , Math . PI / 2.0 ) ; if ( error1 > Math . PI * 0.3 ) continue ; // Find the edge from corner 0 to corner i. The direction of this vector and the corner's // orientation has a known relationship described by 'phaseOri' int e0_to_eI = e0 . dst . parallel . find ( eI . dst ) ; if ( e0_to_eI < 0 ) continue ; // The quadrilateral with the smallest area is most often the best solution. Area is more expensive // so the perimeter is computed instead. one side is left off since all of them have that side double error = e0 . dst . perpendicular . get ( tuple3 . b ) . distance ; error += eI . dst . perpendicular . get ( tuple3 . c ) . distance ; error += eI . distance ; if ( error < results . error ) { results . error = error ; results . index = i ; } } return results . index != - 1 ; }
Greedily select the next edge that will belong to the final graph .