import { last } from '@mathigon/core' ; import { nearlyEquals } from '@mathigon/fermat' ; import { Point } from './point' ; const PRECISION = 0.000001 ; function pointAboveOrOnLine ( pt , left , right ) { const d1 = ( right . x - left . x ) * ( pt . y - left . y ) ; const d2 = ( right . y - left . y ) * ( pt . x - left . x ) ; return d1 - d2 >= - PRECISION ; } function pointBetween ( p , left , right ) { const dpyly = p . y - left . y ; const drxlx = right . x - left . x ; const dpxlx = p . x - left . x ; const dryly = right . y - left . y ; const dot = dpxlx * drxlx + dpyly * dryly ; if ( dot < PRECISION ) return false ; const sqlen = drxlx * drxlx + dryly * dryly ; return dot - sqlen <= - PRECISION ; } function pointsCompare ( p1 , p2 ) { if ( nearlyEquals ( p1 . x , p2 . x ) ) { return nearlyEquals ( p1 . y , p2 . y ) ? 0 : ( p1 . y < p2 . y ? - 1 : 1 ) ; } return p1 . x < p2 . x ? - 1 : 1 ; } /**
 * Categorize where intersection point is along A and B:
 *  -2: intersection point is before segment's first point
 *  -1: intersection point is directly on segment's first point
 *   0: intersection point is between segment's first and second points (exclusive)
 *   1: intersection point is directly on segment's second point
 *   2: intersection point is after segment's second point
 */ function getOffset ( A ) { if ( A <= - PRECISION ) return - 2 ; if ( A < PRECISION ) return - 1 ; if ( A - 1 <= - PRECISION ) return 0 ; if ( A - 1 < PRECISION ) return 1 ; return 2 ; } function linesIntersect ( a0 , a1 , b0 , b1 ) { const adx = a1 . x - a0 . x ; const ady = a1 . y - a0 . y ; const bdx = b1 . x - b0 . x ; const bdy = b1 . y - b0 . y ; const axb = adx * bdy - ady * bdx ; if ( nearlyEquals ( axb , 0 ) ) return false ; const dx = a0 . x - b0 . x ; const dy = a0 . y - b0 . y ; const A = ( bdx * dy - bdy * dx ) / axb ; const B = ( adx * dy - ady * dx ) / axb ; const pt = new Point ( a0 . x + A * adx , a0 . y + A * ady ) ; return { alongA : getOffset ( A ) , alongB : getOffset ( B ) , pt } ; } type Node < T > = { prev ? : Node < T > ; next ? : Node < T > ; root ? : boolean ; remove : ( ) => void ; } & T ; interface Segment { start : Point ; end : Point ; myFill : { above ? : boolean ; below ? : boolean ; } ; otherFill ? : { above ? : boolean ; below ? : boolean ; } ; } interface Event { isStart ? : boolean ; pt : Point ; seg : Segment ; primary ? : boolean ; other ? : Node < Event > ; status ? : Node < Event > ; ev ? : Node < Event > ; } type Status = { ev : Node < Event > ; } ; class LinkedList < T > { root : any = { root : true , next : undefined } ; exists ( node ) { return node !== undefined && node !== this . root ; } get head ( ) { return this . root . next ; } insertBefore ( node , check ) { let last = this . root ; let here = this . root . next ; while ( here ) { if ( check ( here ) ) { node . prev = here . prev ; node . next = here ; here . prev . next = node ; here . prev = node ; return ; } last = here ; here = here . next ; } last . next = node ; node . prev = last ; node . next = undefined ; } findTransition ( check ) { let prev = this . root ; let here = this . root . next ; while ( here ) { if ( check ( here ) ) break ; prev = here ; here = here . next ; } return { before : prev === this . root ? undefined : prev , after : here , insert : ( node ) => { node . prev = prev ; node . next = here ; prev . next = node ; if ( here ) here . prev = node ; return node ; } } ; } static node < T > ( data ) { const d = data as Node < T > ; d . remove = ( ) => { if ( d . prev ) d . prev . next = d . next ; if ( d . next ) d . next . prev = d . prev ; d . prev = d . next = undefined ; } ; return d ; } } function copy ( start , end , seg ) { const myFill = { above : seg . myFill . above , below : seg . myFill . below } ; return { start , end , myFill } ; } function eventCompare ( p1isStart , p11 , p12 , p2isStart , p21 , p22 ) { const comp = pointsCompare ( p11 , p21 ) ; if ( comp !== 0 ) return comp ; if ( Point . equals ( p12 , p22 ) ) return 0 ; if ( p1isStart !== p2isStart ) return p1isStart ? 1 : - 1 ; return pointAboveOrOnLine ( p12 , p2isStart ? p21 : p22 , p2isStart ? p22 : p21 ) ? 1 : - 1 ; } function eventAdd ( eventRoot , ev , otherPt ) { eventRoot . insertBefore ( ev , ( here ) => eventCompare ( ! ! ev . isStart , ev . pt , otherPt , ! ! here . isStart , here . pt , here . other ! . pt ) < 0 ) ; } function addSegmentStart ( eventRoot , seg , primary ) { const evStart = LinkedList . node ( { isStart : true , pt : seg . start , seg , primary } ) ; eventAdd ( eventRoot , evStart , seg . end ) ; return evStart ; } function addSegmentEnd ( eventRoot , evStart , seg , primary ) { const evEnd = LinkedList . node ( { pt : seg . end , seg , primary , other : evStart } ) ; evStart . other = evEnd ; eventAdd ( eventRoot , evEnd , evStart . pt ) ; } function addSegment ( eventRoot , seg , primary ) { const evStart = addSegmentStart ( eventRoot , seg , primary ) ; addSegmentEnd ( eventRoot , evStart , seg , primary ) ; return evStart ; } function eventUpdateEnd ( eventRoot , ev , end ) { ev . other ! . remove ( ) ; ev . seg . end = end ; ev . other ! . pt = end ; eventAdd ( eventRoot , ev . other ! , ev . pt ) ; } function eventDivide ( eventRoot , ev , pt ) { const ns = copy ( pt , ev . seg . end , ev . seg ) ; eventUpdateEnd ( eventRoot , ev , pt ) ; return addSegment ( eventRoot , ns , ! ! ev . primary ) ; } function statusCompare ( ev1 , ev2 ) { const a1 = ev1 . seg . start ; const a2 = ev1 . seg . end ; const b1 = ev2 . seg . start ; const b2 = ev2 . seg . end ; if ( ! Point . colinear ( a1 , b1 , b2 ) ) return pointAboveOrOnLine ( a1 , b1 , b2 ) ? 1 : - 1 ; if ( ! Point . colinear ( a2 , b1 , b2 ) ) return pointAboveOrOnLine ( a2 , b1 , b2 ) ? 1 : - 1 ; return 1 ; } /** Returns the segment equal to ev1, or false if nothing equal. */ function checkIntersection ( eventRoot , ev1 , ev2 ) { const seg1 = ev1 . seg ; const seg2 = ev2 . seg ; const a1 = seg1 . start ; const a2 = seg1 . end ; const b1 = seg2 . start ; const b2 = seg2 . end ; const i = linesIntersect ( a1 , a2 , b1 , b2 ) ; if ( i === false ) { if ( ! Point . colinear ( a1 , a2 , b1 ) ) return false ; if ( Point . equals ( a1 , b2 ) || Point . equals ( a2 , b1 ) ) return false ; const a1isb1 = Point . equals ( a1 , b1 ) ; const a2isb2 = Point . equals ( a2 , b2 ) ; if ( a1isb1 && a2isb2 ) return ev2 ; const a1Between = ! a1isb1 && pointBetween ( a1 , b1 , b2 ) ; const a2Between = ! a2isb2 && pointBetween ( a2 , b1 , b2 ) ; if ( a1isb1 ) { a2Between ? eventDivide ( eventRoot , ev2 , a2 ) : eventDivide ( eventRoot , ev1 , b2 ) ; return ev2 ; } else if ( a1Between ) { if ( ! a2isb2 ) { a2Between ? eventDivide ( eventRoot , ev2 , a2 ) : eventDivide ( eventRoot , ev1 , b2 ) ; } eventDivide ( eventRoot , ev2 , a1 ) ; } } else { if ( i . alongA === 0 ) { if ( i . alongB === - 1 ) { eventDivide ( eventRoot , ev1 , b1 ) ; } else if ( i . alongB === 0 ) { eventDivide ( eventRoot , ev1 , i . pt ) ; } else if ( i . alongB === 1 ) { eventDivide ( eventRoot , ev1 , b2 ) ; } } if ( i . alongB === 0 ) { if ( i . alongA === - 1 ) { eventDivide ( eventRoot , ev2 , a1 ) ; } else if ( i . alongA === 0 ) { eventDivide ( eventRoot , ev2 , i . pt ) ; } else if ( i . alongA === 1 ) { eventDivide ( eventRoot , ev2 , a2 ) ; } } } return false ; } function calculate ( eventRoot , selfIntersection ) { const statusRoot = new LinkedList < Status > ( ) ; const segments = [ ] ; while ( eventRoot . head ) { const ev = eventRoot . head ; if ( ev . isStart ) { const surrounding = statusRoot . findTransition ( ( here ) => statusCompare ( ev , here . ev ) > 0 ) ; const above = surrounding . before ?. ev ; const below = surrounding . after ?. ev ; function checkBothIntersections ( ) { if ( above ) { const eve = checkIntersection ( eventRoot , ev , above ) ; if ( eve ) return eve ; } if ( below ) return checkIntersection ( eventRoot , ev , below ) ; return false ; } const eve = checkBothIntersections ( ) ; if ( eve ) { if ( selfIntersection ) { const toggle = ! ev . seg . myFill . below ? true : ev . seg . myFill . above !== ev . seg . myFill . below ; if ( toggle ) eve . seg . myFill . above = ! eve . seg . myFill . above ; } else { eve . seg . otherFill = ev . seg . myFill ; } ev . other . remove ( ) ; ev . remove ( ) ; } if ( eventRoot . head !== ev ) continue ; if ( selfIntersection ) { const toggle = ( ! ev . seg . myFill . below ) ? true : ev . seg . myFill . above !== ev . seg . myFill . below ; ev . seg . myFill . below = ! below ? false : below . seg . myFill . above ; ev . seg . myFill . above = toggle ? ! ev . seg . myFill . below : ev . seg . myFill . below ; } else if ( ev . seg . otherFill === undefined ) { const inside = ! below ? false : ( ev . primary === below . primary ) ? below . seg . otherFill . above : below . seg . myFill . above ; ev . seg . otherFill = { above : inside , below : inside } ; } ev . other . status = surrounding . insert ( LinkedList . node ( { ev } ) ) ; } else { const st = ev . status ; if ( st === undefined ) throw new Error ( '[Euclid.js] Zero-length segment detected!' ) ; if ( statusRoot . exists ( st . prev ) && statusRoot . exists ( st . next ) ) { checkIntersection ( eventRoot , st . prev . ev , st . next . ev ) ; } st . remove ( ) ; if ( ! ev . primary ) { const s = ev . seg . myFill ; ev . seg . myFill = ev . seg . otherFill ; ev . seg . otherFill = s ; } segments . push ( ev . seg ) ; } eventRoot . head . remove ( ) ; } return segments ; } function segmentChainer ( segments ) { const chains = [ ] ; const regions = [ ] ; segments . forEach ( ( seg ) => { const pt1 = seg . start ; const pt2 = seg . end ; if ( Point . equals ( pt1 , pt2 ) ) return ; const firstMatch = { index : 0 , matchesHead : false , matchesPt1 : false } ; const secondMatch = { index : 0 , matchesHead : false , matchesPt1 : false } ; let nextMatch = firstMatch ; function setMatch ( index , matchesHead , matchesPt1 ) { nextMatch . index = index ; nextMatch . matchesHead = matchesHead ; nextMatch . matchesPt1 = matchesPt1 ; const match = nextMatch === firstMatch ; nextMatch = match ? secondMatch : undefined ; return ! match ; } for ( let i = 0 ; i < chains . length ; i ++ ) { const chain = chains [ i ] ; const head = chain [ 0 ] ; const tail = last ( chain ) ; if ( Point . equals ( head , pt1 ) ) { if ( setMatch ( i , true , true ) ) break ; } else if ( Point . equals ( head , pt2 ) ) { if ( setMatch ( i , true , false ) ) break ; } else if ( Point . equals ( tail , pt1 ) ) { if ( setMatch ( i , false , true ) ) break ; } else if ( Point . equals ( tail , pt2 ) ) { if ( setMatch ( i , false , false ) ) break ; } } if ( nextMatch === firstMatch ) { chains . push ( [ pt1 , pt2 ] ) ; return ; } if ( nextMatch === secondMatch ) { const index = firstMatch . index ; const pt = firstMatch . matchesPt1 ? pt2 : pt1 ; const addToHead = firstMatch . matchesHead ; const chain = chains [ index ] ; let grow = addToHead ? chain [ 0 ] : chain [ chain . length - 1 ] ; const grow2 = addToHead ? chain [ 1 ] : chain [ chain . length - 2 ] ; const oppo = addToHead ? chain [ chain . length - 1 ] : chain [ 0 ] ; const oppo2 = addToHead ? chain [ chain . length - 2 ] : chain [ 1 ] ; if ( Point . colinear ( grow2 , grow , pt ) ) { addToHead ? chain . shift ( ) : chain . pop ( ) ; grow = grow2 ; } if ( Point . equals ( oppo , pt ) ) { chains . splice ( index , 1 ) ; if ( Point . colinear ( oppo2 , oppo , grow ) ) { addToHead ? chain . pop ( ) : chain . shift ( ) ; } regions . push ( chain ) ; return ; } addToHead ? chain . unshift ( pt ) : chain . push ( pt ) ; return ; } function reverseChain ( index ) { chains [ index ] . reverse ( ) ; } function appendChain ( index1 , index2 ) { const chain1 = chains [ index1 ] ; const chain2 = chains [ index2 ] ; let tail = chain1 [ chain1 . length - 1 ] ; const tail2 = chain1 [ chain1 . length - 2 ] ; const head = chain2 [ 0 ] ; const head2 = chain2 [ 1 ] ; if ( Point . colinear ( tail2 , tail , head ) ) { chain1 . pop ( ) ; tail = tail2 ; } if ( Point . colinear ( tail , head , head2 ) ) { chain2 . shift ( ) ; } chains [ index1 ] = chain1 . concat ( chain2 ) ; chains . splice ( index2 , 1 ) ; } const F = firstMatch . index ; const S = secondMatch . index ; const reverseF = chains [ F ] . length < chains [ S ] . length ; if ( firstMatch . matchesHead ) { if ( secondMatch . matchesHead ) { if ( reverseF ) { reverseChain ( F ) ; appendChain ( F , S ) ; } else { reverseChain ( S ) ; appendChain ( S , F ) ; } } else { appendChain ( S , F ) ; } } else { if ( secondMatch . matchesHead ) { appendChain ( F , S ) ; } else { if ( reverseF ) { reverseChain ( F ) ; appendChain ( S , F ) ; } else { reverseChain ( S ) ; appendChain ( F , S ) ; } } } } ) ; return regions ; } function select ( segments , selection ) { const result = [ ] ; for ( const seg of segments ) { const index = ( seg . myFill . above ? 8 : 0 ) + ( seg . myFill . below ? 4 : 0 ) + ( ( seg . otherFill && seg . otherFill . above ) ? 2 : 0 ) + ( ( seg . otherFill && seg . otherFill . below ) ? 1 : 0 ) ; if ( selection [ index ] !== 0 ) { result . push ( { start : seg . start , end : seg . end , myFill : { above : selection [ index ] === 1 , below : selection [ index ] === 2 } } ) ; } } return result ; } function segments ( poly ) { const root = new LinkedList < Event > ( ) ; for ( const region of poly ) { for ( let i = 0 ; i < region . length ; i ++ ) { const pt1 = i ? region [ i - 1 ] : last ( region ) ; const pt2 = region [ i ] ; const forward = pointsCompare ( pt1 , pt2 ) ; if ( forward === 0 ) continue ; const start = forward < 0 ? pt1 : pt2 ; const end = forward < 0 ? pt2 : pt1 ; addSegment ( root , { start , end , myFill : { } } , true ) ; } } return calculate ( root , true ) ; } function operate ( poly1 , poly2 , selection ) { const root = new LinkedList < Event > ( ) ; for ( const s of segments ( poly1 ) ) addSegment ( root , copy ( s . start , s . end , s ) , true ) ; for ( const s of segments ( poly2 ) ) addSegment ( root , copy ( s . start , s . end , s ) , false ) ; const results = select ( calculate ( root , false ) , selection ) ; return segmentChainer ( results ) ; } type MultiPolygon = Point [ ] [ ] ; const UNION = [ 0 , 2 , 1 , 0 , 2 , 2 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 ] ; const INTERSECT = [ 0 , 0 , 0 , 0 , 0 , 2 , 0 , 2 , 0 , 0 , 1 , 1 , 0 , 2 , 1 , 0 ] ; const DIFFERENCE = [ 0 , 0 , 0 , 0 , 2 , 0 , 2 , 0 , 1 , 1 , 0 , 0 , 0 , 1 , 2 , 0 ] ; const XOR = [ 0 , 2 , 1 , 0 , 2 , 0 , 0 , 1 , 1 , 0 , 0 , 2 , 0 , 1 , 2 , 0 ] ; export const union = ( p1 , p2 ) => operate ( p1 , p2 , UNION ) ; export const intersect = ( p1 , p2 ) => operate ( p1 , p2 , INTERSECT ) ; export const difference = ( p1 , p2 ) => operate ( p1 , p2 , DIFFERENCE ) ; export const xor = ( p1 , p2 ) => operate ( p1 , p2 , XOR ) ;