js判断点是否在多边形内部 前端

js运用用射线法判断点是否在多边形内部,该法中常用水平扫描线法或垂直线法来判断一点是否在区域内。假若有一疑问点,要判斯它是否在多边形内,可从该疑问点向左引水平扫描线(即射线)。

关尔先生2021-11-29 16:02:43
![点在多边形内外.png](/img.php?20211129ccaa44686282d4f482da8a29f484e2eb.png) # 判断点是否在多边形内部 ## 射线法 [射线法](https://baike.baidu.com/item/%E5%B0%84%E7%BA%BF%E6%B3%95/22231858?fr=aladdin)。该法中常用水平扫描线法或垂直线法来判断一点是否在区域内。假若有一疑问点 `P(x0,y0)`,要判斯它是否在多边形内,可从该疑问点向左引水平扫描线(即射线)。 ## 引申 射线法 ![点在多边形内外-水平线.png](/img.php?202111292bc173ccbd5f4841c4d17cb996497f9d.png) 1. 前提:~多边形是用顺序的点坐标表示~。 2. 多边形各个边 是 线段(端点属于此边),两端点坐标已知 `A(xa,ya)` 和 `B(xb,yb)`,可以求得线段的表达式。 3. 以疑问点 `P(x0,y0)`,作一条水平线 `y=y0`, 如果 `ya ≤ y0 ≤ yb`,则水平线与线段`AB`相交,否则不相交。 4. 若相交,求交点坐标 `J(xj,yj)`, 已知`yj = y0`,则 `xj = ((y0 - ya) / (yb - ya)) * (xb - xa) + xa` a. `xj = x0` , `P` 与 `J` 重合,即 点在线上,返回 `1`,结束; b. `xj < x0` , `J` 在 `P` 左侧,则 `left++`; c. `xj < x0` , `J` 在 `P` 右侧,则 `right++`; d. 如果 `left` 和 `right` 都为奇数,则 点在多边形内,返回 `true` e. 其它 返回 `false` ## 代码下载 [isPointInRing.min.js](https://www.nanshanqiao.com/dist/isPointInRing.min.js) ## 代码使用 引入后 执行 `BJ_MAP_UTIL.isPointInRing(POINT, PATH)` `POINT` 为 检测点 `[x,y]` `PATH`是多边形点集合 `[[x1,y1],[x2,y2]...]` ## 代码精度 与高德地图 API `AMap.GeometryUtil.isPointInRing` 相比: 1. 多边形内外,判断一致 2. 多边形顶点,高德全部返回 `false`;此算法归到`点在线上`,都返回`1` 3. 多边形边上,高德部分返回 `false`,部分返回`true`;此算法归到`点在线上`,都返回`1` ## 代码速度 与高德地图 API `AMap.GeometryUtil.isPointInRing` 相比 耗时减少了近`80%` (63667 个测试点,高德耗时`21.086s`,此算法耗时`4.676s`) '单引号',"双引号",中文双引号:“”,中文单引号‘’英文逗号,

js射线法点是否在多边形内部水平扫描线法

上一篇:前端跨域:一步一步实现本地 node 代理转发请求实现跨域访问API

下一篇:根据地图经纬度绘制 canvas 电子围栏【1】

本文链接: http://www.nanshanqiao.com/zz_article/104.html

暂无评论