Introduction to ray method

In map applications, we often need to determine whether a point is located within a polygon area. Here is an introduction to how to achieve this using the ray method.

Algorithm idea: Draw a line from the point to be judged in a certain direction, and calculate the number of intersection points with the polygon. If the number is an even number or 0, the point is outside the polygon. If it is an odd number, it is inside the polygon, as shown below: There are two situations here that require special handling:

• 1) The ray passes through the vertex: When the ray passes through the vertex, abnormal conditions will occur.
• 2) The point is on the edge: In this case, the parity of the number of intersection points cannot be used to judge. It is necessary to quickly determine whether the point is on the edge:

Use `{lat, lng}` objects and at least three vertices. Closing the ring explicitly is optional; boundaries count as inside. This planar algorithm is not a global spherical or antimeridian polygon test. `GeoUtils` is an application namespace; declare `const GeoUtils = {};` for standalone use. ```javascript GeoUtils.isPointInPolygon = (point, polygon) => { const valid = p => p && Number.isFinite(p.lat) && Number.isFinite(p.lng); if (!valid(point) || !Array.isArray(polygon) || polygon.length < 3 || !polygon.every(valid)) return false;

const epsilon = 1e-10; // Coordinate-unit tolerance; tune for your data scale. let inside = false; for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) { const a = polygon[j], b = polygon[i]; const dx = b.lng - a.lng, dy = b.lat - a.lat; const length = Math.hypot(dx, dy); if (length <= epsilon) { if (Math.hypot(point.lng - a.lng, point.lat - a.lat) <= epsilon) return true; continue; } const cross = (point.lng - a.lng) * dy - (point.lat - a.lat) * dx; if (Math.abs(cross) <= epsilon * length && point.lng >= Math.min(a.lng, b.lng) - epsilon && point.lng <= Math.max(a.lng, b.lng) + epsilon && point.lat >= Math.min(a.lat, b.lat) - epsilon && point.lat <= Math.max(a.lat, b.lat) + epsilon) return true;

// A half-open crossing rule avoids counting a shared vertex twice.
if ((a.lat > point.lat) !== (b.lat > point.lat)) {
  const crossingLng = a.lng + (point.lat - a.lat) * dx / dy;
  if (point.lng < crossingLng) inside = !inside;
}

} return inside; };

[参考文献](http://paulbourke.net/geometry/)