Typescript Geo项目，在 Web Worker中计算海量点在多边形和圆形范围内的算法

前言

开发的时候采用的是高德地图 API。

为什么不用内置的方法判断点在多边形和圆形范围内呢？ 因为点的计算量太大，并且对应的方法在高德地图的工具对象里面。没办法使用 worker 进行优化。

于是，需要手写等效的函数在 worker 中使用。

我在网上学习了一些公式并且借鉴了 Python 中的计算方法，希望可以帮到有需要的小伙伴。

经纬度是否在圆形范围内

利用了圆弧和点距离公式进行计算。该函数使用了比较常见的 Haversine 公式来计算两个经纬度之间的距离，并将距离转换为单位为米的值，再和半径进行比较。

const isPointInCircle = (
  lnglat1: {
    lat: number,
    lng: number,
  },
  lnglat2: {
    lat: number,
    lng: number,
  },
  radius: number
) => {
  const lat1 = lnglat1.lat
  const lng1 = lnglat1.lng
  const lat2 = lnglat2.lat
  const lng2 = lnglat2.lng
  const radLat1 = (lat1 * Math.PI) / 180.0;
  const radLat2 = (lat2 * Math.PI) / 180.0;
  const a = radLat1 - radLat2;
  const b = (lng1 * Math.PI) / 180.0 - (lng2 * Math.PI) / 180.0;
  let s =
    2 *
    Math.asin(
      Math.sqrt(
        Math.pow(Math.sin(a / 2), 2) +
        Math.cos(radLat1) *
        Math.cos(radLat2) *
        Math.pow(Math.sin(b / 2), 2),
      ),
    );
  s = s * 6378.137; // 地球半径
  s = Math.round(s * 10000) / 10000;
  return s * 1000 <= radius;
};

经纬度是否在多边形范围内

这个函数实现了一个判断点是否在多边形内部的算法，其思路是通过求解待判断点与多边形各条边的交点，并统计位于该点左侧的交点数量，最终根据交点数量的奇偶性来确定点是否在多边形内。

具体地，算法首先将待判断点的经纬度坐标保存到aLat和aLon中，然后遍历多边形上各个顶点，分别计算该点与相邻两个顶点所连成的边的交点（如果存在），并判断该交点是否位于该边的左侧。如果交点确实位于该边左侧，则将iSum累加1。最终，如果iSum为奇数，则待判断点位于多边形内部，反之则不在。

需要注意的是，该算法只适用于凸多边形，对于非凸多边形或其他复杂的多边形可能无法正确判断。此外，当多边形的顶点数量小于3时，该算法会直接返回false，因为三角形以下的形状不存在“内部”。

const isPtInPoly = (
  lnglat: { lng: number; lat: number },
  pointList: { lng: number; lat: number }[],
) => {
  const aLat = lnglat.lat
  const aLon = lnglat.lng
  let iSum = 0;
  const iCount = pointList.length;
  if (iCount < 3) {
    return false;
  }
  //  待判断的点(x, y) 为已知值
  const y = aLat;
  const x = aLon;
  let y2;
  let x2;
  for (let i = 0; i < iCount; i++) {
    const y1 = pointList[i].lat;
    const x1 = pointList[i].lng;
    if (i == iCount - 1) {
      y2 = pointList[0].lat;
      x2 = pointList[0].lng;
    } else {
      y2 = pointList[i + 1].lat;
      x2 = pointList[i + 1].lng;
    }
    // 当前边的 2 个端点分别为 已知值(x1, y1), (x2, y2)
    if ((y >= y1 && y < y2) || (y >= y2 && y < y1)) {
      //  y 界于 y1 和 y2 之间
      //  假设过待判断点(x, y)的水平直线和当前边的交点为(x_intersect, y_intersect)，有y_intersect = y
      // 则有（2个相似三角形，公用顶角，宽/宽 = 高/高）：|x1 - x2| / |x1 - x_intersect| = |y1 - y2| / |y1 - y|
      if (Math.abs(y1 - y2) > 0) {
        const x_intersect = x1 - ((x1 - x2) * (y1 - y)) / (y1 - y2);
        if (x_intersect < x) {
          iSum += 1;
        }
      }
    }
  }
  if (iSum % 2 != 0) {
    return true;
  } else {
    return false;
  }
};

React 中 使用 web worker

需要使用到的库

npm install --save @koale/useworker

使用 worker ,引入 isPointInCircle

import React from "react";
import { useWorker } from "@koale/useworker";

const Example = () => {
  const [sortWorker] = useWorker(isPointInCircle);

  const runSort = async () => {
    const result = await sortWorker(lnglat1,lnglat1,radius); UI
    console.log(result);
  };

  return <></>
};

感兴趣的小伙伴动手点个赞 👍 支持一下作者 🌸