import { Point , IGroup } from '@antv/g-base' ; import { mat3 , vec3 , ext , vec2 } from '@antv/matrix-util' ; import { isArray , each } from '@antv/util' ; import { GraphData , ICircle , IEllipse , IRect , Matrix , EdgeConfig , NodeIdxMap , IBBox , Item , IPoint , GraphAnimateConfig } from '../types' ; const transform = ext . transform ; param { string } attributeName param { number } min param { number } max return { boolean } export const compare = ( attributeName ) => { return ( m , n ) => { return m [ attributeName ] - n [ attributeName ] ; } ; } ; param { number } value param { number } min param { number } max return { boolean } const isBetween = ( value , min , max ) => value >= min && value <= max ; param { Point } p0 param { Point } p1 param { Point } p2 param { Point } p3 return { Point } export const getLineIntersect = ( p0 , p1 , p2 , p3 ) : Point | null => { const tolerance = 0.0001 ; const E = { x : p2 . x - p0 . x , y : p2 . y - p0 . y , } ; const D0 = { x : p1 . x - p0 . x , y : p1 . y - p0 . y , } ; const D1 = { x : p3 . x - p2 . x , y : p3 . y - p2 . y , } ; const kross = D0 . x * D1 . y - D0 . y * D1 . x ; const sqrKross = kross * kross ; const invertKross = 1 / kross ; const sqrLen0 = D0 . x * D0 . x + D0 . y * D0 . y ; const sqrLen1 = D1 . x * D1 . x + D1 . y * D1 . y ; if ( sqrKross > tolerance * sqrLen0 * sqrLen1 ) { const s = ( E . x * D1 . y - E . y * D1 . x ) * invertKross ; const t = ( E . x * D0 . y - E . y * D0 . x ) * invertKross ; if ( ! isBetween ( s , 0 , 1 ) || ! isBetween ( t , 0 , 1 ) ) return null ; return { x : p0 . x + s * D0 . x , y : p0 . y + s * D0 . y , } ; } return null ; } ; param { IRect } rect param { Point } point return { PointPoint } export const getRectIntersectByPoint = ( rect , point ) : Point | null => { const { x , y , width , height } = rect ; const cx = x + width / 2 ; const cy = y + height / 2 ; const points = [ ] ; const center = { x : cx , y : cy , } ; points . push ( { x , y , } ) ; points . push ( { x : x + width , y , } ) ; points . push ( { x : x + width , y : y + height , } ) ; points . push ( { x , y : y + height , } ) ; points . push ( { x , y , } ) ; let rst = null ; for ( let i = 1 ; i < points . length ; i ++ ) { rst = getLineIntersect ( points [ i - 1 ] , points [ i ] , center , point ) ; if ( rst ) { break ; } } return rst ; } ; param { ICircle } circle param { Point } point return { Point } export const getCircleIntersectByPoint = ( circle , point ) : Point | null => { const { x : cx , y : cy , r } = circle ; const { x , y } = point ; const dx = x - cx ; const dy = y - cy ; if ( dx * dx + dy * dy < r * r ) { return null ; } const angle = Math . atan ( dy / dx ) ; return { x : cx + Math . abs ( r * Math . cos ( angle ) ) * Math . sign ( dx ) , y : cy + Math . abs ( r * Math . sin ( angle ) ) * Math . sign ( dy ) , } ; } ; param { Object } ellipse param { Object } point return { object } export const getEllipseIntersectByPoint = ( ellipse , point ) : Point => { const a = ellipse . rx ; const b = ellipse . ry ; const cx = ellipse . x ; const cy = ellipse . y ; const dx = point . x - cx ; const dy = point . y - cy ; let angle = Math . atan2 ( dy / b , dx / a ) ; if ( angle < 0 ) { angle += 2 * Math . PI ; } return { x : cx + a * Math . cos ( angle ) , y : cy + b * Math . sin ( angle ) , } ; } ; param { number } point param { Matrix } matrix param { number } tag return { Point } export const applyMatrix = ( point , matrix , tag = 1 ) : Point => { const vector = [ point . x , point . y , tag ] ; if ( ! matrix || isNaN ( matrix [ 0 ] ) ) { matrix = [ 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 ] ; } vec3 . transformMat3 ( vector , vector , matrix as mat3 ) ; return { x : vector [ 0 ] , y : vector [ 1 ] , } ; } ; param { number } point param { number } matrix param { number } tag return { object } export const invertMatrix = ( point , matrix , tag = 1 ) : Point => { if ( ! matrix || isNaN ( matrix [ 0 ] ) ) { matrix = [ 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 ] ; } let inversedMatrix = mat3 . invert ( [ 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 ] , matrix as mat3 ) ; if ( ! inversedMatrix ) { inversedMatrix = [ 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 ] ; } const vector = [ point . x , point . y , tag ] ; vec3 . transformMat3 ( vector , vector , inversedMatrix ) ; return { x : vector [ 0 ] , y : vector [ 1 ] , } ; } ; param p1 param p2 param p3 export const getCircleCenterByPoints = ( p1 , p2 , p3 ) : Point => { const a = p1 . x - p2 . x ; const b = p1 . y - p2 . y ; const c = p1 . x - p3 . x ; const d = p1 . y - p3 . y ; const e = ( p1 . x * p1 . x - p2 . x * p2 . x - p2 . y * p2 . y + p1 . y * p1 . y ) / 2 ; const f = ( p1 . x * p1 . x - p3 . x * p3 . x - p3 . y * p3 . y + p1 . y * p1 . y ) / 2 ; const denominator = b * c - a * d ; return { x : - ( d * e - b * f ) / denominator , y : - ( a * f - c * e ) / denominator , } ; } ; param p1 param p2 export const distance = ( p1 , p2 ) : number => { const vx = p1 . x - p2 . x ; const vy = p1 . y - p2 . y ; return Math . sqrt ( vx * vx + vy * vy ) ; } ; param matrix param ratio export const scaleMatrix = ( matrix , ratio ) => { const result = [ ] ; matrix . forEach ( row => { const newRow = [ ] ; row . forEach ( v => { newRow . push ( v * ratio ) ; } ) ; result . push ( newRow ) ; } ) ; return result ; } ; param { array } adjMatrix return { array } export const floydWarshall = ( adjMatrix ) : Matrix [ ] => { const dist = [ ] ; const size = adjMatrix . length ; for ( let i = 0 ; i < size ; i += 1 ) { dist [ i ] = [ ] ; for ( let j = 0 ; j < size ; j += 1 ) { if ( i === j ) { dist [ i ] [ j ] = 0 ; } else if ( adjMatrix [ i ] [ j ] === 0 || ! adjMatrix [ i ] [ j ] ) { dist [ i ] [ j ] = Infinity ; } else { dist [ i ] [ j ] = adjMatrix [ i ] [ j ] ; } } } for ( let k = 0 ; k < size ; k += 1 ) { for ( let i = 0 ; i < size ; i += 1 ) { for ( let j = 0 ; j < size ; j += 1 ) { if ( dist [ i ] [ j ] > dist [ i ] [ k ] + dist [ k ] [ j ] ) { dist [ i ] [ j ] = dist [ i ] [ k ] + dist [ k ] [ j ] ; } } } } return dist ; } ; param data param directed export const getAdjMatrix = ( data , directed ) : Matrix [ ] => { const { nodes , edges } = data ; const matrix = [ ] ; const nodeMap = { } ; if ( ! nodes ) { throw new Error ( 'invalid nodes data!' ) ; } if ( nodes ) { nodes . forEach ( ( node , i ) => { nodeMap [ node . id ] = i ; const row = [ ] ; matrix . push ( row ) ; } ) ; } if ( edges ) { edges . forEach ( e => { const { source , target } = e ; const sIndex = nodeMap [ source as string ] ; const tIndex = nodeMap [ target as string ] ; matrix [ sIndex ] [ tIndex ] = 1 ; if ( ! directed ) { matrix [ tIndex ] [ sIndex ] = 1 ; } } ) ; } return matrix ; } ; param group param vec export const translate = ( group , vec ) => { group . translate ( vec . x , vec . y ) ; } ; param group param point export const move = ( group , point , animate ? , animateCfg = { duration : 500 } ) => { let matrix = group . getMatrix ( ) ; if ( ! matrix ) { matrix = [ 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 ] ; } const bbox = group . getCanvasBBox ( ) ; const vx = point . x - bbox . minX ; const vy = point . y - bbox . minY ; if ( animate ) { const dx = vx * matrix [ 0 ] ; const dy = vy * matrix [ 4 ] ; let lastX = 0 ; let lastY = 0 ; let newX = 0 ; let newY = 0 ; group . animate ( ( ratio ) => { newX = dx * ratio ; newY = dy * ratio ; matrix = transform ( matrix , [ [ 't' , newX - lastX , newY - lastY ] ] ) ; lastX = newX ; lastY = newY ; return { matrix } ; } , animateCfg ) ; } else { const movedMatrix = transform ( matrix , [ [ 't' , vx , vy ] ] ) ; group . setMatrix ( movedMatrix ) ; } } ; param group param point export const scale = ( group , ratio ) => { let matrix = group . getMatrix ( ) ; if ( ! matrix ) { matrix = [ 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 ] ; } let scaleXY = ratio ; if ( ! isArray ( ratio ) ) { scaleXY = [ ratio , ratio ] ; } if ( isArray ( ratio ) && ratio . length === 1 ) { scaleXY = [ ratio [ 0 ] , ratio [ 0 ] ] ; } matrix = transform ( matrix , [ [ 's' , ( scaleXY as number [ ] ) [ 0 ] , ( scaleXY as number [ ] ) [ 1 ] ] ] ) ; group . setMatrix ( matrix ) ; } ; param group param ratio export const rotate = ( group , angle ) => { let matrix = group . getMatrix ( ) ; if ( ! matrix ) { matrix = [ 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 ] ; } matrix = transform ( matrix , [ [ 'r' , angle ] ] ) ; group . setMatrix ( matrix ) ; } ; export const getDegree = ( n , nodeIdxMap , edges ) : number [ ] => { const degrees = [ ] ; for ( let i = 0 ; i < n ; i ++ ) { degrees [ i ] = 0 ; } edges . forEach ( e => { if ( e . source ) { degrees [ nodeIdxMap [ e . source ] ] += 1 ; } if ( e . target ) { degrees [ nodeIdxMap [ e . target ] ] += 1 ; } } ) ; return degrees ; } ; function onSegment ( p1 , p2 , q ) { if ( ( q [ 0 ] - p1 [ 0 ] ) * ( p2 [ 1 ] - p1 [ 1 ] ) === ( p2 [ 0 ] - p1 [ 0 ] ) * ( q [ 1 ] - p1 [ 1 ] ) && Math . min ( p1 [ 0 ] , p2 [ 0 ] ) <= q [ 0 ] && q [ 0 ] <= Math . max ( p1 [ 0 ] , p2 [ 0 ] ) && Math . min ( p1 [ 1 ] , p2 [ 1 ] ) <= q [ 1 ] && q [ 1 ] <= Math . max ( p1 [ 1 ] , p2 [ 1 ] ) ) { return true ; } return false ; } param points param x param y export const isPointInPolygon = ( points , x , y ) => { let isHit = false ; const n = points . length ; const tolerance = 1e-6 ; function dcmp ( xValue ) { if ( Math . abs ( xValue ) < tolerance ) { return 0 ; } return xValue < 0 ? - 1 : 1 ; } if ( n <= 2 ) { return false ; } for ( let i = 0 ; i < n ; i ++ ) { const p1 = points [ i ] ; const p2 = points [ ( i + 1 ) % n ] ; if ( onSegment ( p1 , p2 , [ x , y ] ) ) { return true ; } if ( dcmp ( p1 [ 1 ] - y ) > 0 !== dcmp ( p2 [ 1 ] - y ) > 0 && dcmp ( x - ( ( y - p1 [ 1 ] ) * ( p1 [ 0 ] - p2 [ 0 ] ) ) / ( p1 [ 1 ] - p2 [ 1 ] ) - p1 [ 0 ] ) < 0 ) { isHit = ! isHit ; } } return isHit ; } ; export const intersectBBox = ( box1 , box2 ) => { return ! ( box2 . minX > box1 . maxX || box2 . maxX < box1 . minX || box2 . minY > box1 . maxY || box2 . maxY < box1 . minY ) ; } ; const lineIntersectPolygon = ( lines , line ) => { let isIntersect = false ; each ( lines , l => { if ( getLineIntersect ( l . from , l . to , line . from , line . to ) ) { isIntersect = true ; return false ; } } ) ; return isIntersect ; } ; param points1 param points2 export const isPolygonsIntersect = ( points1 , points2 ) : boolean => { type BBox = Partial < IBBox > ; const getBBox = ( points ) : BBox => { const xArr = points . map ( p => p [ 0 ] ) ; const yArr = points . map ( p => p [ 1 ] ) ; return { minX : Math . min . apply ( null , xArr ) , maxX : Math . max . apply ( null , xArr ) , minY : Math . min . apply ( null , yArr ) , maxY : Math . max . apply ( null , yArr ) , } ; } ; const parseToLines = ( points ) => { const lines = [ ] ; const count = points . length ; for ( let i = 0 ; i < count - 1 ; i ++ ) { const point = points [ i ] ; const next = points [ i + 1 ] ; lines . push ( { from : { x : point [ 0 ] , y : point [ 1 ] , } , to : { x : next [ 0 ] , y : next [ 1 ] , } , } ) ; } if ( lines . length > 1 ) { const first = points [ 0 ] ; const last = points [ count - 1 ] ; lines . push ( { from : { x : last [ 0 ] , y : last [ 1 ] , } , to : { x : first [ 0 ] , y : first [ 1 ] , } , } ) ; } return lines ; } ; if ( points1 . length < 2 || points2 . length < 2 ) { return false ; } const bbox1 = getBBox ( points1 ) ; const bbox2 = getBBox ( points2 ) ; if ( ! intersectBBox ( bbox1 , bbox2 ) ) { return false ; } let isIn = false ; each ( points2 , point => { if ( isPointInPolygon ( points1 , point [ 0 ] , point [ 1 ] ) ) { isIn = true ; return false ; } } ) ; if ( isIn ) { return true ; } each ( points1 , point => { if ( isPointInPolygon ( points2 , point [ 0 ] , point [ 1 ] ) ) { isIn = true ; return false ; } } ) ; if ( isIn ) { return true ; } const lines1 = parseToLines ( points1 ) ; const lines2 = parseToLines ( points2 ) ; let isIntersect = false ; each ( lines2 , line => { if ( lineIntersectPolygon ( lines1 , line ) ) { isIntersect = true ; return false ; } } ) ; return isIntersect ; } ; export class Line { public x1 : number ; public y1 : number ; public x2 : number ; public y2 : number ; constructor ( x1 , y1 , x2 , y2 ) { this . x1 = x1 ; this . y1 = y1 ; this . x2 = x2 ; this . y2 = y2 ; } public getBBox ( ) { const minX = Math . min ( this . x1 , this . x2 ) ; const minY = Math . min ( this . y1 , this . y2 ) ; const maxX = Math . max ( this . x1 , this . x2 ) ; const maxY = Math . max ( this . y1 , this . y2 ) ; const res = { x : minX , y : minY , minX , minY , maxX , maxY , width : maxX - minX , height : maxY - minY , } ; return res ; } } export const getBBoxBoundLine = ( bbox , direction ) => { const bounds = { top : [ bbox . minX , bbox . minY , bbox . maxX , bbox . minY ] , left : [ bbox . minX , bbox . minY , bbox . minX , bbox . maxY ] , bottom : [ bbox . minX , bbox . maxY , bbox . maxX , bbox . maxY ] , right : [ bbox . maxX , bbox . minY , bbox . maxX , bbox . maxY ] , } ; return bounds [ direction ] ; } ; /**
 * 计算两条线段相交时，相交点对第一条线段上的分割比例
 */ const fractionAlongLineA = ( la , lb ) => { const uaT = ( lb . x2 - lb . x1 ) * ( la . y1 - lb . y1 ) - ( lb . y2 - lb . y1 ) * ( la . x1 - lb . x1 ) ; const ubT = ( la . x2 - la . x1 ) * ( la . y1 - lb . y1 ) - ( la . y2 - la . y1 ) * ( la . x1 - lb . x1 ) ; const uB = ( lb . y2 - lb . y1 ) * ( la . x2 - la . x1 ) - ( lb . x2 - lb . x1 ) * ( la . y2 - la . y1 ) ; if ( uB ) { const ua = uaT / uB ; const ub = ubT / uB ; if ( ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1 ) { return ua ; } } return Number . POSITIVE_INFINITY ; } ; export const itemIntersectByLine = ( item , line ) : [ IPoint [ ] , number ] => { const directions = [ 'top' , 'left' , 'bottom' , 'right' ] ; const bbox = item . getBBox ( ) ; let countIntersections = 0 ; const intersections = [ ] ; for ( let i = 0 ; i < 4 ; i ++ ) { const [ x1 , y1 , x2 , y2 ] = getBBoxBoundLine ( bbox , directions [ i ] ) ; intersections [ i ] = getLineIntersect ( { x : line . x1 , y : line . y1 } , { x : line . x2 , y : line . y2 } , { x : x1 , y : y1 } , { x : x2 , y : y2 } ) ; if ( intersections [ i ] ) { countIntersections += 1 ; } } return [ intersections , countIntersections ] ; } ; export const fractionToLine = ( item , line ) => { const directions = [ 'top' , 'left' , 'bottom' , 'right' ] ; const bbox = item . getBBox ( ) ; let minDistance = Number . POSITIVE_INFINITY ; let countIntersections = 0 ; for ( let i = 0 ; i < 4 ; i ++ ) { const [ x1 , y1 , x2 , y2 ] = getBBoxBoundLine ( bbox , directions [ i ] ) ; let testDistance = fractionAlongLineA ( line , new Line ( x1 , y1 , x2 , y2 ) ) ; testDistance = Math . abs ( testDistance - 0.5 ) ; if ( testDistance >= 0 && testDistance <= 1 ) { countIntersections += 1 ; minDistance = testDistance < minDistance ? testDistance : minDistance ; } } if ( countIntersections === 0 ) return - 1 ; return minDistance ; } ; export const getPointsCenter = ( points ) : IPoint => { let centerX = 0 ; let centerY = 0 ; if ( points . length > 0 ) { for ( const point of points ) { centerX += point . x ; centerY += point . y ; } centerX /= points . length ; centerY /= points . length ; } return { x : centerX , y : centerY } ; } ; export const squareDist = ( a , b ) : number => { return ( a . x - b . x ) ** 2 + ( a . y - b . y ) ** 2 ; } ; export const pointLineSquareDist = ( point , line ) => { const x1 = line . x1 ; const y1 = line . y1 ; const x2 = line . x2 - x1 ; const y2 = line . y2 - y1 ; let px = point . x - x1 ; let py = point . y - y1 ; let dotprod = px * x2 + py * y2 ; let projlenSq ; if ( dotprod <= 0 ) { projlenSq = 0 ; } else { px = x2 - px ; py = y2 - py ; dotprod = px * x2 + py * y2 ; if ( dotprod <= 0 ) { projlenSq = 0 ; } else { projlenSq = ( dotprod * dotprod ) / ( x2 * x2 + y2 * y2 ) ; } } let lenSq = px * px + py * py - projlenSq ; if ( lenSq < 0 ) { lenSq = 0 ; } return lenSq ; } ; export const isPointsOverlap = ( p1 , p2 , e = 1e-3 ) => { return ( p1 . x - p2 . x ) ** 2 + ( p1 . y - p2 . y ) ** 2 < e ** 2 ; } ; param point param rect export const pointRectSquareDist = ( point , rect ) => { const isLeft = point . x < rect . x ; const isRight = point . x > rect . x + rect . width ; const isTop = point . y > rect . y + rect . height ; const isBottom = point . y < rect . y ; const isPointOutside = isLeft || isRight || isTop || isBottom ; if ( ! isPointOutside ) { return 0 ; } if ( isTop && ! isLeft && ! isRight ) { return ( rect . y + rect . height - point . y ) ** 2 ; } if ( isBottom && ! isLeft && ! isRight ) { return ( point . y - rect . y ) ** 2 ; } if ( isLeft && ! isTop && ! isBottom ) { return ( rect . x - point . x ) ** 2 ; } if ( isRight && ! isTop && ! isBottom ) { return ( rect . x + rect . width - point . x ) ** 2 ; } const dx = Math . min ( Math . abs ( rect . x - point . x ) , Math . abs ( rect . x + rect . width - point . x ) ) ; const dy = Math . min ( Math . abs ( rect . y - point . y ) , Math . abs ( rect . y + rect . height - point . y ) ) ; return dx * dx + dy * dy ; } ; param { array } line param { object } point return { Number | NaN } export const pointLineDistance = ( line , point ) => { const [ x1 , y1 , x2 , y2 ] = line ; const { x , y } = point ; const d = [ x2 - x1 , y2 - y1 ] ; if ( vec2 . exactEquals ( d as any , [ 0 , 0 ] ) ) { return NaN ; } const u = [ - d [ 1 ] , d [ 0 ] ] ; vec2 . normalize ( u , u ) ; const a = [ x - x1 , y - y1 ] ; return Math . abs ( vec2 . dot ( a , u ) ) ; } ; param { Number } start param { Number } end param { Number } alpha returns export const lerp = ( start , end , alpha ) : number => { return start + ( end - start ) * alpha ; } ;