import { Fraction , Line , Matrix , PathUtil } from "bp/math" ; import { Settings } from "bp/global" ; import type { Path , Point , Sign , Vector } from "bp/math" ; interface JIntersection { point : Point ; dist : Fraction ; angle : number ; /** 交點是否在線段內部 */ interior : boolean ; } interface TraceNode { point : Point ; vector : Vector ; shift ? : Vector ; } interface ShootingNode { intersection : JIntersection ; line : Line ; } /**
 * 產生軌跡的工具類別。
 */ export class Trace { private readonly _full : Path = [ ] ; private readonly _trace : Path = [ ] ; private readonly _record = new Set < string > ( ) ; private readonly _candidates : Set < Line > ; param _inflections param _endLine param _startLine constructor ( lines , private readonly _endPt , private readonly _inflections , private readonly _endLine , private readonly _startLine ? ) { this . _candidates = new Set ( lines ) ; } param startPt param sv public $create ( startPt , sv ) { let node = { point : startPt , vector : sv , } ; let isInLeadMode = Boolean ( this . _startLine ) ; let shooting = this . lineShooting ( node ) ; if ( DEBUG_ENABLED && Settings . debug ) { console . log ( "StartPt: " + startPt . toString ( ) ) ; console . log ( "Start: " + this . _startLine ?. toString ( ) ) ; console . log ( "Inflections: " , [ ... this . _inflections ] . toString ( ) ) ; } while ( shooting != null ) { let pt = shooting . intersection . point ; let segment = new Line ( node . point , pt ) ; if ( isInLeadMode ) isInLeadMode = ! this . _processLeadMode ( segment ) ; if ( this . _processGoal ( segment ) ) break ; this . detectLoop ( pt ) ; if ( ! isInLeadMode ) Trace . _pushIfNotEqual ( this . _trace , pt ) ; node = Trace . _reflect ( node , shooting ) ; this . _candidates . delete ( shooting . line ) ; shooting = this . lineShooting ( node ) ; } return this . _trace ; } /** 導繪模式的處理 */ private _processLeadMode ( segment ) { let p = segment . $intersection ( this . _startLine ! ) ; if ( p ) { this . _trace . push ( p ) ; return true ; } return false ; } /** 是否有撞到了終點（優先）或終點線 */ private _processGoal ( currentSegment ) { if ( currentSegment . $contains ( this . _endPt , true ) ) return true ; let goal = currentSegment . $intersection ( this . _endLine ) ; if ( goal ) { this . _trace . push ( goal ) ; return true ; } return false ; } /** 偵測迴圈；迴圈是只有當有 meandering 的時候才會產生 */ private detectLoop ( pt ) { let sg = pt . toString ( ) ; if ( this . _record . has ( sg ) ) { if ( ! pt . eq ( this . _full [ this . _full . length - 1 ] ) ) this . processLoop ( pt ) ; } else { this . _record . add ( sg ) ; } Trace . _pushIfNotEqual ( this . _full , pt ) ; } /**
     * 底下這段程式碼負責解決 ray shooting problem。
     *
     * 這邊我使用的是最直觀但也最沒有效率的逐一檢查每一條線段的方法，
     * 這樣做的話每回合都需要 O(n) 的運算量，再加上全部約有 O(n) 的回合數，
     * 全部的運算量高達 O(n^2)；然而從效能的角度來看，
     * 這一部份的計算耗時並不是目前最吃重的部份，所以並不是非常急著改進。
     */ private lineShooting ( node ) { let currentIntersection = null ; let currentLine = null ; let { point , vector , shift } = node ; for ( let line of this . _candidates ) { let intersection = Trace . $getIntersection ( line , point , vector ) ; if ( intersection ) { let angle = shift ? Trace . _getAngle ( vector , shift ) : undefined ; let f = this . _inflections . has ( intersection . point . toString ( ) ) ? - 1 : 1 ; if ( ! intersection . interior && ! Trace . _isSideTouchable ( line , point , vector , f , angle ) ) continue ; if ( DEBUG_ENABLED && Settings . debug ) { console . log ( [ JSON . stringify ( intersection ) , line . toString ( ) ] ) ; } if ( Trace . _intersectionCloser ( intersection , currentIntersection , f ) ) { currentIntersection = intersection ; currentLine = line ; } } } if ( currentIntersection == null || currentLine == null ) return null ; return { intersection : currentIntersection , line : currentLine , } ; } /** 如果造出軌跡的過程中出現迴圈，排除考慮一切完全落在迴圈裡面的線段 */ private processLoop ( pt ) { let path = [ ] , i = this . _full . length - 1 ; do { path . push ( this . _full [ i ] ) ; } while ( ! this . _full [ i -- ] . eq ( pt ) ) ; for ( let l of this . _candidates ) { if ( PathUtil . $lineInsidePath ( l , path ) ) this . _candidates . delete ( l ) ; } } private static _reflect ( node , shooting ) { let pt = shooting . intersection . point ; let line = shooting . line ; let result = { shift : line . $vector , vector : line . $reflect ( node . vector ) , point : pt , } ; if ( DEBUG_ENABLED && Settings . debug ) { console . log ( [ pt . toString ( ) , line . toString ( ) , result . vector . toString ( ) , line . $vector . toString ( ) , ] ) ; } return result ; } /** 取得指定線段和給定動向的交點 */ public static $getIntersection ( l , p , v ) { let v1 = l . p2 . sub ( l . p1 ) ; let m = new Matrix ( v1 . _x , v . _x , v1 . _y , v . _y ) . $inverse ; if ( m == null ) return null ; let r = m . $multiply ( p . sub ( l . p1 ) ) ; let a = r . _x , b = r . _y . neg ; if ( a . lt ( Fraction . ZERO ) || a . gt ( Fraction . ONE ) || b . lt ( Fraction . ZERO ) ) return null ; return { point : p . add ( v . $scale ( b ) ) , dist : b , angle : Trace . _getAngle ( v , v1 ) , interior : a . gt ( Fraction . ZERO ) && a . lt ( Fraction . ONE ) , } ; } /** 判斷傳入的交點 `r` 是否在特定意義上比起交點 `x` 更「近」 */ private static _intersectionCloser ( r , x , f ) { return x == null || r . dist . lt ( x . dist ) || r . dist . eq ( x . dist ) && r . angle * f < x . angle * f ; } private static _getAngle ( v1 , v2 ) { let ang = v1 . $angle - v2 . $angle ; while ( ang < 0 ) ang += Math . PI ; while ( ang > Math . PI ) ang -= Math . PI ; return ang ; } /** 給定一線段，想像一下、把給定的動向稍微往側邊平移，是否還能碰得到？ */ private static _isSideTouchable ( line , from , v , f , ang ? ) { let rv = v . $rotate90 ( ) ; let v1 = line . p1 . sub ( from ) , v2 = line . p2 . sub ( from ) ; let r1 = v1 . dot ( rv ) , r2 = v2 . dot ( rv ) ; let d1 = v1 . dot ( v ) , d2 = v2 . dot ( v ) ; let result = ( r1 * f > 0 || r2 * f > 0 ) && ( d1 > 0 || d2 > 0 || Boolean ( ang ) && Trace . _getAngle ( v , line . $vector ) * f > ang ! * f ) ; return result ; } private static _pushIfNotEqual ( array , pt ) { if ( ! array . length || ! array [ array . length - 1 ] . eq ( pt ) ) array . push ( pt ) ; } }