#地图编辑路径联通性导致算法计算失败问题修复

Junjie

19 小时以前 ed266efb662c5b8460ecc22e31a070a718f35f9c

#地图编辑路径联通性导致算法计算失败问题修复

 src/main/java/com/zy/asrs/service/impl/BasMapEditorServiceImpl.java

@@ -54,6 +54,8 @@
    private static final double DEFAULT_CANVAS_HEIGHT = 5200D;
    private static final int X_SCALE = 40;
    private static final int Y_SCALE = 8;
    private static final double AUTO_BRIDGE_MAX_GAP_DISPLAY = 2.0d;
    private static final double AUTO_BRIDGE_MIN_OVERLAP_RATIO = 0.85d;

    @Autowired
    private BasMapService basMapService;
@@ -330,6 +332,10 @@
        for (BasMapEditorElement element : elements) {
            CompiledRect rect = toCompiledRect(element);
            rects.add(rect);
        }
        List<CompiledRect> allRects = new ArrayList<>(rects);
        allRects.addAll(buildAutoBridgeRects(rects));
        for (CompiledRect rect : allRects) {
            xBounds.add(rect.left);
            xBounds.add(rect.right);
            yBounds.add(rect.top);
@@ -359,7 +365,7 @@
            stored.add(row);
        }

        for (CompiledRect rect : rects) {
        for (CompiledRect rect : allRects) {
            Integer rowStart = yIndexMap.get(String.valueOf(rect.top));
            Integer rowEndIndex = yIndexMap.get(String.valueOf(rect.bottom));
            Integer colStart = xIndexMap.get(String.valueOf(rect.left));
@@ -426,6 +432,8 @@
        rect.id = element.getId();
        rect.type = element.getType();
        rect.value = normalizeCellValue(element.getType(), element.getValue());
        JSONObject valueObject = parseJsonObject(rect.value);
        rect.stationId = valueObject == null ? null : valueObject.getInteger("stationId");
        rect.left = toRawWidth(element.getX());
        rect.top = toRawHeight(element.getY());
        rect.right = toRawWidth(safeDouble(element.getX()) + safeDouble(element.getWidth()));
@@ -434,6 +442,162 @@
            throw new CoolException("元素尺寸无效: " + element.getId());
        }
        return rect;
    }

    private List<CompiledRect> buildAutoBridgeRects(List<CompiledRect> sourceRects) {
        List<CompiledRect> bridgeRects = new ArrayList<>();
        if (sourceRects == null || sourceRects.size() < 2) {
            return bridgeRects;
        }
        for (int i = 0; i < sourceRects.size(); i++) {
            CompiledRect first = sourceRects.get(i);
            if (!isAutoBridgeCandidate(first)) {
                continue;
            }
            for (int j = i + 1; j < sourceRects.size(); j++) {
                CompiledRect second = sourceRects.get(j);
                if (!isAutoBridgeCandidate(second)) {
                    continue;
                }
                CompiledRect bridgeRect = buildAutoBridgeRect(first, second);
                if (bridgeRect == null) {
                    continue;
                }
                if (hasRectConflict(bridgeRect, sourceRects, bridgeRects, first, second)) {
                    continue;
                }
                bridgeRects.add(bridgeRect);
            }
        }
        return bridgeRects;
    }

    private boolean isAutoBridgeCandidate(CompiledRect rect) {
        return rect != null && "devp".equals(rect.type) && rect.stationId != null && rect.stationId > 0;
    }

    private CompiledRect buildAutoBridgeRect(CompiledRect first, CompiledRect second) {
        CompiledRect horizontalBridge = buildHorizontalBridgeRect(first, second);
        if (horizontalBridge != null) {
            return horizontalBridge;
        }
        return buildVerticalBridgeRect(first, second);
    }

    private CompiledRect buildHorizontalBridgeRect(CompiledRect first, CompiledRect second) {
        CompiledRect left = first.left <= second.left ? first : second;
        CompiledRect right = left == first ? second : first;
        int gap = right.left - left.right;
        if (gap <= 0 || gap > toRawWidth(AUTO_BRIDGE_MAX_GAP_DISPLAY)) {
            return null;
        }
        int overlapTop = Math.max(left.top, right.top);
        int overlapBottom = Math.min(left.bottom, right.bottom);
        int overlapSize = overlapBottom - overlapTop;
        if (!passesAutoBridgeOverlapThreshold(overlapSize, left.bottom - left.top, right.bottom - right.top)) {
            return null;
        }
        return buildBridgeRect(
                "bridge_h_" + left.stationId + "_" + right.stationId,
                left.right,
                overlapTop,
                right.left,
                overlapBottom,
                Arrays.asList("left", "right"),
                left.stationId,
                right.stationId
        );
    }

    private CompiledRect buildVerticalBridgeRect(CompiledRect first, CompiledRect second) {
        CompiledRect top = first.top <= second.top ? first : second;
        CompiledRect bottom = top == first ? second : first;
        int gap = bottom.top - top.bottom;
        if (gap <= 0 || gap > toRawHeight(AUTO_BRIDGE_MAX_GAP_DISPLAY)) {
            return null;
        }
        int overlapLeft = Math.max(top.left, bottom.left);
        int overlapRight = Math.min(top.right, bottom.right);
        int overlapSize = overlapRight - overlapLeft;
        if (!passesAutoBridgeOverlapThreshold(overlapSize, top.right - top.left, bottom.right - bottom.left)) {
            return null;
        }
        return buildBridgeRect(
                "bridge_v_" + top.stationId + "_" + bottom.stationId,
                overlapLeft,
                top.bottom,
                overlapRight,
                bottom.top,
                Arrays.asList("top", "bottom"),
                top.stationId,
                bottom.stationId
        );
    }

    private boolean passesAutoBridgeOverlapThreshold(int overlapSize, int firstSpan, int secondSpan) {
        if (overlapSize <= 0 || firstSpan <= 0 || secondSpan <= 0) {
            return false;
        }
        double overlapRatio = overlapSize * 1.0d / Math.max(firstSpan, secondSpan);
        return overlapRatio >= AUTO_BRIDGE_MIN_OVERLAP_RATIO;
    }

    private CompiledRect buildBridgeRect(String id,
                                         int left,
                                         int top,
                                         int right,
                                         int bottom,
                                         List<String> directions,
                                         Integer firstStationId,
                                         Integer secondStationId) {
        if (left >= right || top >= bottom) {
            return null;
        }
        CompiledRect rect = new CompiledRect();
        rect.id = id;
        rect.type = "devp";
        rect.value = buildBridgeValue(directions, firstStationId, secondStationId);
        rect.left = left;
        rect.top = top;
        rect.right = right;
        rect.bottom = bottom;
        return rect;
    }

    private String buildBridgeValue(List<String> directions, Integer firstStationId, Integer secondStationId) {
        JSONObject value = new JSONObject();
        value.put("direction", directions);
        value.put("bridgeStationIds", Arrays.asList(firstStationId, secondStationId));
        value.put("autoBridge", 1);
        return value.toJSONString();
    }

    private boolean hasRectConflict(CompiledRect candidate,
                                    List<CompiledRect> sourceRects,
                                    List<CompiledRect> bridgeRects,
                                    CompiledRect firstIgnore,
                                    CompiledRect secondIgnore) {
        for (CompiledRect rect : sourceRects) {
            if (rect == null || rect == firstIgnore || rect == secondIgnore) {
                continue;
            }
            if (compiledRectsOverlap(candidate, rect)) {
                return true;
            }
        }
        for (CompiledRect rect : bridgeRects) {
            if (rect != null && compiledRectsOverlap(candidate, rect)) {
                return true;
            }
        }
        return false;
    }

    private boolean compiledRectsOverlap(CompiledRect first, CompiledRect second) {
        return first.left < second.right
                && first.right > second.left
                && first.top < second.bottom
                && first.bottom > second.top;
    }

    private Map<String, Integer> buildBoundaryIndexMap(List<Integer> bounds) {
@@ -893,6 +1057,7 @@
        private String id;
        private String type;
        private String value;
        private Integer stationId;
        private int left;
        private int top;
        private int right;

 src/main/java/com/zy/asrs/service/impl/StationCycleCapacityServiceImpl.java

@@ -1,6 +1,7 @@
package com.zy.asrs.service.impl;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import com.baomidou.mybatisplus.core.conditions.query.QueryWrapper;
import com.zy.asrs.domain.vo.StationCycleCapacityVo;
@@ -372,17 +373,13 @@
                        continue;
                    }
                    for (NavigateNode nextNode : nextNodeList) {
                        JSONObject nextValueObj = parseNodeValue(nextNode.getNodeValue());
                        if (nextValueObj == null) {
                            continue;
                        for (Integer nextStationId : resolveConnectedStationIds(stationId, nextNode)) {
                            if (nextStationId == null || stationId.equals(nextStationId)) {
                                continue;
                            }
                            context.graph.computeIfAbsent(nextStationId, k -> new HashSet<>());
                            context.graph.get(stationId).add(nextStationId);
                        }
                        Integer nextStationId = nextValueObj.getInteger("stationId");
                        if (nextStationId == null || stationId.equals(nextStationId)) {
                            continue;
                        }

                        context.graph.computeIfAbsent(nextStationId, k -> new HashSet<>());
                        context.graph.get(stationId).add(nextStationId);
                    }
                }
            }
@@ -434,6 +431,27 @@
                || (isBarcodeStation != null && isBarcodeStation == 1);
    }

    private Set<Integer> resolveConnectedStationIds(Integer currentStationId, NavigateNode nextNode) {
        Set<Integer> stationIdSet = new HashSet<>();
        JSONObject nextValueObj = parseNodeValue(nextNode == null ? null : nextNode.getNodeValue());
        if (nextValueObj == null) {
            return stationIdSet;
        }
        Integer directStationId = nextValueObj.getInteger("stationId");
        if (directStationId != null && !directStationId.equals(currentStationId)) {
            stationIdSet.add(directStationId);
        }
        JSONArray bridgeStationIds = nextValueObj.getJSONArray("bridgeStationIds");
        if (bridgeStationIds != null) {
            for (Integer bridgeStationId : bridgeStationIds.toJavaList(Integer.class)) {
                if (bridgeStationId != null && !bridgeStationId.equals(currentStationId)) {
                    stationIdSet.add(bridgeStationId);
                }
            }
        }
        return stationIdSet;
    }

    private StationOccupancyContext buildStationOccupancyContext() {
        StationOccupancyContext context = new StationOccupancyContext();
        List<DeviceConfig> devpList = deviceConfigService.list(new QueryWrapper<DeviceConfig>()

 src/main/java/com/zy/common/utils/NavigateSolution.java

@@ -399,12 +399,16 @@
    }

    private Integer extractStationId(NavigateNode node) {
        if (node == null || !"devp".equals(node.getNodeType())) {
        JSONObject valueObj = parseNodeValue(node == null ? null : node.getNodeValue());
        return valueObj == null ? null : valueObj.getInteger("stationId");
    }

    private JSONObject parseNodeValue(String nodeValue) {
        if (nodeValue == null || nodeValue.trim().isEmpty()) {
            return null;
        }
        try {
            JSONObject valueObj = JSON.parseObject(node.getNodeValue());
            return valueObj == null ? null : valueObj.getInteger("stationId");
            return JSON.parseObject(nodeValue);
        } catch (Exception ignore) {
            return null;
        }
@@ -503,18 +507,60 @@
    }

    public NavigateNode findStationNavigateNode(List<List<NavigateNode>> map, int stationId) {
        NavigateNode bestNode = null;
        int bestExternalConnectionCount = -1;
        int bestNeighborCount = -1;
        for(int x = 0; x < map.size(); x++) {
            for(int y = 0; y < map.get(0).size(); y++) {
                NavigateNode node = map.get(x).get(y);
                if("devp".equals(node.getNodeType())) {
                    JSONObject valueObj = JSON.parseObject(node.getNodeValue());
                    if(valueObj.getInteger("stationId") == stationId) {
                        return node;
                    }
                Integer currentStationId = extractStationId(node);
                if (currentStationId == null || currentStationId != stationId) {
                    continue;
                }
                ArrayList<NavigateNode> neighbors = extend_current_node(map, node);
                int externalConnectionCount = countExternalConnectionCount(stationId, neighbors);
                int neighborCount = neighbors == null ? 0 : neighbors.size();
                if (externalConnectionCount > bestExternalConnectionCount
                        || (externalConnectionCount == bestExternalConnectionCount && neighborCount > bestNeighborCount)) {
                    bestNode = node;
                    bestExternalConnectionCount = externalConnectionCount;
                    bestNeighborCount = neighborCount;
                }
            }
        }
        return null;
        return bestNode;
    }

    private int countExternalConnectionCount(Integer currentStationId, List<NavigateNode> neighbors) {
        Set<Integer> connectedStationIdSet = new LinkedHashSet<>();
        if (neighbors == null || neighbors.isEmpty()) {
            return 0;
        }
        for (NavigateNode neighbor : neighbors) {
            connectedStationIdSet.addAll(resolveAdjacentStationIds(currentStationId, neighbor));
        }
        return connectedStationIdSet.size();
    }

    private Set<Integer> resolveAdjacentStationIds(Integer currentStationId, NavigateNode node) {
        Set<Integer> stationIdSet = new LinkedHashSet<>();
        JSONObject valueObj = parseNodeValue(node == null ? null : node.getNodeValue());
        if (valueObj == null) {
            return stationIdSet;
        }
        Integer directStationId = valueObj.getInteger("stationId");
        if (directStationId != null && !directStationId.equals(currentStationId)) {
            stationIdSet.add(directStationId);
        }
        if (valueObj.getJSONArray("bridgeStationIds") == null) {
            return stationIdSet;
        }
        for (Integer bridgeStationId : valueObj.getJSONArray("bridgeStationIds").toJavaList(Integer.class)) {
            if (bridgeStationId != null && !bridgeStationId.equals(currentStationId)) {
                stationIdSet.add(bridgeStationId);
            }
        }
        return stationIdSet;
    }

    public NavigateNode findTrackSiteNoNavigateNode(List<List<NavigateNode>> map, int trackSiteNo) {

 src/main/java/com/zy/common/utils/NavigateUtils.java

@@ -32,6 +32,7 @@
import org.springframework.stereotype.Component;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import com.baomidou.mybatisplus.core.conditions.query.QueryWrapper;
import com.core.common.SpringUtils;
@@ -1224,13 +1225,14 @@
                    graph.computeIfAbsent(stationId, key -> new LinkedHashSet<>());
                    List<NavigateNode> nextNodeList = navigateSolution.extend_current_node(stationMap, node);
                    for (NavigateNode nextNode : safeList(nextNodeList)) {
                        Integer nextStationId = extractStationId(nextNode);
                        if (nextStationId == null || stationId.equals(nextStationId)) {
                            continue;
                        for (Integer nextStationId : resolveConnectedStationIds(stationId, nextNode)) {
                            if (nextStationId == null || stationId.equals(nextStationId)) {
                                continue;
                            }
                            graph.computeIfAbsent(nextStationId, key -> new LinkedHashSet<>());
                            graph.get(stationId).add(nextStationId);
                            graph.get(nextStationId).add(stationId);
                        }
                        graph.computeIfAbsent(nextStationId, key -> new LinkedHashSet<>());
                        graph.get(stationId).add(nextStationId);
                        graph.get(nextStationId).add(stationId);
                    }
                }
            }
@@ -1238,6 +1240,33 @@
        return graph;
    }

    private Set<Integer> resolveConnectedStationIds(Integer currentStationId, NavigateNode nextNode) {
        Set<Integer> stationIdSet = new LinkedHashSet<>();
        if (nextNode == null || nextNode.getNodeValue() == null) {
            return stationIdSet;
        }
        try {
            JSONObject value = JSON.parseObject(nextNode.getNodeValue());
            if (value == null) {
                return stationIdSet;
            }
            Integer directStationId = value.getInteger("stationId");
            if (directStationId != null && !directStationId.equals(currentStationId)) {
                stationIdSet.add(directStationId);
            }
            JSONArray bridgeStationIds = value.getJSONArray("bridgeStationIds");
            if (bridgeStationIds != null) {
                for (Integer bridgeStationId : bridgeStationIds.toJavaList(Integer.class)) {
                    if (bridgeStationId != null && !bridgeStationId.equals(currentStationId)) {
                        stationIdSet.add(bridgeStationId);
                    }
                }
            }
        } catch (Exception ignore) {
        }
        return stationIdSet;
    }

    private List<Integer> loadStationLevList() {
        List<Integer> levList = new ArrayList<>();
        if (basStationService == null) {

 src/main/webapp/views/basMap/editor.html

@@ -496,7 +496,7 @@
            <div class="canvas-toolbar">
                    <div class="canvas-toolbar-main">
                        <div class="canvas-toolbar-title">
                            <h1>PixiJS 自由画布地图编辑器</h1>
                            <h1>WCS地图编辑器</h1>
                        </div>
                    <div class="canvas-toolbar-meta">
                        <span class="canvas-meta">楼层: {{ currentLev ? currentLev + 'F' : '--' }}</span>

 src/test/java/com/zy/asrs/service/impl/BasMapEditorServiceImplTest.java

New file
@@ -0,0 +1,135 @@
package com.zy.asrs.service.impl;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONObject;
import com.zy.asrs.domain.BasMapEditorDoc;
import com.zy.asrs.domain.BasMapEditorElement;
import com.zy.common.model.NavigateNode;
import com.zy.common.utils.NavigateSolution;
import com.zy.core.enums.MapNodeType;
import org.junit.jupiter.api.Test;
import org.springframework.test.util.ReflectionTestUtils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotNull;
import static org.junit.jupiter.api.Assertions.assertTrue;

class BasMapEditorServiceImplTest {

    @Test
    void compileToStoredMapData_bridgesNearlyAlignedDevpElements() {
        BasMapEditorServiceImpl service = new BasMapEditorServiceImpl();
        BasMapEditorDoc doc = buildDoc(
                createDevp("left", 0.0d, 0.0d, 10.0d, 10.0d, 101, 1),
                createDevp("right", 11.0d, 0.5d, 10.0d, 10.0d, 102, 2)
        );

        List<List<HashMap<String, Object>>> storedData = compileStoredMapData(service, doc);
        List<List<NavigateNode>> stationMap = buildStationMap(storedData);
        NavigateSolution navigateSolution = new NavigateSolution();

        NavigateNode startNode = navigateSolution.findStationNavigateNode(stationMap, 101);
        NavigateNode endNode = navigateSolution.findStationNavigateNode(stationMap, 102);
        assertNotNull(startNode);
        assertNotNull(endNode);

        List<List<NavigateNode>> paths = navigateSolution.allSimplePaths(stationMap, startNode, endNode, 40, 20, 200);
        assertFalse(paths.isEmpty(), "轻微错位但接触边高度重合时应自动判定为联通");
    }

    @Test
    void compileToStoredMapData_doesNotBridgeClearlyMisalignedDevpElements() {
        BasMapEditorServiceImpl service = new BasMapEditorServiceImpl();
        BasMapEditorDoc doc = buildDoc(
                createDevp("left", 0.0d, 0.0d, 10.0d, 10.0d, 101, 1),
                createDevp("right", 11.0d, 4.5d, 10.0d, 10.0d, 102, 2)
        );

        List<List<HashMap<String, Object>>> storedData = compileStoredMapData(service, doc);
        List<List<NavigateNode>> stationMap = buildStationMap(storedData);
        NavigateSolution navigateSolution = new NavigateSolution();

        NavigateNode startNode = navigateSolution.findStationNavigateNode(stationMap, 101);
        NavigateNode endNode = navigateSolution.findStationNavigateNode(stationMap, 102);
        assertNotNull(startNode);
        assertNotNull(endNode);

        List<List<NavigateNode>> paths = navigateSolution.allSimplePaths(stationMap, startNode, endNode, 40, 20, 200);
        assertTrue(paths.isEmpty(), "明显错位时不应被自动桥接为联通");
    }

    @SuppressWarnings("unchecked")
    private List<List<HashMap<String, Object>>> compileStoredMapData(BasMapEditorServiceImpl service, BasMapEditorDoc doc) {
        return (List<List<HashMap<String, Object>>>) ReflectionTestUtils.invokeMethod(service, "compileToStoredMapData", doc);
    }

    private BasMapEditorDoc buildDoc(BasMapEditorElement... elements) {
        BasMapEditorDoc doc = new BasMapEditorDoc();
        doc.setLev(1);
        doc.setEditorMode("free-v1");
        doc.setCanvasWidth(80.0d);
        doc.setCanvasHeight(40.0d);
        doc.setElements(List.of(elements));
        return doc;
    }

    private BasMapEditorElement createDevp(String id,
                                           double x,
                                           double y,
                                           double width,
                                           double height,
                                           int stationId,
                                           int deviceNo) {
        BasMapEditorElement element = new BasMapEditorElement();
        element.setId(id);
        element.setType("devp");
        element.setX(x);
        element.setY(y);
        element.setWidth(width);
        element.setHeight(height);

        JSONObject value = new JSONObject();
        value.put("stationId", stationId);
        value.put("deviceNo", deviceNo);
        value.put("direction", List.of("left", "right"));
        element.setValue(value.toJSONString());
        return element;
    }

    private List<List<NavigateNode>> buildStationMap(List<List<HashMap<String, Object>>> storedData) {
        List<List<NavigateNode>> stationMap = new ArrayList<>();
        for (int rowIndex = 0; rowIndex < storedData.size(); rowIndex++) {
            List<HashMap<String, Object>> row = storedData.get(rowIndex);
            List<NavigateNode> navigateNodeRow = new ArrayList<>();
            for (int colIndex = 0; colIndex < row.size(); colIndex++) {
                HashMap<String, Object> cell = row.get(colIndex);
                NavigateNode node = new NavigateNode(rowIndex, colIndex);
                String nodeType = cell == null ? null : String.valueOf(cell.get("type"));
                String mergeType = cell == null ? null : stringValue(cell.get("mergeType"));
                String nodeValue = cell == null ? null : stringValue(cell.get("value"));

                if ("devp".equals(nodeType) || ("merge".equals(nodeType) && "devp".equals(mergeType))) {
                    node.setValue(MapNodeType.NORMAL_PATH.id);
                    JSONObject valueObject = JSON.parseObject(nodeValue);
                    node.setDirectionList(valueObject == null ? new ArrayList<>() : valueObject.getJSONArray("direction").toJavaList(String.class));
                } else {
                    node.setValue(MapNodeType.DISABLE.id);
                }

                node.setNodeType(nodeType);
                node.setNodeValue(nodeValue);
                navigateNodeRow.add(node);
            }
            stationMap.add(navigateNodeRow);
        }
        return stationMap;
    }

    private String stringValue(Object value) {
        return value == null ? null : String.valueOf(value);
    }
}