import { IPoint , IBBox , Item , BubblesetCfg } from '../../types' ; import { squareDist , pointLineSquareDist , itemIntersectByLine , getPointsCenter , fractionToLine , isPointsOverlap , pointRectSquareDist , Line , isPointInPolygon , } from '../../util/math' ; const defaultOps = { maxRoutingIterations : 100 , maxMarchingIterations : 100 , pixelGroupSize : 2 , edgeR0 : 10 , edgeR1 : 10 , nodeR0 : 5 , nodeR1 : 10 , morphBuffer : 5 , threshold : 0.001 , skip : 16 , nodeInfluenceFactor : 1 , edgeInfluenceFactor : 1 , negativeNodeInfluenceFactor : - 0.5 , } ; param potentialArea param threshold function MarchingSquares ( contour , potentialArea , threshold ) { let marched = false ; const getVal = ( x , y ) => { return potentialArea . cells [ x + y * potentialArea . width ] ; } ; const getState = ( x , y ) => { let squareVal = 0 ; if ( getVal ( x - 1 , y - 1 ) >= threshold ) { squareVal += 1 ; } if ( getVal ( x , y - 1 ) > threshold ) { squareVal += 2 ; } if ( getVal ( x - 1 , y ) > threshold ) { squareVal += 4 ; } if ( getVal ( x , y ) > threshold ) { squareVal += 8 ; } return squareVal ; } ; const doMarch = ( xPos , yPos ) => { let x = xPos ; let y = yPos ; let prevX ; let prevY ; for ( let i = 0 ; i < potentialArea . width * potentialArea . height ; i ++ ) { prevX = x ; prevY = y ; if ( contour . findIndex ( ( item ) => item . x === x && item . y === y ) > - 1 ) { if ( contour [ 0 ] . x !== x || contour [ 0 ] . y !== y ) { } else { return true ; } } else { contour . push ( { x , y } ) ; } const state = getState ( x , y ) ; switch ( state ) { case - 1 : console . warn ( 'Marched out of bounds' ) ; return true ; case 0 : case 3 : case 2 : case 7 : x ++ ; break ; case 12 : case 14 : case 4 : x -- ; break ; case 6 : if ( prevX === 0 ) { if ( prevY === - 1 ) { x -= 1 ; } else { x += 1 ; } } break ; case 1 : case 13 : case 5 : y -- ; break ; case 9 : if ( prevX === 1 ) { if ( prevY === 0 ) { y -= 1 ; } else { y += 1 ; } } break ; case 10 : case 8 : case 11 : y ++ ; break ; default : console . warn ( `Marching squares invalid state: ${ state }` ) ; return true ; } } } ; this . march = ( ) => { for ( let x = 0 ; x < potentialArea . width && ! marched ; x += 1 ) { for ( let y = 0 ; y < potentialArea . height && ! marched ; y += 1 ) { if ( getVal ( x , y ) > threshold && getState ( x , y ) !== 15 ) { marched = doMarch ( x , y ) ; } } } return marched ; } ; } param points const initGridCells = ( width , height , pixelGroupSize ) => { const scaleWidth = Math . ceil ( width / pixelGroupSize ) ; const scaleHeight = Math . ceil ( height / pixelGroupSize ) ; const gridCells = new Float32Array ( Math . max ( 0 , scaleWidth * scaleHeight ) ) . fill ( 0 ) ; return { cells : gridCells , width : scaleWidth , height : scaleHeight , } ; } ; param item param visited const pickBestNeighbor = ( item , visited , nonMembers ) : Item | null => { let closestNeighbour = null ; let minCost = Number . POSITIVE_INFINITY ; visited . forEach ( ( neighbourItem ) => { const itemP = { x : item . getModel ( ) . x , y : item . getModel ( ) . y } ; const neighbourItemP = { x : neighbourItem . getModel ( ) . x , y : neighbourItem . getModel ( ) . y } ; const dist = squareDist ( itemP , neighbourItemP ) ; const directLine = new Line ( itemP . x , itemP . y , neighbourItemP . x , neighbourItemP . y ) ; const numberObstacles = nonMembers . reduce ( ( count , _item ) => { if ( fractionToLine ( _item , directLine ) > 0 ) { return count + 1 ; } return count ; } , 0 ) ; if ( dist * ( numberObstacles + 1 ) ** 2 < minCost ) { closestNeighbour = neighbourItem ; minCost = dist * ( numberObstacles + 1 ) ** 2 ; } } ) ; return closestNeighbour ; } ; param items param line const getIntersectItem = ( items , line ) : Item | null => { let minDistance = Number . POSITIVE_INFINITY ; let closestItem = null ; items . forEach ( ( item ) => { const distance = fractionToLine ( item , line ) ; if ( distance >= 0 && distance < minDistance ) { closestItem = item ; minDistance = distance ; } } ) ; return closestItem ; } ; /**
 * Modify the directLine and Route virtual edges around obstacles
 */ const computeRoute = ( directLine , nonMembers , maxRoutingIterations , morphBuffer ) : Line [ ] => { const checkedLines = [ ] ; const linesToCheck = [ ] ; linesToCheck . push ( directLine ) ; let hasIntersection = true ; let iterations = 0 ; const pointExists = ( point , lines ) => { let flag = false ; lines . forEach ( ( line ) => { if ( flag ) return ; if ( isPointsOverlap ( point , { x : line . x1 , y : line . y1 } ) || isPointsOverlap ( point , { x : line . x2 , y : line . y2 } ) ) { flag = true ; } } ) ; return flag ; } ; const isPointInNonMembers = ( point , _nonMembers ) => { for ( const item of _nonMembers ) { const bbox = item . getBBox ( ) ; const itemContour = [ [ bbox . x , bbox . y ] , [ bbox . x + bbox . width , bbox . y ] , [ bbox . x , bbox . y + bbox . height ] , [ bbox . x + bbox . width , bbox . y + bbox . height ] , ] ; if ( isPointInPolygon ( itemContour , point . x , point . y ) ) { return true ; } } return false ; } ; while ( hasIntersection && iterations < maxRoutingIterations ) { hasIntersection = false ; while ( ! hasIntersection && linesToCheck . length ) { const line = linesToCheck . pop ( ) ; const closestItem = getIntersectItem ( nonMembers , line ) ; if ( closestItem ) { const [ intersections , countIntersections ] = itemIntersectByLine ( closestItem , line ) ; if ( countIntersections === 2 ) { const testReroute = ( isFirst ) => { let tempMorphBuffer = morphBuffer ; let virtualNode = rerouteLine ( closestItem , tempMorphBuffer , intersections , isFirst ) ; let exist = pointExists ( virtualNode , linesToCheck ) || pointExists ( virtualNode , checkedLines ) ; let pointInside = isPointInNonMembers ( virtualNode , nonMembers ) ; while ( ! exist && pointInside && tempMorphBuffer >= 1 ) { tempMorphBuffer /= 1.5 ; virtualNode = rerouteLine ( closestItem , tempMorphBuffer , intersections , isFirst ) ; exist = pointExists ( virtualNode , linesToCheck ) || pointExists ( virtualNode , checkedLines ) ; pointInside = isPointInNonMembers ( virtualNode , nonMembers ) ; } if ( virtualNode && ! exist && ( ! isFirst || ! pointInside ) ) { linesToCheck . push ( new Line ( line . x1 , line . y1 , virtualNode . x , virtualNode . y ) ) ; linesToCheck . push ( new Line ( virtualNode . x , virtualNode . y , line . x2 , line . y2 ) ) ; hasIntersection = true ; } } ; testReroute ( true ) ; if ( ! hasIntersection ) { testReroute ( false ) ; } } } if ( ! hasIntersection ) { checkedLines . push ( line ) ; } iterations += 1 ; } } while ( linesToCheck . length ) { checkedLines . push ( linesToCheck . pop ( ) ) ; } return checkedLines ; } ; /**
 *  Connect item with visited members using direct line or virtual edges
 */ function getRoute ( item , nonMembers , visited , maxRoutingIterations , morphBuffer ) { const optimalNeighbor = pickBestNeighbor ( item , visited , nonMembers ) ; if ( optimalNeighbor === null ) { return [ ] ; } const mergeLines = ( checkedLines ) : Line [ ] => { const finalRoute = [ ] ; while ( checkedLines . length > 0 ) { const line1 = checkedLines . pop ( ) ! ; if ( checkedLines . length === 0 ) { finalRoute . push ( line1 ) ; break ; } const line2 = checkedLines . pop ( ) ! ; const mergeLine = new Line ( line1 . x1 , line1 . y1 , line2 . x2 , line2 . y2 ) ; const closestItem = getIntersectItem ( nonMembers , mergeLine ) ; if ( ! closestItem ) { checkedLines . push ( mergeLine ) ; } else { finalRoute . push ( line1 ) ; checkedLines . push ( line2 ) ; } } return finalRoute ; } ; const directLine = new Line ( item . getModel ( ) . x , item . getModel ( ) . y , optimalNeighbor . getModel ( ) . x , optimalNeighbor . getModel ( ) . y ) ; const checkedLines = computeRoute ( directLine , nonMembers , maxRoutingIterations , morphBuffer ) ; const finalRoute = mergeLines ( checkedLines ) ; return finalRoute ; } param graph param members param nonMembers param options export const genBubbleSet = ( members , nonMembers , ops ? ) => { const options = Object . assign ( defaultOps , ops ) ; const centroid = getPointsCenter ( members . map ( ( item ) => ( { x : item . getModel ( ) . x , y : item . getModel ( ) . y } ) ) ) ; members = members . sort ( ( a , b ) => squareDist ( { x : a . getModel ( ) . x , y : a . getModel ( ) . y } , centroid ) - squareDist ( { x : b . getModel ( ) . x , y : b . getModel ( ) . y } , centroid ) ) ; const visited = [ ] ; const virtualEdges = [ ] ; members . forEach ( ( item ) => { const lines = getRoute ( item , nonMembers , visited , options . maxRoutingIterations , options . morphBuffer ) ; lines . forEach ( ( l ) => { virtualEdges . push ( l ) ; } ) ; visited . push ( item ) ; } ) ; const activeRegion = getActiveRregion ( members , virtualEdges , options . nodeR0 ) ; const potentialArea = initGridCells ( activeRegion . width , activeRegion . height , options . pixelGroupSize ) ; let contour = [ ] ; let hull = [ ] ; for ( let iterations = 0 ; iterations < options . maxMarchingIterations ; iterations ++ ) { fillPotentialArea ( members , nonMembers , virtualEdges , activeRegion , potentialArea , options ) ; contour = [ ] ; hull = [ ] ; if ( ! new MarchingSquares ( contour , potentialArea , options . threshold ) . march ( ) ) continue ; const marchedPath = contour . map ( ( point ) => ( { x : Math . round ( point . x * options . pixelGroupSize + activeRegion . minX ) , y : Math . round ( point . y * options . pixelGroupSize + activeRegion . minY ) , } ) ) ; if ( marchedPath ) { let size = marchedPath . length ; if ( options . skip > 1 ) { size = Math . floor ( marchedPath . length / options . skip ) ; while ( size < 3 && options . skip > 1 ) { options . skip -= 1 ; size = Math . floor ( marchedPath . length / options . skip ) ; } } for ( let i = 0 , j = 0 ; j < size ; j += 1 , i += options . skip ) { hull . push ( { x : marchedPath [ i ] . x , y : marchedPath [ i ] . y } ) ; } } const isContourValid = ( ) => { for ( const item of members ) { const hullPoints = hull . map ( ( point ) => [ point . x , point . y ] ) ; if ( ! isPointInPolygon ( hullPoints , item . getBBox ( ) . centerX , item . getBBox ( ) . centerY ) ) return false ; } return true ; } ; if ( hull && isContourValid ( ) ) { return hull ; } options . threshold *= 0.9 ; if ( iterations <= options . maxMarchingIterations * 0.5 ) { options . memberInfluenceFactor *= 1.2 ; options . edgeInfluenceFactor *= 1.2 ; } else if ( options . nonMemberInfluenceFactor !== 0 && nonMembers . length > 0 ) { options . nonMemberInfluenceFactor *= 0.8 ; } else { break ; } } return hull ; } ; param members param edges function getActiveRregion ( members , edges , offset ) { const activeRegion = { minX : Number . POSITIVE_INFINITY , minY : Number . POSITIVE_INFINITY , maxX : Number . NEGATIVE_INFINITY , maxY : Number . NEGATIVE_INFINITY , width : 0 , height : 0 , x : 0 , y : 0 , } ; const bboxes = [ ] ; members . forEach ( ( item ) => { bboxes . push ( item . getBBox ( ) ) ; } ) ; edges . forEach ( ( l ) => { bboxes . push ( l . getBBox ( ) ) ; } ) ; for ( const bbox of bboxes ) { activeRegion . minX = ( bbox . minX < activeRegion . minX ? bbox . minX : activeRegion . minX ) - offset ; activeRegion . minY = ( bbox . minY < activeRegion . minY ? bbox . minY : activeRegion . minY ) - offset ; activeRegion . maxX = ( bbox . maxX > activeRegion . maxX ? bbox . maxX : activeRegion . maxX ) + offset ; activeRegion . maxY = ( bbox . maxY > activeRegion . maxY ? bbox . maxY : activeRegion . maxY ) + offset ; } activeRegion . width = activeRegion . maxX - activeRegion . minX ; activeRegion . height = activeRegion . maxY - activeRegion . minY ; activeRegion . x = activeRegion . minX ; activeRegion . y = activeRegion . minY ; return activeRegion ; } function fillPotentialArea ( members , nonMembers , edges , activeRegion , potentialArea , options ) { function pos2GridIx ( x , offset ) { const gridIx = Math . floor ( ( x - offset ) / options . pixelGroupSize ) ; return gridIx < 0 ? 0 : gridIx ; } function gridIx2Pos ( x , offset ) { return x * options . pixelGroupSize + offset ; } const nodeInfA = ( options . nodeR0 - options . nodeR1 ) * ( options . nodeR0 - options . nodeR1 ) ; const edgeInfA = ( options . edgeR0 - options . edgeR1 ) * ( options . edgeR0 - options . edgeR1 ) ; const getAffectedRegion = ( bbox , thresholdR ) => { const startX = Math . min ( pos2GridIx ( bbox . minX , thresholdR + activeRegion . minX ) , potentialArea . width ) ; const startY = Math . min ( pos2GridIx ( bbox . minY , thresholdR + activeRegion . minY ) , potentialArea . height ) ; const endX = Math . min ( pos2GridIx ( bbox . maxX , - thresholdR + activeRegion . minX ) , potentialArea . width ) ; const endY = Math . min ( pos2GridIx ( bbox . maxY , - thresholdR + activeRegion . minY ) , potentialArea . height ) ; return [ startX , startY , endX , endY ] ; } ; const addItemInfluence = ( item , influenceFactor ) => { const bbox = item . getBBox ( ) ; const [ startX , startY , endX , endY ] = getAffectedRegion ( bbox , options . nodeR1 ) ; for ( let y = startY ; y < endY ; y += 1 ) { for ( let x = startX ; x < endX ; x += 1 ) { if ( influenceFactor < 0 && potentialArea [ x + y * potentialArea . width ] <= 0 ) { continue ; } const tempX = gridIx2Pos ( x , activeRegion . minX ) ; const tempY = gridIx2Pos ( y , activeRegion . minY ) ; const distanceSq = pointRectSquareDist ( { x : tempX , y : tempY } , { x : bbox . minX , y : bbox . minY , width : bbox . width , height : bbox . height } ) ; if ( distanceSq < options . nodeR1 ** 2 ) { const dr = Math . sqrt ( distanceSq ) - options . nodeR1 ; potentialArea . cells [ x + y * potentialArea . width ] += influenceFactor * dr * dr ; } } } } ; const addEdgeInfluence = ( line , influenceFactor ) => { const bbox = line . getBBox ( ) ; const [ startX , startY , endX , endY ] = getAffectedRegion ( bbox , options . edgeR1 ) ; for ( let y = startY ; y < endY ; y += 1 ) { for ( let x = startX ; x < endX ; x += 1 ) { if ( influenceFactor < 0 && potentialArea . cells [ x + y * potentialArea . width ] <= 0 ) { continue ; } const tempX = gridIx2Pos ( x , activeRegion . minX ) ; const tempY = gridIx2Pos ( y , activeRegion . minY ) ; const minDistanceSq = pointLineSquareDist ( { x : tempX , y : tempY } , line ) ; if ( minDistanceSq < options . edgeR1 ** 2 ) { const mdr = Math . sqrt ( minDistanceSq ) - options . edgeR1 ; potentialArea . cells [ x + y * potentialArea . width ] += influenceFactor * mdr * mdr ; } } } } ; if ( options . nodeInfluenceFactor ) { members . forEach ( ( item ) => { addItemInfluence ( item , options . nodeInfluenceFactor / nodeInfA ) ; } ) ; } if ( options . edgeInfluenceFactor ) { edges . forEach ( ( edge ) => { addEdgeInfluence ( edge , options . edgeInfluenceFactor / edgeInfA ) ; } ) ; } if ( options . negativeNodeInfluenceFactor ) { nonMembers . forEach ( ( item ) => { addItemInfluence ( item , options . negativeNodeInfluenceFactor / nodeInfA ) ; } ) ; } } function rerouteLine ( item , buffer , intersections , wrapNormal ) { const bbox = item . getBBox ( ) ; const [ topIntersect , leftIntersect , bottomIntersect , rightIntersect ] = intersections ; const cornerPos = { topLeft : { x : bbox . minX - buffer , y : bbox . minY - buffer } , topRight : { x : bbox . maxX + buffer , y : bbox . minY - buffer } , bottomLeft : { x : bbox . minX - buffer , y : bbox . maxY + buffer } , bottomRight : { x : bbox . maxX + buffer , y : bbox . maxY + buffer } , } ; const totalArea = bbox . height * bbox . width ; function calcHalfArea ( intersect1 , intersect2 ) { return bbox . width * ( ( intersect1 . y - bbox . minY + ( intersect2 . y - bbox . minY ) ) * 0.5 ) ; } if ( leftIntersect ) { if ( topIntersect ) return wrapNormal ? cornerPos . topLeft : cornerPos . bottomRight ; if ( bottomIntersect ) return wrapNormal ? cornerPos . bottomLeft : cornerPos . topRight ; const topArea = calcHalfArea ( leftIntersect , rightIntersect ) ; if ( topArea < totalArea * 0.5 ) { if ( leftIntersect . y > rightIntersect . y ) return wrapNormal ? cornerPos . topLeft : cornerPos . bottomRight ; return wrapNormal ? cornerPos . topRight : cornerPos . bottomLeft ; } if ( leftIntersect . y < rightIntersect . y ) return wrapNormal ? cornerPos . bottomLeft : cornerPos . topRight ; return wrapNormal ? cornerPos . bottomRight : cornerPos . topLeft ; } if ( rightIntersect ) { if ( topIntersect ) return wrapNormal ? cornerPos . topRight : cornerPos . bottomLeft ; if ( bottomIntersect ) return wrapNormal ? cornerPos . bottomRight : cornerPos . topLeft ; } const leftArea = calcHalfArea ( topIntersect , bottomIntersect ) ; if ( leftArea < totalArea * 0.5 ) { if ( topIntersect . x > bottomIntersect . x ) return wrapNormal ? cornerPos . topLeft : cornerPos . bottomRight ; return wrapNormal ? cornerPos . bottomLeft : cornerPos . topRight ; } if ( topIntersect . x < bottomIntersect . x ) return wrapNormal ? cornerPos . topRight : cornerPos . bottomLeft ; return wrapNormal ? cornerPos . bottomRight : cornerPos . topLeft ; }