package Ġxyz . y gg dr azil . mid gard . math . fort une Ċ Ċ import Ġxyz . y gg dr azil . mid gard . math . geometry . Point Ċ Ċ class ĠHalf edge ( edge : ĠEdge ?, Ġlr : ĠLR ?) Ġ{ ĊĠĠĠ Ġvar Ġedge List Left Neighbor : ĠHalf edge ? Ġ= Ġnull ĊĠĠĠ Ġvar Ġedge List Right Neighbor : ĠHalf edge ? Ġ= Ġnull ĊĠĠĠ Ġvar Ġnext In Priority Queue : ĠHalf edge ? Ġ= Ġnull ĊĠĠĠ Ġvar Ġedge : ĠEdge ? Ġ= Ġnull ĊĠĠĠ Ġvar Ġleft Right : ĠLR ? Ġ= Ġnull ĊĠĠĠ Ġvar Ġvertex : ĠVertex ? Ġ= Ġnull ĊĠĠĠ Ġ// Ġthe Ġvertex 's Ġy - coordinate Ġin Ġthe Ġtransformed ĠVor on oi Ġspace ĠV * ĊĠĠĠ Ġvar Ġy star : ĠDouble Ġ= Ġ 0 . toDouble () ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġinit ( edge , Ġlr ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġinit ( edge : ĠEdge ?, Ġlr : ĠLR ?): ĠHalf edge Ġ{ ĊĠĠĠĠĠĠĠ Ġthis . edge Ġ= Ġedge ĊĠĠĠĠĠĠĠ Ġleft Right Ġ= Ġlr ĊĠĠĠĠĠĠĠ Ġnext In Priority Queue Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġvertex Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġreturn Ġthis ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ" Half edge Ġ( left Right : Ġ$ left Right ; Ġvertex : Ġ$ vertex )" ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġdispose () Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( edge List Left Neighbor Ġ!= Ġnull Ġ|| Ġedge List Right Neighbor Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstill Ġin ĠEdge List ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( next In Priority Queue Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstill Ġin ĠPriority Queue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġedge Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġleft Right Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġvertex Ġ= Ġnull ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġis Left Of ( p : ĠPoint ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġtop Site : ĠSite ĊĠĠĠĠĠĠĠ Ġval Ġright Of Site : ĠBoolean ĊĠĠĠĠĠĠĠ Ġvar Ġabove : ĠBoolean ĊĠĠĠĠĠĠĠ Ġvar Ġfast : ĠBoolean ĊĠĠĠĠĠĠĠ Ġval Ġdx p : ĠDouble ĊĠĠĠĠĠĠĠ Ġval Ġd yp : ĠDouble ĊĠĠĠĠĠĠĠ Ġval Ġd xs : ĠDouble ĊĠĠĠĠĠĠĠ Ġval Ġt 1 : ĠDouble ĊĠĠĠĠĠĠĠ Ġval Ġt 2 : ĠDouble ĊĠĠĠĠĠĠĠ Ġval Ġt 3 : ĠDouble ĊĠĠĠĠĠĠĠ Ġval Ġy l : ĠDouble ĊĊĠĠĠĠĠĠĠ Ġtop Site Ġ= Ġedge !!. right Site ĊĠĠĠĠĠĠĠ Ġright Of Site Ġ= Ġp . x Ġ> Ġtop Site ._ x ĊĠĠĠĠĠĠĠ Ġif Ġ( right Of Site Ġ&& Ġthis . left Right Ġ== ĠLR . LEFT ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ(! right Of Site Ġ&& Ġthis . left Right Ġ== ĠLR . RIGHT ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( edge !!. a Ġ== Ġ 1 . 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd yp Ġ= Ġp . y Ġ- Ġtop Site ._ y ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdx p Ġ= Ġp . x Ġ- Ġtop Site ._ x ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfast Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! right Of Site Ġ&& Ġedge !!. b Ġ< Ġ 0 . 0 Ġ|| Ġright Of Site Ġ&& Ġedge !!. b Ġ>= Ġ 0 . 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġabove Ġ= Ġd yp Ġ>= Ġedge !!. b Ġ* Ġdx p ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfast Ġ= Ġabove ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġabove Ġ= Ġp . x Ġ+ Ġp . y Ġ* Ġedge !!. b Ġ> Ġedge !!. c ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( edge !!. b Ġ< Ġ 0 . 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġabove Ġ= Ġ! above ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! above ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfast Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! fast ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd xs Ġ= Ġtop Site ._ x Ġ- Ġedge !!. left Site ._ x ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġabove Ġ= Ġedge !!. b Ġ* Ġ( dx p Ġ* Ġdx p Ġ- Ġd yp Ġ* Ġd yp ) Ġ< Ġd xs Ġ* Ġd yp Ġ* Ġ( 1 . 0 Ġ+ Ġ 2 . 0 Ġ* Ġdx p Ġ/ Ġd xs Ġ+ Ġedge !!. b Ġ* Ġedge !!. b ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( edge !!. b Ġ< Ġ 0 . 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġabove Ġ= Ġ! above ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse ĊĠĠĠĠĠĠĠ Ġ/* Ġedge . b Ġ== Ġ 1 . 0 Ġ*/ Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy l Ġ= Ġedge !!. c Ġ- Ġedge !!. a Ġ* Ġp . x ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt 1 Ġ= Ġp . y Ġ- Ġy l ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt 2 Ġ= Ġp . x Ġ- Ġtop Site ._ x ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt 3 Ġ= Ġy l Ġ- Ġtop Site ._ y ĊĠĠĠĠĠĠĠĠĠĠĠ Ġabove Ġ= Ġt 1 Ġ* Ġt 1 Ġ> Ġt 2 Ġ* Ġt 2 Ġ+ Ġt 3 Ġ* Ġt 3 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġthis . left Right Ġ== ĠLR . LEFT Ġ== Ġabove ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĊĠĠĠĠĠĠĠ Ġfun Ġcreate Dummy (): ĠHalf edge Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠHalf edge ( null , Ġnull ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ