package Ġcom . a 6 5 apps . clustering . core . algorithm Ċ Ċ import Ġcom . a 6 5 apps . clustering . core .* Ċ import Ġcom . a 6 5 apps . clustering . core . geometry . Bounds Ċ import Ġcom . a 6 5 apps . clustering . core . geometry . Point Ċ import Ġcom . a 6 5 apps . clustering . core . projection . S pherical M erc ator Projection Ċ import Ġcom . a 6 5 apps . clustering . core . quad tree . Point Quad Tree Ċ import Ġkotlin . math . sqrt Ċ Ċ val ĠPRO JECTION Ġ= ĠS pherical M erc ator Projection ( 1 . 0 ) Ċ private Ġconst Ġval ĠDEFAULT _ RATIO _ FOR _ CLUSTER ING Ġ= Ġ 0 . 5 f Ċ Ċ /** Ċ Ġ* ĠA Ġsimple Ġclustering Ġalgorithm Ġwith ĠO ( n log Ġn ) Ġperformance . ĠResult ing Ġclusters Ġare Ġnot Ċ Ġ* Ġh ierarchical . Ċ Ġ* Ġ< p /> Ċ Ġ* ĠHigh Ġlevel Ġalgorithm :< br > Ċ Ġ* Ġ 1 . ĠIterate Ġover Ġitems Ġin Ġthe Ġorder Ġthey Ġwere Ġadded Ġ( candidate Ġclusters ). < br > Ċ Ġ* Ġ 2 . ĠCreate Ġa Ġcluster Ġwith Ġthe Ġcenter Ġof Ġthe Ġitem . Ġ< br > Ċ Ġ* Ġ 3 . ĠAdd Ġall Ġitems Ġthat Ġare Ġwithin Ġa Ġcertain Ġdistance Ġto Ġthe Ġcluster . Ġ< br > Ċ Ġ* Ġ 4 . ĠMove Ġany Ġitems Ġout Ġof Ġan Ġexisting Ġcluster Ġif Ġthey Ġare Ġcloser Ġto Ġanother Ġcluster . Ġ< br > Ċ Ġ* Ġ 5 . ĠRemove Ġthose Ġitems Ġfrom Ġthe Ġlist Ġof Ġcandidate Ġclusters . Ċ Ġ* Ġ< p /> Ċ Ġ* ĠCl usters Ġhave Ġthe Ġcenter Ġof Ġthe Ġfirst Ġelement Ġ( not Ġthe Ġcentroid Ġof Ġthe Ġitems Ġwithin Ġit ). Ċ Ġ*/ Ċ open Ġclass ĠNon Hierarchical Distance Based Algorithm ( ĊĠĠĠĠĠĠĠ Ġprivate Ġval Ġcluster Provider : ĠCluster Provider Ġ= ĠDefault Cluster Provider ()) Ġ: ĊĠĠĠĠĠĠĠ ĠAlgorithm < Default Algorithm Parameter > Ġ{ ĊĠĠĠ Ġprotected Ġvar Ġparameter : ĠDefault Algorithm Parameter ? Ġ= Ġnull ĊĠĠĠ Ġprivate Ġvar Ġratio For Cluster ing Ġ= ĠDEFAULT _ RATIO _ FOR _ CLUSTER ING ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAny Ġmodifications Ġshould Ġbe Ġsynchronized Ġon Ġm Quad Tree . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġquad Items : ĠMutable Set < Quad Item > Ġ= Ġmutable Set Of () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAny Ġmodifications Ġshould Ġbe Ġsynchronized Ġon Ġm Quad Tree . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprotected Ġval Ġquad Tree Ġ= ĠPoint Quad Tree < Quad Item >( 0 . 0 , Ġ 1 . 0 , Ġ 0 . 0 , Ġ 1 . 0 ) ĊĊĠĠĠ Ġoverride Ġfun Ġadd Item ( item : ĠCluster ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġquad Item Ġ= ĠQuad Item ( item Ġas ĠDefault Cluster ) ĊĠĠĠĠĠĠĠ Ġsynchronized ( quad Tree ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquad Items . add ( quad Item ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquad Tree . add ( quad Item ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġadd Items ( items : ĠCollection < Cluster >) Ġ= Ġitems . forEach Ġ{ Ġadd Item ( it ) Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġremove Item ( item : ĠCluster ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠQuad Item Ġdeleg ates Ġhash code () Ġand Ġequals () Ġto Ġits Ġitem Ġso , ĊĠĠĠĠĠĠĠ Ġ// ĠĠ Ġremoving Ġany ĠQuad Item Ġto Ġthat Ġitem Ġwill Ġremove Ġthe Ġitem ĊĠĠĠĠĠĠĠ Ġval Ġquad Item Ġ= ĠQuad Item ( item Ġas ĠDefault Cluster ) ĊĠĠĠĠĠĠĠ Ġsynchronized ( quad Tree ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquad Items . remove ( quad Item ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquad Tree . remove ( quad Item ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġremove Items ( items : ĠCollection < Cluster >) Ġ{ ĊĠĠĠĠĠĠĠ Ġsynchronized ( quad Tree ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġitems . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġquad Item Ġ= ĠQuad Item ( it Ġas ĠDefault Cluster ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġquad Items . remove ( quad Item ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġquad Tree . remove ( quad Item ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġclear Items () Ġ{ ĊĠĠĠĠĠĠĠ Ġsynchronized ( quad Tree ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquad Items . clear () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquad Tree . clear () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġcalculate ( parameter : ĠDefault Algorithm Parameter ): ĠSet < Cluster > Ġ{ ĊĠĠĠĠĠĠĠ Ġthis . parameter Ġ= Ġparameter ĊĠĠĠĠĠĠĠ Ġval Ġzoom Specific Span Ġ= Ġget Zoom Specific Span ( parameter . visible Rect ) ĊĠĠĠĠĠĠĠ Ġval Ġvisited Candidates Ġ= Ġmutable Set Of < Quad Item >() ĊĠĠĠĠĠĠĠ Ġval Ġresulting Quad Items Ġ= Ġmutable Set Of < Quad Item >() ĊĠĠĠĠĠĠĠ Ġval Ġdistance To Cluster Ġ= Ġmutable Map Of < Quad Item , ĠDouble >() ĊĠĠĠĠĠĠĠ Ġval Ġitem To Cluster Ġ= Ġmutable Map Of < Quad Item , ĠCluster >() ĊĠĠĠĠĠĠĠ Ġval Ġresulting Clusters Ġ= Ġmutable Set Of < Cluster >() ĊĊĠĠĠĠĠĠĠ Ġsynchronized ( quad Tree ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( candidate Ġin Ġget Cluster ing Items ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( visited Candidates . contains ( candidate )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠC andidate Ġis Ġalready Ġpart Ġof Ġanother Ġcluster . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsearch Bounds Ġ= Ġcreate Bounds From Span ( candidate . point , Ġzoom Specific Span ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcluster Items : ĠCollection < Quad Item > ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcluster Items Ġ= Ġquad Tree . search ( search Bounds ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cluster Items . size Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠOnly Ġthe Ġcurrent Ġcluster Ġis Ġin Ġrange . ĠJust Ġadd Ġthe Ġsingle Ġitem Ġto Ġthe Ġresults . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresulting Quad Items . add ( candidate ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvisited Candidates . add ( candidate ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdistance To Cluster [ candidate ] Ġ= Ġ 0 . 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcluster Ġ= Ġcluster Provider . get ( candidate . cluster ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresulting Quad Items . add ( Quad Item ( cluster )) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( cluster Item Ġin Ġcluster Items ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġexisting Distance Ġ= Ġdistance To Cluster [ cluster Item ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdistance Ġ= Ġdistance Squared ( cluster Item . point , Ġcandidate . point ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( existing Distance Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠItem Ġalready Ġbelongs Ġto Ġanother Ġcluster . ĠCheck Ġif Ġit 's Ġcloser Ġto Ġthis Ġcluster . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( existing Distance Ġ< Ġdistance ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠMove Ġitem Ġto Ġthe Ġcloser Ġcluster . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem To Cluster [ cluster Item ]?. removeItem ( cluster Item . cluster ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdistance To Cluster [ cluster Item ] Ġ= Ġdistance ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcluster . addItem ( cluster Item . cluster ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem To Cluster [ cluster Item ] Ġ= Ġcluster ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvisited Candidates . addAll ( cluster Items ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġresulting Quad Items . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( it . cluster . is Cluster ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresulting Clusters . add ( it . cluster ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresulting Clusters . addAll ( it . cluster . items ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġresulting Clusters ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprotected Ġopen Ġfun Ġget Cluster ing Items (): ĠCollection < Quad Item > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġquad Items ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġget Zoom Specific Span ( visible Rect : ĠVis ible Rect ): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġpoint 1 Ġ= ĠPRO JECTION . to Point ( visible Rect . top Left ) ĊĠĠĠĠĠĠĠ Ġval Ġpoint 2 Ġ= ĠPRO JECTION . to Point ( visible Rect . bottom Right ) ĊĠĠĠĠĠĠĠ Ġreturn Ġsqrt ( distance Squared ( point 1 , Ġpoint 2 )) Ġ* Ġratio For Cluster ing ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġset Ratio For Cluster ing ( value : ĠFloat ) Ġ{ ĊĠĠĠĠĠĠĠ Ġratio For Cluster ing Ġ= Ġvalue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġdistance Squared ( a : ĠPoint , Ġb : ĠPoint ): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ( a . x Ġ- Ġb . x ) Ġ* Ġ( a . x Ġ- Ġb . x ) Ġ+ Ġ( a . y Ġ- Ġb . y ) Ġ* Ġ( a . y Ġ- Ġb . y ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġcreate Bounds From Span ( p : ĠPoint , Ġspan : ĠDouble ): ĠBounds Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġhalf Span Ġ= Ġspan Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġreturn ĠBounds ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . x Ġ- Ġhalf Span , Ġp . x Ġ+ Ġhalf Span , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . y Ġ- Ġhalf Span , Ġp . y Ġ+ Ġhalf Span ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġclass ĠQuad Item ( val Ġcluster : ĠCluster ) Ġ: ĠPoint Quad Tree . Item Ġ{ ĊĠĠĠĠĠĠĠ Ġprivate Ġval Ġposition : ĠLat Lng Ġ= Ġcluster . geo Co or () ĊĠĠĠĠĠĠĠ Ġoverride Ġval Ġpoint : ĠPoint ĊĠĠĠĠĠĠĠĠĠĠĠ Ġget () Ġ= ĠPRO JECTION . to Point ( position ) ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠhashCode (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġcluster . hashCode () ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġequals ( other : ĠAny ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ( other Ġas ? ĠQuad Item )?. cluster ?. equals ( cluster ) Ġ?: Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ