Research on usage of google::s2

[CodeBear801]

We plan to experience to use google::s2 to build spatial index for charge stations. For more context, please go to: #231

The target we want to achieve is:

• For given charge stations, we pre-calculate all charge stations in certain route distance(such as 600km), the result should be sorted based on distance
  • The first step should be build spatial index for all charge station points
  • For given charge station position, could retrieve all nearby charge stations based on great circle distance
  • Calculate route distance between given charge station and all reachable charge stations, sort result by distance.

[CodeBear801]

My notes about Google S2

• Google S2 general: https://github.com/CodeBear801/tech_summary/blob/master/tech-summary/navigation/spatial_index/google_s2.md
• Google S2 basic types: https://github.com/CodeBear801/tech_summary/blob/master/tech-summary/navigation/spatial_index/google_s2_basic_types.md
• Google S2 Cell definition: https://github.com/CodeBear801/tech_summary/blob/master/tech-summary/navigation/spatial_index/google_s2_cell.md

[CodeBear801]

Draft logic(based on C++):

• Loading charge station data(stationid : string, location: lat, lon)
• Construct S2PointIndex for charge stations

  S2PointIndex<int> index;
  for (int i = 0; i < num_index_points; ++i) 
  {
    index.Add(station_point, i);
  }

• Dump result to file(Encode?), so next time could build this quicker(optional)
• For each charge station point

// Create a query to search within the given radius of a target point.
S2ClosestPointQuery<int> query(&index);
query.mutable_options()->set_max_distance(
      S1Angle::Radians(S2Earth::KmToRadians(FLAGS_query_radius_km)));  // 600km
for (int i = 0; i < num_index_points; ++i) 
{
    S2ClosestPointQuery<int>::PointTarget target(station_point);
    result = query.FindClosestPoints(&target)
    dump_result_2_json
}

• Implementation of S2ClosestPointQueryBase

template <class Distance, class Data>
inline std::vector<typename S2ClosestPointQueryBase<Distance, Data>::Result>
S2ClosestPointQueryBase<Distance, Data>::FindClosestPoints(
    Target* target, const Options& options) {
  std::vector<Result> results;
  FindClosestPoints(target, options, &results);
  return results;
}

[CodeBear801]

The go version didn't implement FindClosestPoints, so my plan is using C++ for part of work:

• Stage 1, C++, finding nearest charge stations for each charge station in great circle distance. Result record in json format?

  • The code still put into integration, it will use compiling env of osrm docker and also put dependencies there such as google/s2geometry, create separate cmake file for this one.
  • Why not GO: It implements about 40% of all C++ features: https://github.com/golang/geo, not including PointIndex and ClosestPointQuery

• Stage 2, Go, take stage 1's output as input, using OSRM to calculate shortest path distance between each charge station-> other charge stations, sort them based on distance and dump result to json

  • The reason to use go is due to I already implement a wrapper for OSRM

• Write logic to load this file and generate a hash map, which could answer queries like:

  • give one point, retrieve nearby stations
  • give one station, retrieve all reachable stations based on some filter(distance_of_avoid_distance, max_distance_could_reach)

[CodeBear801]

Before start C++ version, will investigate whether could make it work all use GO code.

Original Draft Estimation (03182020)

• First build ShapeIndex for each station points
• Second, iterate all cell id cover each station point, build reverse index map, like <cellid, all charge stations> // need confirm
• Third, check how to answer <circle, cellids> query

Detail Analysis with Go-geo (03192020)

Cell operation

• How to get cell id for given point

c := CellFromLatLng(LatLngFromDegrees(test.lat, test.lng))

• CellFromLatLng returns the leaf cell, how to get all the parenets

// code from go/geo/cellid.go
// Level returns the subdivision level of this cell ID, in the range [0, maxLevel].
func (ci CellID) Level() int {
	return maxLevel - findLSBSetNonZero64(uint64(ci))>>1
}

// Parent returns the cell at the given level, which must be no greater than the current level.
func (ci CellID) Parent(level int) CellID {
	lsb := lsbForLevel(level)
	return CellID((uint64(ci) & -lsb) | lsb)
}

Will write code as

    currLevel := c.Level()
    for i := currLevel; i <= pre_defined_maxLevel;  --i {
            cellid = c.Parent(i)
            dict[ceillid] = // append station id into slice
   }

Covering operation

// code from go/geo
// Covering returns a CellUnion that covers the given region and satisfies the various restrictions.
func (rc *RegionCoverer) Covering(region Region) CellUnion {
	covering := rc.CellUnion(region)
	covering.Denormalize(maxInt(0, minInt(maxLevel, rc.MinLevel)), maxInt(1, minInt(3, rc.LevelMod)))
	return covering
}

Will write code like

rc := &s2.RegionCoverer{MaxLevel: 30, MaxCells: 500}
r := s2.Region(CapFromCenterArea(center, area))
covering := rc.Covering(r)

[wangyoucao577]

The go version didn't implement FindClosestPoints, so my plan is using C++ for part of work:

• Stage 1, C++, finding nearest charge stations for each charge station in great circle distance. Result record in json format?

  • The code still put into integration, it will use compiling env of osrm docker and also put dependencies there such as google/s2geometry, create separate cmake file for this one.
  • Why not GO: It implements about 40% of all C++ features: https://github.com/golang/geo, not including PointIndex and ClosestPointQuery

• Stage 2, Go, take stage 1's output as input, using OSRM to calculate shortest path distance between each charge station-> other charge stations, sort them based on distance and dump result to json

  • The reason to use go is due to I already implement a wrapper for OSRM

• Write logic to load this file and generate a hash map, which could answer queries like:

  • give one point, retrieve nearby stations
  • give one station, retrieve all reachable stations based on some filter(distance_of_avoid_distance, max_distance_could_reach)

If new C++ binary is necessary, I'll suggest to use integration/cpp as its root folder, i.e. put its C++/cmake codes in. The dependency can be installed into osrm-backend-dev if necessary. The build process can be added in dockefile of osrm-backend as a separate step.

[CodeBear801]

The go version didn't implement FindClosestPoints, so my plan is using C++ for part of work:

• Stage 1, C++, finding nearest charge stations for each charge station in great circle distance. Result record in json format?

  • The code still put into integration, it will use compiling env of osrm docker and also put dependencies there such as google/s2geometry, create separate cmake file for this one.
  • Why not GO: It implements about 40% of all C++ features: https://github.com/golang/geo, not including PointIndex and ClosestPointQuery

• Stage 2, Go, take stage 1's output as input, using OSRM to calculate shortest path distance between each charge station-> other charge stations, sort them based on distance and dump result to json

  • The reason to use go is due to I already implement a wrapper for OSRM

• Write logic to load this file and generate a hash map, which could answer queries like:

  • give one point, retrieve nearby stations
  • give one station, retrieve all reachable stations based on some filter(distance_of_avoid_distance, max_distance_could_reach)

If new C++ binary is necessary, I'll suggest to use integration/cpp as its root folder, i.e. put its C++/cmake codes in. The dependency can be installed into osrm-backend-dev if necessary. The build process can be added in dockefile of osrm-backend as a separate step.

Agree. Thanks for the suggestion.

[CodeBear801]

Play with https://github.com/google/s2geometry

openssl

brew install open ssl

// go to the folder you want to build
cmake -DOPENSSL_ROOT_DIR=/usr/local/Cellar/openssl/1.0.2s -DOPENSSL_LIBRARIES=/usr/local/Cellar/openssl/1.0.2s/lib ..
make

[CodeBear801]

Experiment on S2 Unit Tests

Center is Great America Pkwy, radius as 1600 meters

Center is Great America Pkwy, radius as 500km

Max cell = 500

For compare, result for Max cell = 50