Geosearch critiques/questions

[jessekrubin]

The idea of a super fast all jawascript/interfacescript geo search is super appealling, BUT it has a few oddities and seems rough around the edges (I work in geo-spatial number crunching btw). Let me know if I am missing anything and/or you are handling the points below, but I could not see anything when grepping around. I was able to load a relatively small dataset into orama

• Storing points in an orama db with {lon: number, lat: number} is ok, but searching with polygons should be done with standardized format(s) GeoJSON and/or wkt/wkb. Converting my data to a custom polygon format for the polygon search is a pain. https://datatracker.ietf.org/doc/html/rfc7946
• The polygon search doesn't seem to sanity check for bad polygons
• The point in polygon doesn't quick check for point outside of polygon envelope

function isPointInTriangle(triangle: [Point, Point, Point],  point: Point): boolean {
  const [p0, p1, p2] = triangle;
  const d1 = (point.lon - p1.lon) * (p0.lat - p1.lat) - (p0.lon - p1.lon) * (point.lat - p1.lat);
  const d2 = (point.lon - p2.lon) * (p1.lat - p2.lat) - (p1.lon - p2.lon) * (point.lat - p2.lat);
  const d3 = (point.lon - p0.lon) * (p2.lat - p0.lat) - (p2.lon - p0.lon) * (point.lat - p0.lat);
  const has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
  const has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
  return !(has_neg && has_pos);
}

function isPointInPolygon(polygon: Point[], point: Point): boolean {
  const x = point.lon
  const y = point.lat
  const polygonLength = polygon.length
  const lons = polygon.map((p) => p.lon)
  const lats = polygon.map((p) => p.lat)
  const lonMin = Math.min(...lons)
  const lonMax = Math.max(...lons)
  const latMin = Math.min(...lats)
  const latMax = Math.max(...lats)
  // outside of bbox... DOES NOT HANDLE ANTIMERIDIAN
  if  (x < lonMin || x > lonMax || y < latMin || y > latMax) {
    return false
  }

  // assuming first and last points are the same (like in a proper polygon)
  // use point in triangle instead of point in polygon if
  // the polygon is a triangle (3 points - 4 coordinates - first and last are the same)
  if (polygonLength === 4) {
    return isPointInTriangle([polygon[0], polygon[1], polygon[2]], point)
  }

  let isInside = false
  for (let i = 0, j = polygonLength - 1; i < polygonLength; j = i++) {
    const xi = polygon[i].lon
    const yi = polygon[i].lat
    const xj = polygon[j].lon
    const yj = polygon[j].lat

    const intersect = yi > y !== yj > y && x < ((xj - xi) * (y - yi)) / (yj - yi) + xi
    if (intersect) isInside = !isInside
  }

  return isInside
}

PS: great work in general!

[micheleriva]

Hi @jessekrubin,
thank you so much for opening this. I agree 100% with what you said, and we should improve with Orama 2.0.

Geosearch was first released with Orama v2.0.0-beta.1, so the API * might * be subject to change.

I'd kindly ask you to open an issue for this, so we can keep track of this discussion a bit better and implement some enhancements.

If you're then willing to open a PR, that's even better :)

[jessekrubin]

@micheleriva I can make it an issue or issues. What do you see as the most pressing? Is there a reason you are not using something like turfjs (which is highly optimized)?

should geo search be something that is more of a plugin to orama as opposed to baked in?