Efficiently searching a LARGE GeoJson file to see if it contains a point

I have a 200mb geojson file containing the speed limits of a country. In short the file has polygons that encompass different areas with each polygon having a given speed limit value.

I am creating a naviagation app that needs to query this geojson file to get the speed limit the user is in. My current approach is somwhat of a linear search so whilst working induces lag and massive peformance hits to the program.

My current implementation:

func findSpeedLimit(location: CLLocationCoordinate2D, geoJSON: GeoJSON) -> Int? {
    // Decode the GeoJSON data into a FeatureCollection object
    guard case let .featureCollection(featureCollection) = geoJSON else {
        print("Error: GeoJSON data is not a FeatureCollection")
        return nil
    }
    
    // Create a Point object from the location coordinates
    let point = Point(x: location.longitude, y: location.latitude)
    //print("Looking for speed limit at location: \(location.latitude), \(location.longitude)")
    
    // Loop through the features in the feature collection
    for (index, feature) in featureCollection.features.enumerated() {
        // Check if the feature has a geometry and properties
        guard let geometry = feature.geometry,
              let properties = feature.properties else {
            print("Feature \(index) has no geometry or properties")
            continue
        }
        
        do {
            // Check if the geometry contains the point
            if try geometry.contains(point) {
                // Check if the properties have a speedLimitZoneValue key
                if let speedLimit = properties["speedLimitZoneValue"] {
                    let speedLimitString = String(describing: speedLimit)
                    if let number = Int(speedLimitString.components(separatedBy: CharacterSet.decimalDigits.inverted).joined()) {
                        //print (number)
                        //print("Speed limit found for feature \(index): \(number) km/h")
                        return number
                    }
                    
                } else {
                    print("Feature \(index) has no 'speedLimitZoneValue' property")
                }
            } else {
                //print("Feature \(index) does not contain the point")
            }
        } catch {
            print("Error checking if geometry contains point: \(error)")
        }
    }
    
    return nil
}

I tried using a GKRtree but wasent able to get it to work in this context. Any ideas?

Answered by Jessers in 751818022

Update, communicated with the people at the geoswift library to implement the "prepared geometry" function of geos into the library.

Implementation:

  1. Map the geometry of each of your features to a PreparedGeometry by calling the new makePrepared() method, and store those values somewhere alongside the original features/properties.

  2. At each location update use one of the new contains methods on PreparedGeometry to test for containment.

https://github.com/GEOSwift/GEOSwift/pull/264

I would try the following:

  • build upfront an array of the polygons "centers" positions (and of course a polygon ID)
  • get a value of the max size of a polygon
  • then search would be to compute the distance of user location to those centers. It should be much faster than contains.
  • when distance is less than the maxSize, test if you are in the polygon. There will be just a handful of such tests

If not fast enough

  • You may order array by latitude and longitude,
  • then limit comparison to a small part of the array

I'm interested to know how it works.

You need a "spatial index".

Decide whether you want to do this in-memory or on-disk. If on-disk, look at the geospatial extensions for sqlite. (200 MB is an intermediate size. If it were 20 GB, you'd definitely want to do it on disk. For 200 MB, you need to ask what is more important, speed of lookup or startup time.)

If you want to make your own spatial index, I recommend "Foundations of Multidimensional and Metric Data Structures" by Samet. This is not a difficult case as the data is read-only, it gets much more complicated if you are modifying it.

P.S.

GKRTree is probably not a bad option. What exactly happened when you tried to use it?

Accepted Answer

Update, communicated with the people at the geoswift library to implement the "prepared geometry" function of geos into the library.

Implementation:

  1. Map the geometry of each of your features to a PreparedGeometry by calling the new makePrepared() method, and store those values somewhere alongside the original features/properties.

  2. At each location update use one of the new contains methods on PreparedGeometry to test for containment.

https://github.com/GEOSwift/GEOSwift/pull/264

Efficiently searching a LARGE GeoJson file to see if it contains a point
 
 
Q