#

luxiaotao1123

2024-10-25 beb476733eaff1f3a76ec1be772337655803cccb

 zy-acs-manager/src/main/java/com/zy/acs/manager/core/DispatcherTestController.java

@@ -38,56 +38,206 @@
        Map<String, List<String>> adjacencyCodeMap = new HashMap<>();
        for (Code code : codeList) {
            List<Long> adjacencyNode = routeService.getAdjacencyNode(code.getId());
            adjacencyCodeMap.put(code.getData(), adjacencyNode.stream().map(node -> {
                return codeService.getById(node).getData();
            }).collect(Collectors.toList()));
            adjacencyCodeMap.put(code.getData(), adjacencyNode.stream().map(node -> (
                    codeService.getById(node).getData()
            )).collect(Collectors.toList()));
        }
        List<String> codeDataList = codeList.stream().map(Code::getData).collect(Collectors.toList());
//        System.out.println(codeDataList.toString());
//        System.out.println(adjacencyCodeMap.toString());


        Set<String> visited = new HashSet<>();

        for (String codeData : codeList.stream().map(Code::getData).collect(Collectors.toList())) {
            if (!visited.contains(codeData)) {
        // 遍历所有节点，寻找度数不等于2的节点作为起点
        for (String codeData : codeDataList) {
            if (adjacencyCodeMap.get(codeData).size() != 2) {
                List<String> neighbors = adjacencyCodeMap.get(codeData);
                for (String neighbor : neighbors) {
                    if (adjacencyCodeMap.get(neighbor).size() == 2 && !visited.contains(neighbor)) {
                        Lane lane = new Lane(String.valueOf(snowflakeIdWorker.nextId()).substring(3));
                        lane.getCodes().add(codeData); // 包含起点
                        dfsCalcIncludingEnd(codeData, neighbor, lane, visited, adjacencyCodeMap);
                        lanes.add(lane);
                    }
                }
            }
        }

        // 处理独立的度数为2的环路或未连接到度数不等于2的节点的部分
        for (String codeData : codeDataList) {
            if (adjacencyCodeMap.get(codeData).size() == 2 && !visited.contains(codeData)) {
                // 检查是否为环路的一部分
                Lane lane = new Lane(String.valueOf(snowflakeIdWorker.nextId()).substring(3));
                dfsCalc(codeData, null, lane, visited, adjacencyCodeMap);
                dfsCalcForLoop(codeData, null, lane, visited, adjacencyCodeMap);
                lanes.add(lane);
            }
        }

        /**
         * 1.explore a dead end lane and checkout end point that is not dead point
         * 2.if this point has two near points and one of those points which not in current lane was also have two near points too
         * 3.then merge above two lane because they can connect each other
         */
        Iterator<Lane> iterator = lanes.iterator();
        while (iterator.hasNext()) {
            Lane lane = iterator.next();
            String[] endPoints = lane.queryEndPoints();
            if (null == endPoints) {
                continue;
            }
            String startPoint = endPoints[0];
            String endPoint = endPoints[1];

            boolean isDeadEndLane = false;
            String deadEndPoint = null;
            Integer anotherPointNearsCount = null;
            if (adjacencyCodeMap.get(startPoint).size() == 1) {
                isDeadEndLane = true;
                deadEndPoint = startPoint;
                anotherPointNearsCount = adjacencyCodeMap.get(endPoint).size();
            }
            if (adjacencyCodeMap.get(endPoint).size() == 1) {
                isDeadEndLane = true;
                deadEndPoint = endPoint;
                anotherPointNearsCount = adjacencyCodeMap.get(startPoint).size();
            }

            if (!isDeadEndLane) {
                continue;
            }

            if (anotherPointNearsCount == 2) {
                String anotherPoint = deadEndPoint.equals(startPoint) ? endPoint : startPoint;
                List<String> anotherPointNears = adjacencyCodeMap.get(anotherPoint);
                for (String anotherPointNear : anotherPointNears) {
                    if (!lane.getCodes().contains(anotherPointNear) && adjacencyCodeMap.get(anotherPointNear).size() == 2) {

                        for (Lane lane0 : lanes) {
                            if (lane0.getCodes().contains(anotherPointNear)) {

                                lane0.getCodes().addAll(lane.getCodes());
                                iterator.remove();


                                Collections.shuffle(lane0.getCodes());
                                System.out.println(lane0.getCodes().toString());
                                for (String code : lane0.getCodes()) {
                                    System.out.println("key: " + code + "; val" + adjacencyCodeMap.get(code).toString());
                                }
                                lane0.sortUsingDfs(adjacencyCodeMap);
                                System.out.println(lane0.getCodes().toString());


                            }

                        }

                    }
                }
            }

        }

        for (Lane lane : lanes) {
            lane.removeInteraction(adjacencyCodeMap);
        }

        lanes.removeIf(next -> next.getCodes().size() <= 2);

        System.out.println(GsonUtils.toJson(lanes));
        return R.ok().add(lanes);
    }

    private void dfsCalcIncludingEnd(String start, String current, Lane lane, Set<String> visited, Map<String, List<String>> adjacencyCodeMap) {
        // 添加当前节点
        lane.getCodes().add(current);
        visited.add(current);

    private void dfsCalc(String code, String parent, Lane lane, Set<String> visited, Map<String, List<String>> adjacencyCodeMap) {
        visited.add(code);
        lane.getCodes().add(code);

        List<String> neighbors = adjacencyCodeMap.get(code);
        List<String> neighbors = adjacencyCodeMap.get(current);
        if (neighbors == null || neighbors.isEmpty()) {
            return;
        }

        for (String neighbor : neighbors) {
            if (parent != null && neighbor.equals(parent)) {
            if (neighbor.equals(start)) {
                continue;
            }
            if (!visited.contains(neighbor) && isSameDirection(code, neighbor, parent)) {
                dfsCalc(neighbor, code, lane, visited, adjacencyCodeMap);

            if (!visited.contains(neighbor)) {
                int degree = adjacencyCodeMap.get(neighbor).size();
                if (degree == 2) {
                    if (isSameDirection(current, neighbor, start)) {
                        dfsCalcIncludingEnd(current, neighbor, lane, visited, adjacencyCodeMap);
                    }
                } else {
                    // 终点或拐弯点，包含并停止
                    lane.getCodes().add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }
    private void dfsCalcForLoop(String current, String parent, Lane lane, Set<String> visited, Map<String, List<String>> adjacencyCodeMap) {
        lane.getCodes().add(current);
        visited.add(current);

        List<String> neighbors = adjacencyCodeMap.get(current);
        if (neighbors == null || neighbors.isEmpty()) {
            return;
        }

        for (String neighbor : neighbors) {
            if (neighbor.equals(parent)) {
                continue;
            }

            if (!visited.contains(neighbor)) {
                int degree = adjacencyCodeMap.get(neighbor).size();
                if (degree == 2) {
                    if (isSameDirection(current, neighbor, parent)) {
                        dfsCalcForLoop(current, neighbor, lane, visited, adjacencyCodeMap);
                    }
                } else {
                    lane.getCodes().add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

    public boolean isSameDirection(String code, String neighbor, String parent) {
    public boolean isSameDirection(String current, String neighbor, String parent) {
        if (parent == null) {
            return true;
        }
        double direction1 = calculateDirection(codeService.selectByData(parent) , codeService.selectByData(code));
        double direction2 = calculateDirection(codeService.selectByData(code), codeService.selectByData(neighbor));
        return direction1 == direction2;

        Code parentCode = codeService.selectByData(parent);
        Code currentCode = codeService.selectByData(current);
        Code neighborCode = codeService.selectByData(neighbor);

        double direction1 = calculateDirection(parentCode, currentCode);
        double direction2 = calculateDirection(currentCode, neighborCode);
        double angleDifference = Math.abs(direction1 - direction2);

        // 规范化角度差
        angleDifference = Math.min(angleDifference, 2 * Math.PI - angleDifference);

        // 设置角度差阈值为3度
        return angleDifference < Math.toRadians(3);
    }

    /**
     * 计算两个点之间的方向角
     *
     * @param from 起点
     * @param to 终点
     * @return 方向角（弧度）
     */
    public double calculateDirection(Code from, Code to) {
        double deltaX = to.getX() - from.getX();
        double deltaY = to.getY() - from.getY();
        return Math.atan2(deltaY, deltaX);
    }


}