最近有根据一堆离散的报警数据（内部包含经纬度 报警类型）需要聚合出每个报警发生的区域需求，比如 超速报警 聚集点有哪些，疲劳驾驶报警有哪些等等，个人没有采用已成型的算法 比如DBSCAN，而是自己实现

思路

为了让聚合的区域更精确，以及聚合的区域过大，我们采取了如下措施

1、限制聚合距离

何为限制聚合距离呢，就是定位点与定位点间 或定位点与多边形区域之间设置距离限制，如果点与点 或点与多边形距离小于设置阈值，则点加入该区域，否则成都一个独立区域？

2、绘制多边形区域

为了避免区域内非聚集空白区过多，我们取消了圆形区域，决定基于聚集的点形成多边形区域

3、多边形区域之间合并

为什么多边形区域之间需要合并呢，随着区域的增多，可能一个点同时与多个多边形区域距离符合阈值需要加入，那此时，对应的多边形就需要合并在一起组成新的区域

4、多边形定边点

组成多边形我们就使用定位数据点，并按顺序存入，最后前端根据定位点顺序绘制出多边形（A>B>C） 那么前端就会基于 A>B B>C C>A 绘制出一个三角形区域

报警模型

/*** @author lei* @create 2023-02-27 15:51* @desc**/
@Data
@NoArgsConstructor
@AllArgsConstructor
public class Alarm {private Integer vehicleId;@ApiModelProperty("经度")private Integer longitude;@ApiModelProperty("纬度")private Integer latitude;private String pointName;private Integer alarmType;public Alarm(Integer vehicleId, Integer longitude, Integer latitude, String pointName) {this.vehicleId = vehicleId;this.longitude = longitude;this.latitude = latitude;this.pointName = pointName;}
}

4、逻辑流程

基于当前定位点循环当前所有的多边形区域，与区域元素进行判断，满足则加入（contine区域列表并记录已有区域）并与剩下区域列表中区域依次比对，不满足则新建区域，已有满足区域但还有匹配区域则两个区域进行合并

    private static boolean collectCalc(List<PolygonMapArea> polygonMapAreas, Alarm curAlarm, Double collectDistance) {// 是否需要初始化新多边形boolean needInitNewPolygon = true;PolygonMapArea belongedArea = null;MapPoint curPoint = new MapPoint(curAlarm.getLongitude(), curAlarm.getLatitude(), curAlarm.getPointName());for (PolygonMapArea polygonMapArea : polygonMapAreas) {if (!polygonMapArea.isLive()) {continue;}// 先算圆心到当前点距离是否超过指定阈值,超过则进行下一个多边形判断double distance = AreaUtil.distance(polygonMapArea.getCycleCenter(), curPoint);if (distance > polygonMapArea.getRadius() + collectDistance) {continue;}if (polygonMapArea.getPoints().getSize() == 1) {needInitNewPolygon = false;if (belongedArea == null) {// 归属当前聚集点，计算最大经纬度与圆心polygonMapArea.getAlarms().add(curAlarm);polygonDrawCircle(curPoint, polygonMapArea, distance);polygonMapArea.setBelong(true);belongedArea = polygonMapArea;} else {mergePolygonArea(belongedArea, polygonMapArea, collectDistance);}continue;}// 属于当前多边形扫描圆距离,则进行多边形内外部判断boolean inPolygonArea = AreaUtil.locateInPolygonArea(curPoint, polygonMapArea);if (inPolygonArea) {// 当前点在现多边形内needInitNewPolygon = false;if (belongedArea == null) {polygonMapArea.getAlarms().add(curAlarm);polygonMapArea.setBelong(true);belongedArea = polygonMapArea;} else {mergePolygonArea(belongedArea, polygonMapArea, collectDistance);}continue;}// 当前点在多边形之外,则与各边进行判断,找到与其相邻最近边,如距离小于指定阈值则加入多边形Pair<Pair<Node<MapPoint>, Node<MapPoint>>, Double> nearestEdge = getNearestEdge(curPoint, polygonMapArea.getPoints());if (nearestEdge == null) {log.warn("当前点:{}未找到最近边", curAlarm);continue;}Pair<Node<MapPoint>, Node<MapPoint>> nearestNode = nearestEdge.getKey();double nearestEdgeDistance = nearestEdge.getValue();if (nearestEdgeDistance <= collectDistance) {needInitNewPolygon = false;if (belongedArea == null) {polygonMapArea.getAlarms().add(curAlarm);if (nearestEdgeDistance > AreaUtil.ON_LINE_DISTANCE) {// 加入多边形并削内凹角tryRecalculationArea(polygonMapArea, nearestNode.getKey(), nearestNode.getValue(), curPoint);}polygonMapArea.setBelong(true);belongedArea = polygonMapArea;} else {mergePolygonArea(belongedArea, polygonMapArea, collectDistance);}}}return needInitNewPolygon;}

一些性能上的优化

1、多边形设置圆心

多边形圆心是由 多边形定边点数据中洗出来的 （最大经度，最大纬度） （最小经度最小纬度） 获取出的中心点

当判断点是否加入多边形时 先与圆心距离判断 （点与圆心点距离小于等于 圆半径+聚合距离是着可能需要加入，如大于着必不可能加入该多边形）

2、采用分支合并思路

区域列表循环采用分支合并思路，基于当前机器核心线程数拆分现有区域列表，异步计算最后合并汇总数据

 /*** 获取对应报警类型计算线程池** @param alarm* @return ThreadPoolExecutor* @author lei* @date 2023-03-27 11:06:57*/private static ThreadPoolExecutor getCalcExecutor(Alarm alarm) {return ALARM_TYPE_EXECUTOR_MAP.computeIfAbsent(alarm.getAlarmType(), alarmType -> {alarmType = Optional.ofNullable(alarmType).orElse(0);ThreadPoolExecutor executor = new ThreadPoolExecutor(CORE, CORE, 10, TimeUnit.MINUTES,new ArrayBlockingQueue<>(1024), new ThreadFactoryBuilder().setNameFormat(alarmType + "-calc-%d").setUncaughtExceptionHandler((t, e) -> log.error("线程:{}处理异常", t.getName(), e)).build(), new ThreadPoolExecutor.CallerRunsPolicy());log.debug("初始化报警类型:{}计算线程池!", alarmType);return executor;});}/*** 加入多边形计算** @param polygonMapAreas 现有聚集区* @param curAlarm        当前报警* @param collectDistance 聚集距离* @param calcIncr        累计计算量* @param incrId* @return void* @author lei* @date 2023-03-08 11:24:30*/private static void forkJoinPolygonArea(List<PolygonMapArea> polygonMapAreas, Alarm curAlarm, Double collectDistance,AtomicLong calcIncr, AtomicLong incrId) {long calcNum = calcIncr.incrementAndGet();if (CollUtil.isEmpty(polygonMapAreas)) {initPolygonArea(curAlarm, polygonMapAreas, incrId);return;}boolean needInitNewPolygon;List<List<PolygonMapArea>> splitAreaList = splitPolygonArea(polygonMapAreas);int splitAreaSize = splitAreaList.size();if (splitAreaSize > 1) {// 与各个子分支区域列表计算ThreadPoolExecutor calcExecutor = getCalcExecutor(curAlarm);List<CompletableFuture<Boolean>> collect = splitAreaList.stream().map(areas ->CompletableFuture.supplyAsync(() -> collectCalc(areas, curAlarm, collectDistance), calcExecutor)).collect(toList());List<Boolean> forkResultList = collect.stream().map(CompletableFuture::join).collect(toList());// 分支结果全真为真,非全真则再次合并needInitNewPolygon = splitAreaSize == forkResultList.stream().filter(x -> x).count();if (!needInitNewPolygon) {forkMergePolygonArea(polygonMapAreas, collectDistance);}} else {needInitNewPolygon = collectCalc(polygonMapAreas, curAlarm, collectDistance);}if (needInitNewPolygon) {initPolygonArea(curAlarm, polygonMapAreas, incrId);}// 清理较为离散的区域cleanDispersedArea(polygonMapAreas, calcNum);}/*** 合并线程子分支区域计算结果** @return List<PolygonMapArea> 返回分支合并后的区域列表,此时的区域列表为当前定位点计算后的最新结果* @author lei* @date 2023-03-27 15:46:26*/private static void forkMergePolygonArea(List<PolygonMapArea> polygonMapAreas, Double collectDistance) {PolygonMapArea belongArea = null;for (PolygonMapArea polygonMapArea : polygonMapAreas) {if (polygonMapArea.isBelong() && polygonMapArea.isLive()) {if (belongArea == null) {belongArea = polygonMapArea;} else {mergePolygonArea(belongArea, polygonMapArea, collectDistance);}}}}

3、清理聚集较分散区域

我们采取了定量清理区域逻辑思路，比如计算了20000个定位点清理一部分区域（区域一个点），区域数量达到10000个时清理区域内小于三个点的数据

合理性处理

1、解决多边形内凹角问题

由于每个定位点都有可能成为组成多边形区域的点，故此有可能组成的多边形是弯弯曲曲的畸形，比如像手，像魔爪等等，不是一个外凸的多边形

我们期望减少内凹角，使其成为一个更加饱满的多边形区域，比如下图

使用jts依赖库

 compile 'org.locationtech.jts:jts-core:1.19.0'

核心思路是拿需消除内凹角的多边形所有定边点，使用jts依赖库绘制图形然后获取凸包，然后过滤出多边形定边点 不在凸包列表的数据

// 转换多边形定边点数据
Coordinate[] coordinates = points.getList().stream().map(x -> {Coordinate coordinate = new Coordinate(x.getLongitude(), x.getLatitude());return coordinate;}).toArray(Coordinate[]::new);
// 计算凸包
ConvexHull convexHull = new ConvexHull(coordinates, new GeometryFactory());
Geometry geometry = convexHull.getConvexHull();
Set<Coordinate> after = Arrays.stream(geometry.getCoordinates()).collect(Collectors.toSet());
// 踢出多边形定边点中不在Set集合中的数据

2、解决定边点插入位置问题

当新的定位点时要成为组成多边形定边点的时候会面临一个问题，这个点要插入哪里呢（插入顺序）？因为一旦位置选错了后，绘制成的多边形地图就会交叉

比如下图的多边形

先分析上图问题产生原因

1、最开始 是 2 3 4组成三角区域，5点到来时，需要先判断该点与多边形哪一边更近（答案很显然，与 3 4 更近）于是加入了 3 后 成为新多边形 2 3 5 4

6点到来，则需要与多边形 2 3 5 4判断最近边，但此时其与 3 5 54 边距离是相等的，由于我逻辑的不完整性，选错了边，选了3 5 边，绘制最终多边形 2 3 6 5 4，导致多边形交叉

如何解决选错边的问题？如何选择插入的边？

思考了很久，我们可以将要插入的点与最近两个边夹角大小来判断，即上图的 3 5 6 与 4 5 6两个夹角的大小来判断，插入夹角较小的那一边。

35 54 一个最近边的结束 也是另一个最近边的开始

但还特别需要注意的是 多边形的组成顺序并不一定都是我上图的 2 3 5…这样顺时针（多边形从右边开始绘制）组成的，也可能多边形是逆时针绘制组成出来的（多边形从左边开始生成绘制）

抛除6点，我们假设上图多边形是从左边绘制的，并且 6点不是与 35 54最近，而是与 24 32 最近，那么此时会发现，相邻的两个边，一个最近边的结束不是另一个最近边的开始 这个时候我们夹角度数就要修改为 4 2 6 与 3 2 6，这样计算夹角才对

那么我们如何确定顺时针与逆时针呢？我们只需要判断第二个最近边的开始是不是第一边的结束即可

    /*** 根据当前点 获取与当前多边形最近边** @param curPoint 当前点* @param points   当前多边形组合点* @return Pair<Pair < Node < MapPoint>,Node<MapPoint>>,Double> 最近边组成点 当前点与最近边距离* @author lei* @date 2023-03-02 15:45:18*/private static Pair<Pair<Node<MapPoint>, Node<MapPoint>>, Double> getNearestEdge(MapPoint curPoint, LinkList<MapPoint> points) {Node<MapPoint> foreachNode = points.getFirst();Double nearestEdgeDistance = null;List<Pair<Pair<Node<MapPoint>, Node<MapPoint>>, Double>> pairList = new ArrayList<>();for (int i = 0; i < points.getSize(); i++) {Node<MapPoint> endPoint = foreachNode.getNext();double curDistance = AreaUtil.pointToLine(foreachNode.getData(), endPoint.getData(), curPoint);if (nearestEdgeDistance == null || nearestEdgeDistance >= curDistance) {nearestEdgeDistance = curDistance;Pair<Pair<Node<MapPoint>, Node<MapPoint>>, Double> nearestEdge = new Pair<>(Pair.of(foreachNode, foreachNode.getNext()), curDistance);pairList.add(nearestEdge);}foreachNode = endPoint;}Map<Double, List<Pair<Pair<Node<MapPoint>, Node<MapPoint>>, Double>>> map = pairList.stream().collect(Collectors.groupingBy(Pair::getValue));List<Pair<Pair<Node<MapPoint>, Node<MapPoint>>, Double>> nearestEdgeList = map.get(nearestEdgeDistance);// 特殊情况会出现当前点d与多边形两个边 (顺时针查找ab bc、或逆时针查找 ab ca)距离相同情况,因此做特殊处理,返回其夹角度数最小所在的那一边if (points.getSize() >= 3 && nearestEdgeList.size() == 2) {// 边1Pair<Pair<Node<MapPoint>, Node<MapPoint>>, Double> nearestEdgeOne = nearestEdgeList.get(0);Pair<Node<MapPoint>, Node<MapPoint>> edgeOne = nearestEdgeOne.getKey();Node<MapPoint> edgeOneStart = edgeOne.getKey();Node<MapPoint> edgeOneEnd = edgeOne.getValue();// 边2Pair<Pair<Node<MapPoint>, Node<MapPoint>>, Double> nearestEdgeTwo = nearestEdgeList.get(1);Pair<Node<MapPoint>, Node<MapPoint>> edgeTwo = nearestEdgeTwo.getKey();Node<MapPoint> edgeTwoStart = edgeTwo.getKey();Node<MapPoint> edgeTwoEnd = edgeTwo.getValue();double cosValue1;double cosValue2;// 顺时针相邻if (edgeTwoStart.equals(edgeOneEnd)) {// 求 边1 开始 结束 当前点组成夹角余弦 （a b d）cosValue1 = AreaUtil.cosValue(edgeOneStart.getData(), edgeOneEnd.getData(), curPoint);// 求 边2 结束 开始 当前点组成夹角余弦  (c b d)cosValue2 = AreaUtil.cosValue(edgeTwoEnd.getData(), edgeTwoStart.getData(), curPoint);} else {// a b c a// 求 边1 结束 开始 当前点组成夹角余弦 （b a d）cosValue1 = AreaUtil.cosValue(edgeOneEnd.getData(), edgeOneStart.getData(), curPoint);// 求 边2 开始 结束 当前点组成夹角余弦  (c a d)cosValue2 = AreaUtil.cosValue(edgeTwoStart.getData(), edgeTwoEnd.getData(), curPoint);}// 返回小夹角所在边,如夹角一致则交由下一步消内凹逻辑return cosValue1 >= cosValue2 ? nearestEdgeOne : nearestEdgeTwo;}return nearestEdgeList.get(0);}

3、多边形区域扩展

我们生成了某一类型报警的 N个聚集区域后，当其他车辆快要经过这里时我们怎么提前预警呢？

1、基于现在车辆定位点计算其与报警聚集区距离，小于等于阈值则报警

此方案可行，但是如果车辆速度过快（且我们的车辆定位是30s传一条）且聚集区比较小的话可能还没起到提示作用就已经过了该聚集区了

2、在原有多边形区域基础之上，向外扩展指定阈值，当车辆在记录扩展后的区域达到阈值或在进入到扩展后的区域时触发提醒

我们最终选择了方案二

那么多边形区域如何扩展呢？

使用jts依赖库

 compile 'org.locationtech.jts:jts-core:1.19.0'

我们将原多边形区域定边点使用jts依赖库组成几何图形，并设置外扩，我们拿到外扩后的几何图形凸包即可

/*** 多边形区域扩展** @param points         定位点* @param extendDistance 外扩距离 m* @return List<MapPoint>* @author lei* @date 2023-03-21 16:19:30*/
public static List<MapPoint> extendPoints(List<MapPoint> points, double extendDistance) {List<MapPoint> extendsPoints = points;if (extendDistance > 1 && points.size() >= NEED_EXTEND_SIZE) {Coordinate[] coordinates = points.stream().map(point -> new Coordinate(point.getLongitude(), point.getLatitude())).toArray(Coordinate[]::new);ConvexHull convexHull = new ConvexHull(coordinates, new GeometryFactory());Geometry polygon = convexHull.getConvexHull();// 每个圆弧的线段数,值越夹角越平滑,int quadrantSegments = 1;// 端点类型int endCapStyle = BufferParameters.CAP_SQUARE;// 连接类型int joinStyle = BufferParameters.JOIN_MITRE;// 指定斜接连接的斜率限制 当两个线段夹角很小时,斜接点锐角非常尖锐; 避免锐化可限制斜接点的斜率,当斜率超过指定阈值将强使用JOIN_BEVELdouble mitreLimit = 5.0;BufferParameters bufferParams = new BufferParameters(quadrantSegments, endCapStyle, joinStyle, mitreLimit);bufferParams.setSingleSided(true);// 向外扩展区域Geometry expandedPolygon = BufferOp.bufferOp(polygon, extendDistance * 10, bufferParams);Coordinate[] extendArray = expandedPolygon.convexHull().getCoordinates();extendsPoints = Arrays.stream(extendArray).map(x -> new MapPoint((int) x.x, (int) x.y)).distinct().collect(Collectors.toList());}return extendsPoints;
}

成果展示