package Ġalgorithms inan ut shell . spatial tree Ċ Ċ import Ġalgorithms inan ut shell . Point Ċ Ċ /** Ċ Ġ* Ġhttps :// al gs 4 . cs . pr inc et on . edu / 9 2 search / Quad Tree . java . html Ċ Ġ* Ċ Ġ* Ġhttps :// www . youtube . com / watch ? v = j xb DY xm - pX g Ċ Ġ* Ċ Ġ* Ġhttps :// www . youtube . com / watch ? v = xF c Qa ig 5 Z 2 A Ċ Ġ*/ Ċ class ĠQuad Tree Ġ{ ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠQuad Node Ġconsists Ġof Ġa Ġvalue Ġand Ġ 4 Ġquadr ants . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠĠĠĠĠĠĠĠĠ Ġ| Ġ Ġsw Ġ Ġ| Ġ Ġse Ġ Ġ| Ġ Ġnw Ġ Ġ| Ġ Ġne Ġ Ġ| ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġinner Ġclass ĠQuad Node ( ĊĠĠĠĠĠĠĠ Ġval Ġvalue : ĠInt , Ġval Ġpoint : ĠPoint ĊĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġsw : ĠQuad Node ? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġvar Ġse : ĠQuad Node ? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġvar Ġnw : ĠQuad Node ? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġvar Ġne : ĠQuad Node ? Ġ= Ġnull ĊĊĠĠĠĠĠĠĠ Ġval Ġx : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġget () Ġ= Ġpoint . x ĊĊĊĠĠĠĠĠĠĠ Ġval Ġy : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġget () Ġ= Ġpoint . y ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ" Quad Node ($ value , Ġsw =$ sw , Ġse =$ se , Ġnw =$ nw , Ġne =$ ne )" ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġvar Ġroot : ĠQuad Node ? Ġ= Ġnull ĊĊĠĠĠ Ġfun Ġinsert ( x : ĠInt , Ġy : ĠInt , Ġvalue : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval ĠnewNode Ġ= ĠQuad Node ( value , Ġpoint Ġ= ĠPoint ( x , Ġy )) ĊĠĠĠĠĠĠĠ Ġroot Ġ= Ġinsert ( root , ĠnewNode ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġinsert ( parent : ĠQuad Node ?, Ġnode : ĠQuad Node ): ĠQuad Node Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( parent Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnode ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( node . x Ġ< Ġparent . x Ġ&& Ġnode . y Ġ< Ġparent . y ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġparent . sw Ġ= Ġinsert ( parent . sw , Ġnode ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( node . x Ġ< Ġparent . x Ġ&& Ġnode . y Ġ> Ġparent . y ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġparent . nw Ġ= Ġinsert ( parent . nw , Ġnode ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( node . x Ġ> Ġparent . x Ġ&& Ġnode . y Ġ< Ġparent . y ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġparent . se Ġ= Ġinsert ( parent . se , Ġnode ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( node . x Ġ> Ġparent . x Ġ&& Ġnode . y Ġ> Ġparent . y ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġparent . ne Ġ= Ġinsert ( parent . ne , Ġnode ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġparent ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ" Quad Tree ($ root )" ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGiven Ġa Ġrectangle Ġwith Ġ([ xmin ], Ġ[ ymin ]) Ġand Ġ([ xmax ], Ġ[ ymax ]), Ġfind Ġthe Ġpoints Ġinside Ġit . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġrange Query ( xmin : ĠInt , Ġymin : ĠInt , Ġxmax : ĠInt , Ġymax : ĠInt ): ĠList < Quad Node > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= Ġmutable ListOf < Quad Node >() ĊĠĠĠĠĠĠĠ Ġrange Query ( root !! , Ġxmin , Ġymin , Ġxmax , Ġymax , Ġresult ) ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġrange Query ( root : ĠQuad Node ?, Ġxmin : ĠInt , Ġymin : ĠInt , Ġxmax : ĠInt , Ġymax : ĠInt , Ġresult : ĠMutable List < Quad Node >) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( root . x Ġin Ġxmin .. xmax Ġ&& Ġroot . y Ġin Ġymin .. ymax ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( root ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( root . x Ġ> Ġxmin Ġ&& Ġroot . y Ġ> Ġymin ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrange Query ( root . sw , Ġxmin , Ġymin , Ġxmax , Ġymax , Ġresult ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( root . x Ġ> Ġxmin Ġ&& Ġroot . y Ġ< Ġymax ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrange Query ( root . nw , Ġxmin , Ġymin , Ġxmax , Ġymax , Ġresult ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( root . x Ġ< Ġxmax Ġ&& Ġroot . y Ġ> Ġymin ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrange Query ( root . se , Ġxmin , Ġymin , Ġxmax , Ġymax , Ġresult ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( root . x Ġ< Ġxmax Ġ&& Ġroot . y Ġ< Ġymax ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrange Query ( root . ne , Ġxmin , Ġymin , Ġxmax , Ġymax , Ġresult ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġval Ġtree Ġ= ĠQuad Tree () ĊĠĠĠ Ġtree . insert ( 1 0 , Ġ 1 0 , Ġ 1 0 1 0 ) ĊĠĠĠ Ġtree . insert ( 1 1 , Ġ 1 1 , Ġ 1 1 1 1 ) ĊĠĠĠ Ġtree . insert ( 5 , Ġ 5 , Ġ 5 5 ) ĊĠĠĠ Ġtree . insert ( 3 , Ġ 3 , Ġ 3 3 ) ĊĠĠĠ Ġtree . insert ( 2 , Ġ 2 , Ġ 2 2 ) ĊĠĠĠ Ġtree . insert ( 4 , Ġ 4 , Ġ 4 3 ) ĊĠĠĠ Ġprintln ( tree ) ĊĠĠĠ Ġtree . range Query ( 1 , Ġ 1 , Ġ 6 , Ġ 6 ). forEach Ġ{ Ġprintln ( it ) Ġ} Ċ }