package com.zy.acs.manager.core; import com.baomidou.mybatisplus.core.conditions.query.LambdaQueryWrapper; import com.zy.acs.common.utils.GsonUtils; import com.zy.acs.framework.common.R; import com.zy.acs.framework.common.SnowflakeIdWorker; import com.zy.acs.manager.core.domain.Lane; import com.zy.acs.manager.manager.entity.Code; import com.zy.acs.manager.manager.entity.Route; import com.zy.acs.manager.manager.service.CodeService; import com.zy.acs.manager.manager.service.RouteService; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.web.bind.annotation.GetMapping; import org.springframework.web.bind.annotation.RequestMapping; import org.springframework.web.bind.annotation.RestController; import java.util.*; import java.util.stream.Collectors; /** * Created by vincent on 10/24/2024 */ @RestController @RequestMapping("/test") public class DispatcherTestController { @Autowired private CodeService codeService; @Autowired private RouteService routeService; @Autowired private SnowflakeIdWorker snowflakeIdWorker; @GetMapping("/dfs") public R dfs() { List lanes = new ArrayList<>(); List codeList = codeService.list(new LambdaQueryWrapper().eq(Code::getStatus, 1)); Map> adjacencyCodeMap = new HashMap<>(); for (Code code : codeList) { List adjacencyNode = routeService.getAdjacencyNode(code.getId()); adjacencyCodeMap.put(code.getData(), adjacencyNode.stream().map(node -> { return codeService.getById(node).getData(); }).collect(Collectors.toList())); } List codeDataList = codeList.stream().map(Code::getData).collect(Collectors.toList()); System.out.println(codeDataList.toString()); System.out.println(adjacencyCodeMap.toString()); Set visited = new HashSet<>(); // 遍历所有节点,寻找度数不等于2的节点作为起点 for (String codeData : codeDataList) { if (adjacencyCodeMap.get(codeData).size() != 2) { List 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)); dfsCalcForLoop(codeData, null, lane, visited, adjacencyCodeMap); lanes.add(lane); } } System.out.println(GsonUtils.toJson(lanes)); return R.ok().add(lanes); } private void dfsCalcIncludingEnd(String start, String current, Lane lane, Set visited, Map> adjacencyCodeMap) { // 添加当前节点 lane.getCodes().add(current); visited.add(current); List neighbors = adjacencyCodeMap.get(current); if (neighbors == null || neighbors.isEmpty()) { return; } for (String neighbor : neighbors) { if (neighbor.equals(start)) { continue; } 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 visited, Map> adjacencyCodeMap) { lane.getCodes().add(current); visited.add(current); List 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 current, String neighbor, String parent) { if (parent == null) { return true; } 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); } }