@ubuntu:~/osm-3s-patch-version/build/bin$ /usr/bin/time -v ./o3 --db-dir=db/ < ph
encoding remark: Please enter your query and terminate it with CTRL+D.
<?xml version="1.0" encoding="UTF-8"?>
<osm version="0.6" generator="Overpass API">
<note>The data included in this document is from www.openstreetmap.org. The data is made available under ODbL.</note>
<meta osm_base=""/>
<count>
<tag k="nodes" v="0"/>
<tag k="ways" v="0"/>
<tag k="relations" v="0"/>
<tag k="areas" v="2317"/>
<tag k="total" v="2317"/>
</count>
<count>
<tag k="nodes" v="467196"/>
<tag k="ways" v="1017886"/>
<tag k="relations" v="0"/>
<tag k="areas" v="0"/>
<tag k="total" v="1485082"/>
</count>
</osm>
Command being timed: "./o3 --db-dir=db/"
User time (seconds): 204.09
System time (seconds): 0.37
Percent of CPU this job got: 100%
Elapsed (wall clock) time (h:mm:ss or m:ss): 3:24.46
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 784856
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 168840
Voluntary context switches: 1
Involuntary context switches: 259
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
@ubuntu:~/osm-3s-patch-version/build/bin$ /usr/bin/time -v ./osm3s_query --db-dir=db/ < ph
encoding remark: Please enter your query and terminate it with CTRL+D.
<?xml version="1.0" encoding="UTF-8"?>
<osm version="0.6" generator="Overpass API">
<note>The data included in this document is from www.openstreetmap.org. The data is made available under ODbL.</note>
<meta osm_base=""/>
<count>
<tag k="nodes" v="0"/>
<tag k="ways" v="0"/>
<tag k="relations" v="0"/>
<tag k="areas" v="2317"/>
<tag k="total" v="2317"/>
</count>
<count>
<tag k="nodes" v="467196"/>
<tag k="ways" v="1017886"/>
<tag k="relations" v="0"/>
<tag k="areas" v="0"/>
<tag k="total" v="1485082"/>
</count>
</osm>
Command being timed: "./osm3s_query --db-dir=db/"
User time (seconds): 55.80
System time (seconds): 0.42
Percent of CPU this job got: 100%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:56.22
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 883220
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 194466
Voluntary context switches: 1
Involuntary context switches: 75
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
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;