1 // This is brl/bbas/volm/volm_geo_index2.h
2 #ifndef volm_geo_index2_h_
3 #define volm_geo_index2_h_
4 //:
5 // \file
6 // \brief A templated class to enable fast access to geographic areas and attributes
7 // Units are in lat, lon
8 //        index is a quadtree
9 //        some of the 4 children of a node may have zero as sptr which means that region is pruned (out of ROI or eliminated for some reason)
10 //        WARNING: this class assumes that the areas in question are small enough so that Euclidean distances approximate geodesic distances
11 //                 also assumes that the regions do not cross over lon = 0
12 //
13 // \author Yi Dong
14 // \date July 09, 2013
15 //
16 // \verbatim
17 //  Modifications
18 //   <none yet>
19 // \endverbatim
20 //
21 
22 #include <vbl/vbl_ref_count.h>
23 #include <vgl/vgl_polygon.h>
24 #include <vgl/vgl_box_2d.h>
25 #include "volm_tile.h"
26 #include "volm_geo_index2_node_base.h"
27 
28 
29 template <class Type>
30 class volm_geo_index2_node : public volm_geo_index2_node_base
31 {
32 public:
33   //: Default constructor
34   volm_geo_index2_node() = default;
35 
36   //: Constructor
volm_geo_index2_node(vgl_box_2d<double> const & extent,volm_geo_index2_node_sptr & parent)37   volm_geo_index2_node(vgl_box_2d<double> const& extent, volm_geo_index2_node_sptr& parent)
38   {
39     extent_ = extent;
40     parent_ = parent;
41   }
42 
volm_geo_index2_node(vgl_box_2d<double> const & extent)43   volm_geo_index2_node(vgl_box_2d<double> const& extent)
44   {
45     extent_ = extent;
46     parent_ = nullptr;
47   }
48 
49   //: Destructor
50   ~volm_geo_index2_node() override = default;
51 
52 public:
53   //: data inside current tile (for non-leaf tile, the data should be empty, i.e. the templated member should contain method that contents_.size() == 0 or contents_.empty() == true)
54   Type contents_;
55 };
56 
57 class volm_geo_index2
58 {
59 public:
60   //: construct a tree such that the give tile is the root, and the hierarchy of its children form a quadtree space partition
61   template <class Type>
62   static volm_geo_index2_node_sptr construct_tree(volm_tile t, double const& min_size);
63   template <class Type>
64   static volm_geo_index2_node_sptr construct_tree(vgl_box_2d<double> bbox, double const& min_size);
65 
66   //: construct with a polygon with possible multiple sheets, only keep the children who intersect one of the sheets of the polygon
67   template <class Type>
68   static volm_geo_index2_node_sptr construct_tree(volm_tile t, double const& min_size, vgl_polygon<double> const& poly);
69   template <class Type>
70   static volm_geo_index2_node_sptr construct_tree(vgl_box_2d<double> bbox, double const& min_size, vgl_polygon<double> const& poly);
71   template <class Type>
72   static volm_geo_index2_node_sptr construct_tree(volm_tile t, double const& min_size, vgl_polygon<float> const& poly);
73   template <class Type>
74   static volm_geo_index2_node_sptr construct_tree(vgl_box_2d<double> bbox, double const& min_size, vgl_polygon<float> const& poly);
75 
76   //: create the quadtree from text file.  Note even if a child has zero pointer, it's order in the children array remains same such that
77   //  the children have consistent clockwise geographic sequence
78   template <class Type>
79   static volm_geo_index2_node_sptr read_and_construct(std::string const& file_name, double& min_size);
80 
81   //: prune the children which do not intersect with given polygon
82   static bool prune_tree(const volm_geo_index2_node_sptr& root, vgl_polygon<float>  const& poly);
83   static bool prune_tree(const volm_geo_index2_node_sptr& root, vgl_polygon<double> const& poly);
84   //: prune the tree by utm zone
85   static bool prune_by_zone(const volm_geo_index2_node_sptr& root, unsigned utm_zone);
86 
87   //: write the bboxes of the nodes at the give depth to kml file
88   static void write_to_kml(const volm_geo_index2_node_sptr& root, unsigned depth, std::string const& file_name);
89   static void write_to_kml_node(std::ofstream& ofs, const volm_geo_index2_node_sptr& n, unsigned current_depth, unsigned depth, std::string explanation = "location");
90 
91   //: write the quadtree structure into a text file, only the tree structure and not the content on the leaf
92   static void write(const volm_geo_index2_node_sptr& root, std::string const& file_name, double const& min_size);
93 
94   //: return all leaves of the quadtree
95   static void get_leaves(const volm_geo_index2_node_sptr& root, std::vector<volm_geo_index2_node_sptr>& leaves);
96 
97   //: return all leaves that intersect with a given rectangular area
98   static void get_leaves(const volm_geo_index2_node_sptr& root, std::vector<volm_geo_index2_node_sptr>& leaves, vgl_box_2d<float>  const& area);
99   static void get_leaves(const volm_geo_index2_node_sptr& root, std::vector<volm_geo_index2_node_sptr>& leaves, vgl_box_2d<double> const& area);
100 
101   //: return all leaves that intersect with a given polygon
102   static void get_leaves(const volm_geo_index2_node_sptr& root, std::vector<volm_geo_index2_node_sptr>& leaves, vgl_polygon<float>  const& poly);
103   static void get_leaves(const volm_geo_index2_node_sptr& root, std::vector<volm_geo_index2_node_sptr>& leaves, vgl_polygon<double> const& poly);
104 
105   //: return all leaves that intersect with a line (this line is a list of points)
106   static void get_leaves(const volm_geo_index2_node_sptr& root, std::vector<volm_geo_index2_node_sptr>& leaves, std::vector<vgl_point_2d<float> > const& line);
107   static void get_leaves(const volm_geo_index2_node_sptr& root, std::vector<volm_geo_index2_node_sptr>& leaves, std::vector<vgl_point_2d<double> > const& line);
108 
109   //: return the leave that contains the given loc point
110   static void get_leaf(const volm_geo_index2_node_sptr& root, volm_geo_index2_node_sptr& leaf, vgl_point_2d<float> const& point);
111   static void get_leaf(const volm_geo_index2_node_sptr& root, volm_geo_index2_node_sptr& leaf, vgl_point_2d<double> const& point);
112 
113   //: return the depth of quadtree at level node
114   static unsigned depth(const volm_geo_index2_node_sptr& node);
115 
116 
117 
118 };
119 
120 #include <volm/volm_geo_index2_sptr.h>
121 #define VOLM_GEO_INDEX2_INSTANTIATE(T) extern "Please #include <volm/volm_geo_index2.hxx>"
122 
123 #endif // volm_geo_index2_h_
124