import { Epsilon } from "./Epsilon" ; import type { Path , Segment } from "./types" ; interface Match { index : number ; matches_head : boolean ; matches_pt1 : boolean ; } export function segmentChainer ( segments ) { let chains = [ ] ; let regions = [ ] ; segments . forEach ( ( seg ) => { let pt1 = seg . start ; let pt2 = seg . end ; if ( Epsilon . $pointsSame ( pt1 , pt2 ) ) { console . warn ( 'PolyBool: Warning: Zero-length segment detected; your epsilon is probably too small or too large' ) ; return ; } let first_match = { index : 0 , matches_head : false , matches_pt1 : false , } ; let second_match = { index : 0 , matches_head : false , matches_pt1 : false , } ; let next_match = first_match ; function setMatch ( index , matches_head , matches_pt1 ) { next_match ! . index = index ; next_match ! . matches_head = matches_head ; next_match ! . matches_pt1 = matches_pt1 ; if ( next_match === first_match ) { next_match = second_match ; return false ; } next_match = null ; return true ; } /**
         * 這邊採用線性搜尋的方式檢查所有的 chain，這乍看非常沒效率，
         * 但很意外地，實務上 chains 的大小頂多兩三個而已，所以不需要更進一步改進。
         */ for ( let i = 0 ; i < chains . length ; i ++ ) { let chain = chains [ i ] ; let head = chain [ 0 ] ; let tail = chain [ chain . length - 1 ] ; if ( Epsilon . $pointsSame ( head , pt1 ) ) { if ( setMatch ( i , true , true ) ) break ; } else if ( Epsilon . $pointsSame ( head , pt2 ) ) { if ( setMatch ( i , true , false ) ) break ; } else if ( Epsilon . $pointsSame ( tail , pt1 ) ) { if ( setMatch ( i , false , true ) ) break ; } else if ( Epsilon . $pointsSame ( tail , pt2 ) ) { if ( setMatch ( i , false , false ) ) break ; } } if ( next_match === first_match ) { chains . push ( [ pt1 , pt2 ] ) ; return ; } if ( next_match === second_match ) { let index = first_match . index ; let pt = first_match . matches_pt1 ? pt2 : pt1 ; let addToHead = first_match . matches_head ; let chain = chains [ index ] ; let grow = addToHead ? chain [ 0 ] : chain [ chain . length - 1 ] ; let grow2 = addToHead ? chain [ 1 ] : chain [ chain . length - 2 ] ; let oppo = addToHead ? chain [ chain . length - 1 ] : chain [ 0 ] ; let oppo2 = addToHead ? chain [ chain . length - 2 ] : chain [ 1 ] ; if ( Epsilon . $pointsCollinear ( grow2 , grow , pt ) ) { if ( addToHead ) { chain . shift ( ) ; } else { chain . pop ( ) ; } grow = grow2 ; } if ( Epsilon . $pointsSame ( oppo , pt ) ) { chains . splice ( index , 1 ) ; if ( Epsilon . $pointsCollinear ( oppo2 , oppo , grow ) ) { if ( addToHead ) { chain . pop ( ) ; } else { chain . shift ( ) ; } } regions . push ( chain ) ; return ; } if ( addToHead ) { chain . unshift ( pt ) ; } else { chain . push ( pt ) ; } return ; } function reverseChain ( index ) { chains [ index ] . reverse ( ) ; } function appendChain ( index1 , index2 ) { let chain1 = chains [ index1 ] ; let chain2 = chains [ index2 ] ; let tail = chain1 [ chain1 . length - 1 ] ; let tail2 = chain1 [ chain1 . length - 2 ] ; let head = chain2 [ 0 ] ; let head2 = chain2 [ 1 ] ; if ( Epsilon . $pointsCollinear ( tail2 , tail , head ) ) { chain1 . pop ( ) ; tail = tail2 ; } if ( Epsilon . $pointsCollinear ( tail , head , head2 ) ) { chain2 . shift ( ) ; } chains [ index1 ] = chain1 . concat ( chain2 ) ; chains . splice ( index2 , 1 ) ; } let F = first_match . index ; let S = second_match . index ; let reverseF = chains [ F ] . length < chains [ S ] . length ; if ( first_match . matches_head ) { if ( second_match . matches_head ) { if ( reverseF ) { reverseChain ( F ) ; appendChain ( F , S ) ; } else { reverseChain ( S ) ; appendChain ( S , F ) ; } } else { appendChain ( S , F ) ; } } else if ( second_match . matches_head ) { appendChain ( F , S ) ; } else if ( reverseF ) { reverseChain ( F ) ; appendChain ( S , F ) ; } else { reverseChain ( S ) ; appendChain ( F , S ) ; } } ) ; return regions ; }