Laboratorium 8 - województwa, powiaty, gminy, miejscowości (kontynuacja)

Napisz docelową klasę BoundingBox. Jest to prostokąt otaczający jednostkę. Do zdefiniowania prostokąta wystarczą dwa przeciwległe punkty, zamiast pięciu.

Zaprojektuj BoundingBox tak, aby miał dwa stany:

• BoundingBox może być pusty
• albo definiuje prostokąt (w tym zdegenerowany do pojedynczego punktu)

Sam(a) zadecyduj, jak je odróżnić, np. stosując specjalne wartości Double.NaN albo dodając flagę pusty/niepusty.

public class BoundingBox {
    double xmin = ???;
    double ymin = ???;
    double xmax = ???;
    double ymax = ???;
 
    /**
     * Powiększa BB tak, aby zawierał punkt (x,y) 
     * @param x - współrzędna x
     * @param y - współrzędna y
     */
    void addPoint(double x, double y){
 
    }
 
    /**
     * Sprawdza, czy BB zawiera punkt (x,y)
     * @param x
     * @param y
     * @return
     */
    boolean contains(double x, double y){
        return false;
    }
 
    /**
     * Sprawdza czy dany BB zawiera bb 
     * @param bb
     * @return
     */
    boolean contains(BoundingBox bb){
        return false;
    }
 
    /**
     * Sprawdza, czy dany BB przecina się z bb
     * @param bb
     * @return
     */
    boolean intersects(BoundingBox bb){
        return false;
    }
    /**
     * Powiększa rozmiary tak, aby zawierał bb oraz poprzednią wersję this
     * @param bb
     * @return
     */
    BoundingBox add(BoundingBox bb){
        return this;
    }
    /**
     * Sprawdza czy BB jest pusty
     * @return
     */
    boolean isEmpty(){
        return true;
    }
 
    /**
     * Oblicza i zwraca współrzędną x środka
     * @return if !isEmpty() współrzędna x środka else wyrzuca wyjątek
     * (sam dobierz typ)
     */
    double getCenterX(){
        throw new RuntimeException("Not implemented");
    }
    /**
     * Oblicza i zwraca współrzędną y środka
     * @return if !isEmpty() współrzędna y środka else wyrzuca wyjątek
     * (sam dobierz typ)
     */
    double getCenterY(){
        throw new RuntimeException("Not implemented");
    }
 
    /**
     * Oblicza odległość pomiędzy środkami this bounding box oraz bbx
     * @param bbx prostokąt, do którego liczona jest odległość
     * @return if !isEmpty odległość, else wyrzuca wyjątek lub zwraca maksymalną możliwą wartość double
     * Ze względu na to, że są to współrzędne geograficzne, zamiast odległosci euklidesowej możesz użyć wzoru haversine
     * (ang. haversine formula)
     */
    double distanceTo(BoundingBox bbx){
        throw new RuntimeException("Not implemented");
    }
 
}

• Uzupełnij wartości BoundingBox podczas odczytu.
• Dodaj w klasie BoundingBox metodę toString() i uwzględnij jej wywołanie w AdminUnit.toString()
• Sprawdź, czy wartości współrzędnych czytane są poprawnie

Podczas czytania rekordów wydrukuj

System.out.printf(Locale.US,"LINESTRING(%f %f, %f %f, %f %f, %f %f,%f %f)", 
reader.getDouble("x1"),
reader.getDouble("y1"),
reader.getDouble("x2"),
reader.getDouble("y2"),
reader.getDouble("x3"),
reader.getDouble("y3"),
reader.getDouble("x4"),
reader.getDouble("y4"),
reader.getDouble("x5"),
reader.getDouble("y5")
);

Np. dla Krakowa będzie to

LINESTRING(19.7922353426102 49.9676667885393,19.7922353426102 50.1261382575516,20.2173454438402 50.1261382575516,20.2173454438402 49.9676667885393,19.7922353426102 49.9676667885393)

Skopiuj wynik i wklej na stronie http://arthur-e.github.io/Wicket/sandbox-gmaps3.html

Oczywiście możesz też wypisać odpowiedni tekst na podstawie współrzędnych w BoundingBox, a nawet dodać metodę, która to robi do klasy. Metoda np. może nazywać się getWKT() - WKT (Well Known Text) to format reprezentacji wektorów https://en.wikipedia.org/wiki/Well-known_text.

Zdefiniujmy wpierw pojęcie sąsiada. W typowym przypadku sąsiadem danej jednostki ma być jednostka

• na tym samym poziomie hierarchii (czyli sąsiadami województw mają być województwa, powiatów – powiaty, gmin – gminy, a miejscowości - leżące w pobliżu miejscowości
• podstawowym kryterium (dla województw, powiatów i gmin) ma być pokrywanie się BoundingBox testowane za pomocą metody intersects()

Miejscowości mogą być oddalone i ich granice nie będą się pokrywały. Stąd kryterium pokrywania nie wystarczy. Przyjmiemy więc, że sąsiadujące miejscowości położone są w odległości mniejszej niż pewien konfigurowalny parametr maxdistance, np. równy 15 km. Odległości mają być liczone od środków BoundingBox

Napisz funkcję klasy AdminUnitList

   /**
     * Zwraca listę jednostek sąsiadujących z jendostką unit na tym samym poziomie hierarchii admin_level. 
     * Czyli sąsiadami wojweództw są województwa, powiatów - powiaty, gmin - gminy, miejscowości - inne miejscowości
     * @param unit - jednostka, której sąsiedzi mają być wyznaczeni
     * @param maxdistance - parametr stosowany wyłącznie dla miejscowości, maksymalny promień odległości od środka unit, 
     *                    w którym mają sie znaleźć punkty środkowe BoundingBox sąsiadów
     * @return lista wypełniona sąsiadami
     */
    AdminUnitList getNeighbors(AdminUnit unit, double maxdistance){
        throw new RuntimeException("Not implemented");
    }

Zademonstruj w kodzie (np. testach), że jesteś w stanie:

• znaleźć wybraną jednostkę na danym poziomie hierarchii
• wyznaczyć i wypisać listę sąsiadów
• sprawdź wyniki na mapie…

Oblicz czas wyszukiwania sąsiadów

        double t1 = System.nanoTime()/1e6;
        // wywołanie funkcji
        double t2 = System.nanoTime()/1e6;
        System.out.printf(Locale.US,"t2-t1=%f\n",t2-t1);

Najprostsza metoda realizacji algorytmu wyszukiwania sąsiadów polega na iteracji przez wszystkie elementy listy i sprawdzenie, czy są sąsiadami (zgodnie ze zdefiniowanymi kryteriami). Gdybyśmy chcieli wyznaczyć sąsiadów dla wszystkich obiektów AdminUnit złożoność obliczeniowa będzie O(n^2). Biorąc pod uwagę, że n~15000, da to 22500000 testów sąsiedztwa, czyli raczej dużo…

Dysponujemy jednak hierarchią obiektów (parent→children) - potencjalnie drzewem z nieistniejącym korzeniem, którego potomkami są województwa, dalej powiaty i gminy. Jeżeli z niej skorzystamy - pozwoli to nam zapewne przyspieszyć obliczenia.

Zaimplementuj algorytm wyszukiwania dla R-tree opisany w Wikipedii (sekcja Search). Dla województwa, powiatu lub gminy użyj zdefiniowanego BoundingBox. Dla miejscowości - po prostu rozszerz środek o maxdistance w każdym kierunku (ale zastosuj kryterium odległości). Porównaj czasy wykonania dla wersji liniowej i wykorzystującej drzewo parent→children.