JTS CBS Kütüphanesi Rehberi 5 - Quadtree Nedir? Java'da Örnek Kullanım

Her düğümünün (node) 4 adet çocuğu (child) olan ağaç (tree) veri yapısına quadtree denir. Genellikle 2 boyutlu bir yüzeyi 4 eşit alana bölmek için kullanılır. Bu bölümler de yinelemeli olarak 4 er eşit parçaya ayrılır. Bu şekilde her bir alan quadtree yapısında tutulur.

 

Quadtree

Java'da quadtree örneği görselleştirmesini JTS (Java Topology Suite) kütüphanesinde bulunan Quadtree sınıfı ile yapacağız. 

Öncelikle 100 adet rastgele nokta türünde geometri tanımlayalım. Bu noktaları tanımladığımız Quadtree nesnesine ekleyeceğiz. 

quadTree.insert(Envelope itemEnv, Object item);

insert metodu ile verdiğimiz "item" nesnesi Envlope (zarf, kapsam) ile tanımlanan konuma indekslenir. Daha sonra belli bir arama / tarama dikdörtgeni kullanarak quadtree nesnesinde bu alana denk gelen itemler sorgulanır.

quadTree.query(Envelope searchEnv);

query() metodunun Java dokümanında query metodunun döndüğü sonuçlar arasında searchEnv arama alanında olmayan nesnelerin de dönülebileceği belirtilmiş. Yani false positive sonuçlar da dönülebilmektedir. JTS geliştiricileri, sevimsiz bir şekilde, bu false positive sorgu sonuçlarını elemek sorumluluğunu kullanıcıya bırakmışlar. Bu nedenle dönen sorgu sonuçlarını bir kez de tarama poligonuyla kesiştirip, kesişmeyenleri sonuç listesinden sileceğiz. query()'yi kullanmayıp direk poligon ile kesişim hesaplamamamızın sebebi, query metodu ile tree içindeki yüksek sayıdaki nesnelerin çoğunu eleyerek daha az sayıda nesnede kesişim hesaplamamızı sağlaması, bu sayede performans kazancı sağlamasıdır.

Görselleştirme amacıyla, quadTree'ye eklediğimiz tüm noktaları ekrana çizdireceğiz. Arama tarama dikdörgenimizi ve query sorgusundan dönen noktaları, false positive sonuçları temizlemiş bir şekilde, kırmızı renge boyayacağız. Dışarda kalan noktaları maviye boyayacağız.

   

     GeometryFactory geometryFactory = new GeometryFactory();

                Random randomX = new Random(System.currentTimeMillis());
               
                Random randomY = new Random(System.currentTimeMillis() + 100);
               
                List<Coordinate> noktaKoordinatlari = new ArrayList<>();

                int noktaSayisi = 100;
               
                Point[] noktalar = new Point[noktaSayisi];

                Quadtree quadTree = new Quadtree();
               
                for(int i = 1; i <= noktaSayisi; i++) {
                   
                    int xRandomlySelected = randomX.nextInt(250) + 65;
                   
                    int yRandomlySelected = randomY.nextInt(250) + 50;
                   
                    Coordinate coordinate = new Coordinate(xRandomlySelected, yRandomlySelected);
                   
                    noktaKoordinatlari.add(coordinate);
               
                    noktalar[i-1] = geometryFactory.createPoint(coordinate);
                   
                    quadTree.insert(noktalar[i-1].getEnvelopeInternal(), noktalar[i-1]);
                   
                }
               
                Coordinate[] coordinates = new Coordinate[] { new Coordinate(150, 60), new Coordinate(250, 60),  new Coordinate(250, 250),new Coordinate(150, 250), new Coordinate(150, 60)};
               
                Polygon cercevePoligon = geometryFactory.createPolygon(coordinates);
               
                List<Object> cerceveOlasiKapsananNoktalar = quadTree.query(cercevePoligon.getEnvelopeInternal());
               
                List<Point> falsePositives = new ArrayList<>();
               
                for (Object c : cerceveOlasiKapsananNoktalar) {
                    Point p = (Point) c;
                   
                    System.out.println(p + " intersects polygon: " + cercevePoligon.intersects(p) + " envlope " + p.getEnvelopeInternal());
                   
                    if(!cercevePoligon.intersects(p)) {
                        falsePositives.add(p);
                    }
                }
               
                cerceveOlasiKapsananNoktalar.removeAll(falsePositives);

JTS Quadtree Visualisation

Github'daki örnek JTS eğitim projemizdeki QuadtreeGorsellestirme.java sınıfını çalıştırarak görselleştirebilirsiniz.

 Önceki bölümler:

1.  JTS CBS Kütüphanesi Rehberi  1 - Geometri Modeli
2.  JTS CBS Kütüphanesi Rehberi  2 - Geometrik İlişki Hesaplamaları 
3.  JTS CBS Kütüphanesi Rehberi  3 - Geometrik Alan Hesaplamaları
4.  JTS CBS Kütüphanesi Rehberi 4 - Delaunay Üçgenleme, Voronoi Diyagram, Convex Hull 

Sonraki Bölümler:

JTS CBS Kütüphanesi Rehberi  6 - Douglas Peucker Geometri Basitleştirme ve Yoğunlaştırma 

Download as E-book PDF