OPENER-next / OpenStop

App for collecting OpenStreetMap-compliant accessibility data in public transport
https://openstop.app
GNU General Public License v3.0
65 stars 13 forks source link

Spatial marker filtering #87

Closed Robbendebiene closed 1 year ago

Robbendebiene commented 1 year ago

This PR implements spatial marker filtering.

Note: currently due to performance reasons this uses a clustering algorithm under the hood. However this sometimes leads to imperfect results (for example some space where an additional marker would fit).

This currently does not include any marker importance weighting.


In the future this may be replaced by a custom algorithm that works like this:

  1. Use rbush to store/add/delete markers
  2. Get all markers from rbush with padded viewport bbox
  3. (Optional) Sort by marker importance
  4. Calculate projection offset(x, y)
  5. Calculate (radial) collision, see following pseudo code:

  for (final marker in markers) {
    if (_containsCollision(marker, _nonColliding)) {
      _colliding.add(marker);
    }
    else {
      _nonColliding.add(marker);
    }
  }

  bool _containsCollision(Circle circle, Iterable<Circles> circles) {
    for (final comparisonCircle in circles) {
      if (_collides(circle, comparisonCircle)) {
        return true;
      }
    }
    return false;
  }

  bool _collides(Circle circleA, Circle circleB) {
    final collisionDistance = pow(circleA.radius + circleB.radius, 2);
    final distanceSquared = (circleB.center - circleA.center).distanceSquared;
    return distanceSquared < collisionDistance;
  }