顺丰04. 顺丰中转场车辆入场识别-电子围栏

【背景】
物流站点的王经理需要对进出站点的物流车辆进行管理，王经理需要通过车载定位知道某物流车辆是否在某个划定的区域内，如果物流车辆超出指定的区域，系统会自动发送提醒信息给王经理，王经理可以通过提醒信息来监管具体情况。
【问题】
几何计算简化如下：
点（x，y） 为车辆所在坐标点，coords[x1,y1,x2,y2,x3,y3,x4,x4,….,x1,y1]为连续封闭区域坐标点。
现给定连续封闭坐标点的一维数组coords[n]和车辆坐标(x,y)，
返回车辆是否在封闭区域coords内（点在多边形边界线上算在区域内）。
【示例】
image.png
输入： x = 1, y = 3, coords = [0,0,0,4,4,4,2,2,4,0,0,0] 输出：true
提示

  • 0 < coords.length < 1000
  • 0 < coords[i] < 10000.0
  • 0 < x < 10000.0
  • 0 < y < 10000.0
  • 点在多边形边界线上算在区域内

思路：
射线法
固定向一个方向的射线，一般为x轴负方向
若点(x, y)穿过多边形的次数为奇数次，说明(x, y)在多边形内，否则在多边形外
注意以下特殊情况
image.png
即：对于一条从(x1, y1)到(x2, y2)的边

  1. 若y1 == y2, continue，平行边跳过，因为交点无穷
  2. 若y > max(y1, y2) || y <= min(y1, y2), continue，经过两条边的交点只计算一种重合

问题1：如何判断(x, y)是否在(x1, y1), (x2, y2)表示的线段上？
叉乘 + 点乘
(x1 - x) * (y2 - y) - (y1 - y) * (x2 - x) == 0 && (x1 - x) * (y1 - y) + (x2 - x) * (y2 - y) <= 0

问题2：如何判断(x, y)沿x轴负方向的射线经过(x1, y1), (x2, y2)表示的线段？
见代码

  1. class Solution {
  2.     final double eps = 1e-6;
  3.     public boolean isPointInPolygon(double x, double y, double[] c) {
  4.         int n = c.length;
  5.         int cnt = 0;
  6.         for (int i = 0; i < n - 3; i += 2) {
  7.             double x1 = c[i], y1 = c[i + 1], x2 = c[i + 2], y2 = c[i + 3];
  9.             if (onLine(x, y, x1, y1, x2, y2)) {
  10.                 return false;
  11.             }
  12.             if (cross(x, y, x1, y1, x2, y2)) {
  13.                 cnt ^= 1;
  14.             }
  15.         }
  17.         return cnt == 1;
  18.     }
  20.     boolean onLine(double x, double y, double x1, double y1, double x2, double y2) {
  21.         return (x1 - x) * (y2 - y) - (x2 - x) * (y1 - y) == 0 && (x1 - x) * (x2 - x) + (y1 - y) * (y2 - y) <= 0;
  22.     }
  24.     boolean cross(double x, double y, double x1, double y1, double x2, double y2) {
  25.         if (y1 == y2) return false;
  26.         if (y < Math.min(y1, y2)) return false;;
  27.         if (y >= Math.max(y1, y2)) return false;
  29.         if (x1 == x2) return x1 <= x;
  30.         double k = (y1 - y2) / (x1 - x2), b = y1 - k * x1;
  31.         return (y - b) / k < x;
  32.     }
  34. }