mmd-osm / overpass-api Goto Github PK

diff --git a/src/overpass_api/core/type_area.h b/src/overpass_api/core/type_area.h
index a57f29a..453e0a9 100644
--- a/src/overpass_api/core/type_area.h
+++ b/src/overpass_api/core/type_area.h
@@ -313,6 +313,8 @@ struct Area_Block
   Id_Type id;
   std::vector< uint64 > coors;
 
+  std::vector< std::pair< uint32, int32 > > ilat_ilon_pairs;
+
   Area_Block() : id(0u) {}
 
   Area_Block(void* data) : id(*(Id_Type*)data)
diff --git a/src/overpass_api/statements/area_query.cc b/src/overpass_api/statements/area_query.cc
index cd10022..90ca17f 100644
--- a/src/overpass_api/statements/area_query.cc
+++ b/src/overpass_api/statements/area_query.cc
@@ -35,6 +35,109 @@
 #include "recurse.h"
 
 
+
+namespace area_query {
+
+namespace detail {
+
+const static int HIT = 1;
+const static int TOGGLE_EAST = 2;
+const static int TOGGLE_WEST = 4;
+
+int check_area_block2
+(uint32 ll_index_ilat, int32 ll_index_ilon, const Area_Block& area_block,
+    uint32 coord_lat, int32 coord_lon)
+{
+  int state = 0;
+
+  auto it(area_block.ilat_ilon_pairs.begin());
+  uint32 lat = ll_index_ilat | it->first;                             // avoid ::ilat / ::ilon 
+  int32 lon = ll_index_ilon | it->second;                        // avoid ::ilat / ::ilon
+
+  while (++it != area_block.ilat_ilon_pairs.end())
+  {
+    uint32 last_lat = lat;
+    int32 last_lon = lon;
+
+    lat = ll_index_ilat | it->first;
+    lon = ll_index_ilon | it->second;
+
+    if (last_lon < lon)
+    {
+      if (lon < coord_lon)
+        continue; // case (1)
+      else if (last_lon > coord_lon)
+        continue; // case (1)
+      else if (lon == coord_lon)
+      {
+        if (lat < coord_lat)
+          state ^= TOGGLE_WEST; // case (4)
+        else if (lat == coord_lat)
+          return HIT; // case (2)
+        // else: case (1)
+        continue;
+      }
+      else if (last_lon == coord_lon)
+      {
+        if (last_lat < coord_lat)
+          state ^= TOGGLE_EAST; // case (4)
+        else if (last_lat == coord_lat)
+          return HIT; // case (2)
+        // else: case (1)
+        continue;
+      }
+    }
+    else if (last_lon > lon)
+    {
+      if (lon > coord_lon)
+        continue; // case (1)
+      else if (last_lon < coord_lon)
+        continue; // case (1)
+      else if (lon == coord_lon)
+      {
+        if (lat < coord_lat)
+          state ^= TOGGLE_EAST; // case (4)
+        else if (lat == coord_lat)
+          return HIT; // case (2)
+        // else: case (1)
+        continue;
+      }
+      else if (last_lon == coord_lon)
+      {
+        if (last_lat < coord_lat)
+          state ^= TOGGLE_WEST; // case (4)
+        else if (last_lat == coord_lat)
+          return HIT; // case (2)
+        // else: case (1)
+        continue;
+      }
+    }
+    else // last_lon == lon
+    {
+      if (lon == coord_lon &&
+          ((last_lat <= coord_lat && coord_lat <= lat) || (lat <= coord_lat && coord_lat <= last_lat)))
+        return HIT; // case (2)
+      continue; // else: case (1)
+    }
+
+    uint32 intersect_lat = lat +
+        ((int64)coord_lon - lon)*((int64)last_lat - lat)/((int64)last_lon - lon);
+    if (coord_lat > intersect_lat)
+      state ^= (TOGGLE_EAST | TOGGLE_WEST); // case (3)
+    else if (coord_lat == intersect_lat)
+      return HIT; // case (2)
+    // else: case (1)
+  }
+  return state;
+}
+
+
+}
+
+}
+
+
+
 class Area_Constraint : public Query_Constraint
 {
   public:
@@ -441,6 +544,10 @@ void Area_Query_Statement::collect_nodes
 
   uint32 loop_count = 0;
   uint32 current_idx(0);
+
+  uint32 current_idx_ilat(0);
+  int32 current_idx_ilon(0);
+
   while (!(area_it == area_blocks_db.discrete_end()))
   {
     current_idx = area_it.index().val();
@@ -459,6 +566,23 @@ void Area_Query_Statement::collect_nodes
       ++area_it;
     }
 
+    /* Test: Precalculate ilat/ilon pairs */
+    {
+      for (auto &it : areas)
+        for (auto& it2 : it.second)
+          for (auto coor : it2.coors)
+          {
+            uint32 _lat = ::ilat((coor>>32)&0xff, coor & 0xffffffff);
+            int32 _lon = ::ilon(((coor>>32)&0xff) ^ 0x40000000, coor & 0xffffffff); 
+            it2.ilat_ilon_pairs.push_back(std::make_pair(_lat, _lon));
+          }
+      current_idx_ilat = ::ilat(current_idx, 0);
+      current_idx_ilon = ::ilon(current_idx, 0);   // ^ 0x40000000 is only being applies once here
+    }
+
+    /* ------------------------------ */
+
+
     while (nodes_it != nodes.end() && nodes_it->first.val() < current_idx)
     {
       nodes_it->second.clear();
@@ -475,6 +599,7 @@ void Area_Query_Statement::collect_nodes
             + 91.0)*10000000+0.5);
         int32 ilon(::lon(nodes_it->first.val(), iit->ll_lower)*10000000
             + (::lon(nodes_it->first.val(), iit->ll_lower) > 0 ? 0.5 : -0.5));
+
         for (std::map< Area_Skeleton::Id_Type, std::vector< Area_Block > >::const_iterator it = areas.begin();
 	     it != areas.end(); ++it)
         {
@@ -484,7 +609,8 @@ void Area_Query_Statement::collect_nodes
           {
             ++loop_count;
 
-	    int check(Coord_Query_Statement::check_area_block(current_idx, *it2, ilat, ilon));
+	    int check(area_query::detail::check_area_block2(current_idx_ilat, current_idx_ilon, *it2, ilat, ilon));
+	    //int check(Coord_Query_Statement::check_area_block(current_idx, *it2, ilat, ilon));
 	    if (check == Coord_Query_Statement::HIT && add_border)
 	    {
 	      inside = 1;
@@ -494,10 +620,10 @@ void Area_Query_Statement::collect_nodes
 	      inside ^= check;
           }
           if (inside)
-	  {
-	    into.push_back(*iit);
-	    break;
-	  }
+          {
+            into.push_back(*iit);
+            break;
+          }
         }
       }
       nodes_it->second.swap(into);
@@ -679,6 +805,7 @@ void has_inner_points(const Area_Block& string_a, const Area_Block& string_b, in
     uint32 ilat = (coords_a[i].first + coords_a[i+1].first)/2;
     uint32 ilon = (coords_a[i].second + coords_a[i+1].second)/2 + 0x80000000u;
     int check = Coord_Query_Statement::check_area_block(0, string_b, ilat, ilon);
+
     if (check & Coord_Query_Statement::HIT)
       inside = check;
     else if (check)
@@ -708,6 +835,18 @@ void Area_Query_Statement::collect_ways
       add_way_to_area_blocks(way_geometries.get_geometry(*it2), it2->id.val(), way_segments);
   }
 
+  /* Test: Populate ilat/ilon pairs */
+  {
+    for (auto &it : way_segments)
+      for (auto& it2 : it.second)
+        for (auto coor : it2.coors)
+        {
+          uint32 _lat = ::ilat((coor>>32)&0xff, coor & 0xffffffff);
+          int32 _lon = ::ilon(((coor>>32)&0xff) ^ 0x40000000, coor & 0xffffffff);
+          it2.ilat_ilon_pairs.push_back(std::make_pair(_lat, _lon));
+        }
+  }
+
   std::map< uint32, std::vector< std::pair< uint32, Way::Id_Type > > > way_coords_to_id;
   for (typename std::map< Uint31_Index, std::vector< Way_Skeleton > >::iterator it = ways.begin(); it != ways.end(); ++it)
   {
@@ -724,6 +863,9 @@ void Area_Query_Statement::collect_ways
   // Fill node_status with the area related status of each node and segment
   uint32 loop_count = 0;
   uint32 current_idx(0);
+  uint32 current_idx_ilat(0);
+  int32 current_idx_ilon(0);
+
   while (!(area_it == area_blocks_db.discrete_end()))
   {
     current_idx = area_it.index().val();
@@ -742,6 +884,20 @@ void Area_Query_Statement::collect_ways
       ++area_it;
     }
 
+    /* Test: Populate ilat/ilon pairs */
+    {
+      for (auto &it : areas)
+        for (auto& it2 : it.second)
+          for (auto coor : it2.coors)
+          {
+            uint32 _lat = ::ilat((coor>>32)&0xff, coor & 0xffffffff);
+            int32 _lon = ::ilon(((coor>>32)&0xff) ^ 0x40000000, coor & 0xffffffff);
+            it2.ilat_ilon_pairs.push_back(std::make_pair(_lat, _lon));
+          }
+      current_idx_ilat = ::ilat(current_idx, 0);
+      current_idx_ilon = ::ilon(current_idx, 0);
+    }
+
     // check nodes
     while (nodes_it != way_coords_to_id.end() && nodes_it->first < current_idx)
       ++nodes_it;
@@ -763,7 +919,8 @@ void Area_Query_Statement::collect_ways
           {
             ++loop_count;
 
-	    int check(Coord_Query_Statement::check_area_block(current_idx, *it2, ilat, ilon));
+	    // int check(Coord_Query_Statement::check_area_block(current_idx, *it2, ilat, ilon));
+	    int check(area_query::detail::check_area_block2(current_idx_ilat, current_idx_ilon, *it2, ilat, ilon));
 	    if (check == Coord_Query_Statement::HIT)
             {
               inside = Coord_Query_Statement::HIT;