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<Lane> lanes = new ArrayList<>();
|
List<Code> codeList = codeService.list(new LambdaQueryWrapper<Code>().eq(Code::getStatus, 1));
|
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()));
|
}
|
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<>();
|
|
// 遍历所有节点，寻找度数不等于2的节点作为起点
|
for (String codeData : codeDataList) {
|
if (adjacencyCodeMap.getOrDefault(codeData, Collections.emptyList()).size() != 2) {
|
List<String> neighbors = adjacencyCodeMap.getOrDefault(codeData, Collections.emptyList());
|
for (String neighbor : neighbors) {
|
// 仅遍历度数为2且未被访问的邻居
|
if (adjacencyCodeMap.getOrDefault(neighbor, Collections.emptyList()).size() == 2 && !visited.contains(neighbor)) {
|
Lane lane = new Lane(String.valueOf(snowflakeIdWorker.nextId()).substring(3));
|
dfsCalc(neighbor, codeData, lane, visited, adjacencyCodeMap);
|
lanes.add(lane);
|
}
|
}
|
}
|
}
|
|
// 处理度数为2且连接两个拐弯点的节点（独立巷道）
|
for (String codeData : codeDataList) {
|
if (adjacencyCodeMap.getOrDefault(codeData, Collections.emptyList()).size() == 2 && !visited.contains(codeData)) {
|
List<String> neighbors = adjacencyCodeMap.getOrDefault(codeData, Collections.emptyList());
|
boolean connectedToTwoTurningPoints = true;
|
for (String neighbor : neighbors) {
|
if (adjacencyCodeMap.getOrDefault(neighbor, Collections.emptyList()).size() == 2) {
|
connectedToTwoTurningPoints = false;
|
break;
|
}
|
}
|
if (connectedToTwoTurningPoints) {
|
Lane lane = new Lane(String.valueOf(snowflakeIdWorker.nextId()).substring(3));
|
lane.getCodes().add(codeData);
|
lanes.add(lane);
|
visited.add(codeData);
|
}
|
}
|
}
|
|
|
System.out.println(GsonUtils.toJson(lanes));
|
return R.ok().add(lanes);
|
}
|
|
|
private void dfsCalc(String code, String parent, Lane lane, Set<String> visited, Map<String, List<String>> adjacencyCodeMap) {
|
// 检查当前节点的度数是否为2
|
if (adjacencyCodeMap.getOrDefault(code, Collections.emptyList()).size() != 2) {
|
// 不包含拐弯点
|
return;
|
}
|
|
// 标记为已访问并加入巷道
|
visited.add(code);
|
lane.getCodes().add(code);
|
|
List<String> neighbors = adjacencyCodeMap.get(code);
|
if (neighbors == null || neighbors.isEmpty()) {
|
return;
|
}
|
|
for (String neighbor : neighbors) {
|
if (neighbor.equals(parent)) {
|
continue;
|
}
|
|
if (adjacencyCodeMap.getOrDefault(neighbor, Collections.emptyList()).size() == 2 && !visited.contains(neighbor)) {
|
// 检查方向是否一致
|
if (isSameDirection(code, neighbor, parent)) {
|
dfsCalc(neighbor, code, lane, visited, adjacencyCodeMap);
|
}
|
}
|
}
|
}
|
|
public boolean isSameDirection(String code, String neighbor, String parent) {
|
if (parent == null) {
|
return true;
|
}
|
|
Code parentCode = codeService.selectByData(parent);
|
Code currentCode = codeService.selectByData(code);
|
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);
|
}
|
|
public double calculateDirection(Code from, Code to) {
|
double deltaX = to.getX() - from.getX();
|
double deltaY = to.getY() - from.getY();
|
return Math.atan2(deltaY, deltaX);
|
}
|
|
|
}
|
