10397997272

Committed 15 Aug 2024 02:51AM UTC coverage: 90.932% (+0.02%) from 90.915%

Build # 10397997272

Build Type

Pull #6181

github

Committed by

yvonneyx

Commit Message

test: supplement unit test

Pull Request Pull Request #6181: feat: use a-star pathfinding algorithm to draw polyline

Run Details

2863 of 3505 branches covered (81.68%)

Branch coverage included in aggregate %.

212 of 220 new or added lines in 5 files covered. (96.36%)

9 existing lines in 2 files now uncovered.

6473 of 6762 relevant lines covered (95.73%)

12058.51 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

91.67

/packages/g6/src/utils/router/shortest-path.ts

import { isNumber } from '@antv/util';
import type { Direction, ID, Node, Point, ShortestPathRouterOptions } from '../../types';
import { getBBoxSegments, getBBoxSize, getExpandedBBox, isPointInBBox, isPointOnBBoxBoundary } from '../bbox';
import { getLinesIntersection } from '../line';
import { add, manhattanDistance, toVector2 } from '../vector';

const defaultCfg: ShortestPathRouterOptions = {
  enableObstacleAvoidance: false,
  offset: 10,
  maxAllowedDirectionChange: Math.PI / 2,
  maximumLoops: 3000,
  gridSize: 5,
  startDirections: ['top', 'right', 'bottom', 'left'],
  endDirections: ['top', 'right', 'bottom', 'left'],
  directionMap: {
    right: { stepX: 1, stepY: 0 },
    left: { stepX: -1, stepY: 0 },
    bottom: { stepX: 0, stepY: 1 },
    top: { stepX: 0, stepY: -1 },
  },
  penalties: { 0: 0, 90: 0 },
  distFunc: manhattanDistance,
};

const keyOf = (point: Point) => `${Math.round(point[0])}|||${Math.round(point[1])}`;

function alignToGrid(p: Point, gridSize: number): Point;
function alignToGrid(p: number, gridSize: number): number;
/**
 * <zh/> 将坐标对齐到网格
 *
 * <en/> Align to the grid
 * @param p - <zh/> 坐标 | <en/> point
 * @param gridSize - <zh/> 网格大小 | <en/> grid size
 * @returns <zh/> 对齐后的坐标 | <en/> aligned point
 */
function alignToGrid(p: number | Point, gridSize: number): number | Point {
  const align = (value: number) => Math.round(value / gridSize);
  if (isNumber(p)) return align(p);
  return p.map(align) as Point;
}

/**
 * <zh/> 获取两个角度的变化方向，并确保小于 180 度
 *
 * <en/ >Get changed direction angle and make sure less than 180 degrees
 * @param angle1 - <zh/> 第一个角度 | <en/> the first angle
 * @param angle2 - <zh/> 第二个角度 | <en/> the second angle
 * @returns <zh/> 两个角度的变化方向 | <en/> changed direction angle
 */
function getAngleDiff(angle1: number, angle2: number) {
  const directionChange = Math.abs(angle1 - angle2);
  return directionChange > Math.PI ? 2 * Math.PI - directionChange : directionChange;
}

/**
 * <zh/> 获取从 p1 指向 p2 的向量与 x 轴正方向之间的夹角，单位为弧度
 *
 * <en/> Get the angle between the vector from p1 to p2 and the positive direction of the x-axis, in radians
 * @param p1 - <zh/> 点 p1 | <en/> point p1
 * @param p2 - <zh/> 点 p2 | <en/> point p2
 * @returns <zh/> 夹角 | <en/> angle
 */
function getDirectionAngle(p1: Point, p2: Point) {
  const deltaX = p2[0] - p1[0];
  const deltaY = p2[1] - p1[1];

  if (!deltaX && !deltaY) return 0;

  return Math.atan2(deltaY, deltaX);
}

/**
 * <zh/> 获取两个点之间的方向变化
 *
 * <en/> Get direction change between two points
 * @param current - <zh/> 当前点 | <en/> current point
 * @param neighbor - <zh/> 邻居点 | <en/> neighbor point
 * @param cameFrom - <zh/> 来源点 | <en/> source point
 * @param scaleStartPoint - <zh/> 缩放后的起点 | <en/> scaled start point
 * @returns <zh/> 方向变化 | <en/> direction change
 */
function getDirectionChange(
  current: Point,
  neighbor: Point,
  cameFrom: Record<string, Point>,
  scaleStartPoint: Point,
): number {
  const directionAngle = getDirectionAngle(current, neighbor);

  const currentCameFrom = cameFrom[keyOf(current)];
  const prev = !currentCameFrom ? scaleStartPoint : currentCameFrom;
  const prevDirectionAngle = getDirectionAngle(prev, current);

  return getAngleDiff(prevDirectionAngle, directionAngle);
}

/**
 * <zh/> 获取障碍物地图
 *
 * <en/> Get obstacle map
 * @param nodes - <zh/> 图上所有节点 | <en/> all nodes on the graph
 * @param options - <zh/> 路由配置 | <en/> router options
 * @returns <zh/> 障碍物地图 | <en/> obstacle map
 */
const getObstacleMap = (nodes: Node[], options: Required<ShortestPathRouterOptions>) => {
  const { offset, gridSize } = options;
  const obstacleMap: Record<string, boolean> = {};

  nodes.forEach((item: Node) => {
    if (!item || item.destroyed || !item.isVisible()) return;
    const bbox = getExpandedBBox(item.getRenderBounds(), offset);
    for (let x = alignToGrid(bbox.min[0], gridSize); x <= alignToGrid(bbox.max[0], gridSize); x += 1) {
      for (let y = alignToGrid(bbox.min[1], gridSize); y <= alignToGrid(bbox.max[1], gridSize); y += 1) {
        obstacleMap[`${x}|||${y}`] = true;
      }
    }
  });
  return obstacleMap;
};

/**
 * <zh/> 估算从起点到多个锚点的最小代价
 *
 * <en/> Estimate minimum cost from the starting point to multiple anchor points
 * @param from - <zh/> 起点 | <en/> source point
 * @param anchors - <zh/> 锚点 | <en/> anchor points
 * @param distFunc - <zh/> 距离函数 | <en/> distance function
 * @returns <zh/> 最小成本 | <en/> minimum cost
 */
export function estimateCost(from: Point, anchors: Point[], distFunc: (p1: Point, p2: Point) => number) {
  return Math.min(...anchors.map((anchor) => distFunc(from, anchor)));
}

/**
 * <zh/> 已知一个点集与一个参考点，从点集中找到距离参考点最近的点
 *
 * <en/> Given a set of points and a reference point, find the point closest to the reference point from the set of points
 * @param points - <zh/> 点集 | <en/> set of points
 * @param refPoint - <zh/> 参考点 | <en/> reference point
 * @param distFunc - <zh/> 距离函数 | <en/> distance function
 * @returns <zh/> 最近的点 | <en/> nearest point
 */
export function getNearestPoint(points: Point[], refPoint: Point, distFunc: (p1: Point, p2: Point) => number): Point {
  let nearestPoint = points[0];
  let minDistance = distFunc(points[0], refPoint);
  for (let i = 0; i < points.length; i++) {
    const point = points[i];
    const dis = distFunc(point, refPoint);
    if (dis < minDistance) {
      nearestPoint = point;
      minDistance = dis;
    }
  }
  return nearestPoint;
}

/**
 * Calculate the connection points on the expanded BBox
 * @param point
 * @param node
 * @param directions
 * @param options
 */
const getBoxPoints = (
  point: Point,
  node: Node,
  directions: Direction[],
  options: Required<ShortestPathRouterOptions>,
): Point[] => {
  // create-edge 生成边的过程中，endNode 为 null
  if (!node) return [point];

  const { directionMap, offset } = options;
  const expandedBBox = getExpandedBBox(node.getRenderBounds(), offset);

  const points = (Object.keys(directionMap) as Direction[]).reduce<Point[]>((res, directionKey) => {
    if (directions.includes(directionKey)) {
      const direction = directionMap[directionKey];
      const [width, height] = getBBoxSize(expandedBBox);
      const otherPoint: Point = [point[0] + direction.stepX * width, point[1] + direction.stepY * height];
      const segments = getBBoxSegments(expandedBBox);
      for (let i = 0; i < segments.length; i++) {
        const intersectP = getLinesIntersection([point, otherPoint], segments[i]);
        if (intersectP && isPointOnBBoxBoundary(intersectP, expandedBBox)) {
          res.push(intersectP);
        }
      }
    }

    return res;
  }, []);

  if (!isPointInBBox(point, expandedBBox)) {
    points.push(point);
  }

  return points.map((point) => alignToGrid(point, options.gridSize));
};

const getControlPoints = (
  current: Point,
  cameFrom: Record<ID, Point>,
  scaleStartPoint: Point,
  endPoint: Point,
  startPoints: Point[],
  scaleEndPoint: Point,
  gridSize: number,
) => {
  const controlPoints: Point[] = [];

  // append endPoint
  let pointZero: Point = [
    scaleEndPoint[0] === endPoint[0] ? endPoint[0] : current[0] * gridSize,
    scaleEndPoint[1] === endPoint[1] ? endPoint[1] : current[1] * gridSize,
  ];
  controlPoints.unshift(pointZero);

  let _current = current;
  let _currentCameFrom = cameFrom[keyOf(_current)];

  while (_currentCameFrom) {
    const prePoint = _currentCameFrom;
    const point = _current;
    const directionChange = getDirectionChange(prePoint, point, cameFrom, scaleStartPoint);

    if (directionChange) {
      pointZero = [
        prePoint[0] === point[0] ? pointZero[0] : prePoint[0] * gridSize,
        prePoint[1] === point[1] ? pointZero[1] : prePoint[1] * gridSize,
      ];
      controlPoints.unshift(pointZero);
    }
    _currentCameFrom = cameFrom[keyOf(prePoint)];
    _current = prePoint;
  }

  // append startPoint
  const realStartPoints = startPoints.map((point) => [point[0] * gridSize, point[1] * gridSize] as Point);
  const startPoint = getNearestPoint(realStartPoints, pointZero, manhattanDistance);

  controlPoints.unshift(startPoint);

  return controlPoints;
};

/**
 * Find the shortest path between a given source node to a destination node according to A* Search Algorithm：https://www.geeksforgeeks.org/a-search-algorithm/
 * @param sourceNode - <zh/> 源节点 | <en/> source node
 * @param targetNode - <zh/> 目标节点 | <en/> target node
 * @param nodes - <zh/> 图上所有节点 | <en/> all nodes on the graph
 * @param config - <zh/> 路由配置 | <en/> router options
 * @returns <zh/> 控制点数组 | <en/> control point array
 */
export function aStarSearch(
  sourceNode: Node,
  targetNode: Node,
  nodes: Node[],
  config: ShortestPathRouterOptions,
): Point[] {
  const startPoint = toVector2(sourceNode.getCenter());
  const endPoint = toVector2(targetNode.getCenter());

  const options = Object.assign(defaultCfg, config) as Required<ShortestPathRouterOptions>;

  const { gridSize } = options;

  const obstacles = options.enableObstacleAvoidance ? nodes : [sourceNode, targetNode];
  const obstacleMap = getObstacleMap(obstacles, options);

  const scaleStartPoint = alignToGrid(startPoint, gridSize);
  const scaleEndPoint = alignToGrid(endPoint, gridSize);

  const startPoints = getBoxPoints(startPoint, sourceNode, options.startDirections, options);
  const endPoints = getBoxPoints(endPoint, targetNode, options.endDirections, options);

  startPoints.forEach((point) => delete obstacleMap[keyOf(point)]);
  endPoints.forEach((point) => delete obstacleMap[keyOf(point)]);

  const openList: Record<string, Point> = {};
  const closedList: Record<string, boolean> = {};
  const cameFrom: Record<string, Point> = {};

  // The movement cost to move from the starting point to the current point on the grid.
  const gScore: Record<string, number> = {};

  // The estimated movement cost to move from the starting point to the end point after passing through the current point.
  // f = g + h
  const fScore: Record<string, number> = {};

  const sortedOpenSet = new SortedArray();

  for (let i = 0; i < startPoints.length; i++) {
    const firstStep = startPoints[i];
    const key = keyOf(firstStep);
    openList[key] = firstStep;
    gScore[key] = 0;
    fScore[key] = estimateCost(firstStep, endPoints, options.distFunc);

    // Push start point to sortedOpenSet
    sortedOpenSet.add({
      id: key,
      value: fScore[key],
    });
  }

  const endPointsKeys = endPoints.map((point) => keyOf(point));

  let remainLoops = options.maximumLoops;
  let current: Point;
  let curCost = Infinity;

  for (const [id, value] of Object.entries(openList)) {
    if (fScore[id] <= curCost) {
      curCost = fScore[id];
      current = value;
    }
  }

  while (Object.keys(openList).length > 0 && remainLoops > 0) {
    const minId = sortedOpenSet.minId(false);
    if (minId) {
      current = openList[minId];
    } else {
      break;
    }
    const key = keyOf(current);

    // If currentNode is final, return the successful path
    if (endPointsKeys.includes(key)) {
      return getControlPoints(current, cameFrom, scaleStartPoint, endPoint, startPoints, scaleEndPoint, gridSize);
    }

    // Set currentNode as closed
    delete openList[key];
    sortedOpenSet.remove(key);
    closedList[key] = true;

    // Get the neighbor points of the next step
    for (const dir of Object.values(options.directionMap)) {
      const neighbor = add(current, [dir.stepX, dir.stepY]);
      const neighborId = keyOf(neighbor);
      if (closedList[neighborId]) continue;

      const directionChange = getDirectionChange(current, neighbor, cameFrom, scaleStartPoint);
      if (directionChange > options.maxAllowedDirectionChange) continue;

      if (obstacleMap[neighborId]) continue; // skip if intersects

      // Add neighbor points to openList, and calculate the cost of each neighbor point
      if (!openList[neighborId]) {
        openList[neighborId] = neighbor;
      }

      const directionPenalties = options.penalties[directionChange];
      const neighborCost =
        options.distFunc(current, neighbor) + (isNaN(directionPenalties) ? gridSize : directionPenalties);
      const costFromStart = gScore[key] + neighborCost;
      const neighborGScore = gScore[neighborId];

      if (neighborGScore && costFromStart >= neighborGScore) continue;

      cameFrom[neighborId] = current;
      gScore[neighborId] = costFromStart;
      fScore[neighborId] = costFromStart + estimateCost(neighbor, endPoints, options.distFunc);

      sortedOpenSet.add({
        id: neighborId,
        value: fScore[neighborId],
      });
    }
    remainLoops -= 1;
  }

  return [];
}

type Item = {
  id: string;
  value: number;
};

/**
 * <zh/> 有序数组，按升序排列
 *
 * <en/> Sorted array, sorted in ascending order
 */
export class SortedArray {
  public arr: Item[] = [];

  private map: Record<string, boolean> = {};

  constructor() {
    this.arr = [];
    this.map = {};
  }

  private _innerAdd(item: Item, length: number) {
    let low = 0,
      high = length - 1;
    while (high - low > 1) {
      const mid = Math.floor((low + high) / 2);
      if (this.arr[mid].value > item.value) {
        high = mid;
      } else if (this.arr[mid].value < item.value) {
        low = mid;
      } else {
        this.arr.splice(mid, 0, item);
        this.map[item.id] = true;
        return;
      }
    }
    this.arr.splice(high, 0, item);
    this.map[item.id] = true;
  }

  /**
   * <zh/> 将新项添加到适当的索引位置
   *
   * <en/> Add the new item to the appropriate index
   * @param item - <zh/> 新项 | <en/> new item
   */
  public add(item: Item) {
    // 已经存在，先移除
    // If exists, remove it
    delete this.map[item.id];

    const length = this.arr.length;
    // 如果为空或者最后一个元素小于当前元素，直接添加到最后
    // If empty or the last element is less than the current element, add to the end
    if (!length || this.arr[length - 1].value < item.value) {
      this.arr.push(item);
      this.map[item.id] = true;
      return;
    }

    // 按照升序排列，找到合适的位置插入
    // Find the appropriate position to insert in ascending order
    this._innerAdd(item, length);
  }

  public remove(id: string) {
    if (!this.map[id]) return;
    delete this.map[id];
  }

  private _clearAndGetMinId() {
    let res;
    for (let i = this.arr.length - 1; i >= 0; i--) {
      if (this.map[this.arr[i].id]) res = this.arr[i].id;
      else this.arr.splice(i, 1);
    }
    return res;
  }

  private _findFirstId() {
    while (this.arr.length) {
      const first = this.arr.shift()!;
      if (this.map[first.id]) return first.id;
    }
  }

  public minId(clear: boolean) {
    if (clear) {
      return this._clearAndGetMinId();
    } else {
      return this._findFirstId();
    }
  }
}

1	import { isNumber } from '@antv/util';	274✔
2	import type { Direction, ID, Node, Point, ShortestPathRouterOptions } from '../../types';
3	import { getBBoxSegments, getBBoxSize, getExpandedBBox, isPointInBBox, isPointOnBBoxBoundary } from '../bbox';	274✔
4	import { getLinesIntersection } from '../line';	274✔
5	import { add, manhattanDistance, toVector2 } from '../vector';	274✔
6
7	const defaultCfg: ShortestPathRouterOptions = {	274✔
8	enableObstacleAvoidance: false,
9	offset: 10,
10	maxAllowedDirectionChange: Math.PI / 2,
11	maximumLoops: 3000,
12	gridSize: 5,
13	startDirections: ['top', 'right', 'bottom', 'left'],
14	endDirections: ['top', 'right', 'bottom', 'left'],
15	directionMap: {
16	right: { stepX: 1, stepY: 0 },
17	left: { stepX: -1, stepY: 0 },
18	bottom: { stepX: 0, stepY: 1 },
19	top: { stepX: 0, stepY: -1 },
20	},
21	penalties: { 0: 0, 90: 0 },
22	distFunc: manhattanDistance,
23	};
24
25	const keyOf = (point: Point) => `${Math.round(point[0])}\|\|\|${Math.round(point[1])}`;	106,692✔
26
27	function alignToGrid(p: Point, gridSize: number): Point;
28	function alignToGrid(p: number, gridSize: number): number;
29	/**
30	* <zh/> 将坐标对齐到网格
31	*
32	* <en/> Align to the grid
33	* @param p - <zh/> 坐标 \| <en/> point
34	* @param gridSize - <zh/> 网格大小 \| <en/> grid size
35	* @returns <zh/> 对齐后的坐标 \| <en/> aligned point
36	*/
37	function alignToGrid(p: number \| Point, gridSize: number): number \| Point {
38	const align = (value: number) => Math.round(value / gridSize);	5,512✔
39	if (isNumber(p)) return align(p);	5,276✔
40	return p.map(align) as Point;	236✔
41	}
42
43	/**
44	* <zh/> 获取两个角度的变化方向，并确保小于 180 度
45	*
46	* <en/ >Get changed direction angle and make sure less than 180 degrees
47	* @param angle1 - <zh/> 第一个角度 \| <en/> the first angle
48	* @param angle2 - <zh/> 第二个角度 \| <en/> the second angle
49	* @returns <zh/> 两个角度的变化方向 \| <en/> changed direction angle
50	*/
51	function getAngleDiff(angle1: number, angle2: number) {
52	const directionChange = Math.abs(angle1 - angle2);	33,266✔
53	return directionChange > Math.PI ? 2 * Math.PI - directionChange : directionChange;	33,266✔
54	}
55
56	/**
57	* <zh/> 获取从 p1 指向 p2 的向量与 x 轴正方向之间的夹角，单位为弧度
58	*
59	* <en/> Get the angle between the vector from p1 to p2 and the positive direction of the x-axis, in radians
60	* @param p1 - <zh/> 点 p1 \| <en/> point p1
61	* @param p2 - <zh/> 点 p2 \| <en/> point p2
62	* @returns <zh/> 夹角 \| <en/> angle
63	*/
64	function getDirectionAngle(p1: Point, p2: Point) {
65	const deltaX = p2[0] - p1[0];	66,532✔
66	const deltaY = p2[1] - p1[1];	66,532✔
67
68	if (!deltaX && !deltaY) return 0;	66,532!
69
70	return Math.atan2(deltaY, deltaX);	66,532✔
71	}
72
73	/**
74	* <zh/> 获取两个点之间的方向变化
75	*
76	* <en/> Get direction change between two points
77	* @param current - <zh/> 当前点 \| <en/> current point
78	* @param neighbor - <zh/> 邻居点 \| <en/> neighbor point
79	* @param cameFrom - <zh/> 来源点 \| <en/> source point
80	* @param scaleStartPoint - <zh/> 缩放后的起点 \| <en/> scaled start point
81	* @returns <zh/> 方向变化 \| <en/> direction change
82	*/
83	function getDirectionChange(
84	current: Point,
85	neighbor: Point,
86	cameFrom: Record<string, Point>,
87	scaleStartPoint: Point,
88	): number {
89	const directionAngle = getDirectionAngle(current, neighbor);	33,266✔
90
91	const currentCameFrom = cameFrom[keyOf(current)];	33,266✔
92	const prev = !currentCameFrom ? scaleStartPoint : currentCameFrom;	33,266✔
93	const prevDirectionAngle = getDirectionAngle(prev, current);	33,266✔
94
95	return getAngleDiff(prevDirectionAngle, directionAngle);	33,266✔
96	}
97
98	/**
99	* <zh/> 获取障碍物地图
100	*
101	* <en/> Get obstacle map
102	* @param nodes - <zh/> 图上所有节点 \| <en/> all nodes on the graph
103	* @param options - <zh/> 路由配置 \| <en/> router options
104	* @returns <zh/> 障碍物地图 \| <en/> obstacle map
105	*/
106	const getObstacleMap = (nodes: Node[], options: Required<ShortestPathRouterOptions>) => {	274✔
107	const { offset, gridSize } = options;	26✔
108	const obstacleMap: Record<string, boolean> = {};	26✔
109
110	nodes.forEach((item: Node) => {	26✔
111	if (!item \|\| item.destroyed \|\| !item.isVisible()) return;	70✔
112	const bbox = getExpandedBBox(item.getRenderBounds(), offset);	70✔
113	for (let x = alignToGrid(bbox.min[0], gridSize); x <= alignToGrid(bbox.max[0], gridSize); x += 1) {	70✔
114	for (let y = alignToGrid(bbox.min[1], gridSize); y <= alignToGrid(bbox.max[1], gridSize); y += 1) {	490✔
115	obstacleMap[`${x}\|\|\|${y}`] = true;	3,430✔
116	}
117	}
118	});
119	return obstacleMap;	26✔
120	};
121
122	/**
123	* <zh/> 估算从起点到多个锚点的最小代价
124	*
125	* <en/> Estimate minimum cost from the starting point to multiple anchor points
126	* @param from - <zh/> 起点 \| <en/> source point
127	* @param anchors - <zh/> 锚点 \| <en/> anchor points
128	* @param distFunc - <zh/> 距离函数 \| <en/> distance function
129	* @returns <zh/> 最小成本 \| <en/> minimum cost
130	*/
131	export function estimateCost(from: Point, anchors: Point[], distFunc: (p1: Point, p2: Point) => number) {	2✔
132	return Math.min(...anchors.map((anchor) => distFunc(from, anchor)));	89,806✔
133	}
134
135	/**
136	* <zh/> 已知一个点集与一个参考点，从点集中找到距离参考点最近的点
137	*
138	* <en/> Given a set of points and a reference point, find the point closest to the reference point from the set of points
139	* @param points - <zh/> 点集 \| <en/> set of points
140	* @param refPoint - <zh/> 参考点 \| <en/> reference point
141	* @param distFunc - <zh/> 距离函数 \| <en/> distance function
142	* @returns <zh/> 最近的点 \| <en/> nearest point
143	*/
144	export function getNearestPoint(points: Point[], refPoint: Point, distFunc: (p1: Point, p2: Point) => number): Point {	2✔
145	let nearestPoint = points[0];	24✔
146	let minDistance = distFunc(points[0], refPoint);	24✔
147	for (let i = 0; i < points.length; i++) {	24✔
148	const point = points[i];	84✔
149	const dis = distFunc(point, refPoint);	84✔
150	if (dis < minDistance) {	84✔
151	nearestPoint = point;	16✔
152	minDistance = dis;	16✔
153	}
154	}
155	return nearestPoint;	24✔
156	}
157
158	/**
159	* Calculate the connection points on the expanded BBox
160	* @param point
161	* @param node
162	* @param directions
163	* @param options
164	*/
165	const getBoxPoints = (	274✔
166	point: Point,
167	node: Node,
168	directions: Direction[],
169	options: Required<ShortestPathRouterOptions>,
170	): Point[] => {
171	// create-edge 生成边的过程中，endNode 为 null
172	if (!node) return [point];	52!
173
174	const { directionMap, offset } = options;	52✔
175	const expandedBBox = getExpandedBBox(node.getRenderBounds(), offset);	52✔
176
177	const points = (Object.keys(directionMap) as Direction[]).reduce<Point[]>((res, directionKey) => {	52✔
178	if (directions.includes(directionKey)) {	208✔
179	const direction = directionMap[directionKey];	184✔
180	const [width, height] = getBBoxSize(expandedBBox);	184✔
181	const otherPoint: Point = [point[0] + direction.stepX * width, point[1] + direction.stepY * height];	184✔
182	const segments = getBBoxSegments(expandedBBox);	184✔
183	for (let i = 0; i < segments.length; i++) {	184✔
184	const intersectP = getLinesIntersection([point, otherPoint], segments[i]);	736✔
185	if (intersectP && isPointOnBBoxBoundary(intersectP, expandedBBox)) {	736✔
186	res.push(intersectP);	184✔
187	}
188	}
189	}
190
191	return res;	208✔
192	}, []);
193
194	if (!isPointInBBox(point, expandedBBox)) {	52!
NEW 195	points.push(point);	×
196	}
197
198	return points.map((point) => alignToGrid(point, options.gridSize));	184✔
199	};
200
201	const getControlPoints = (	274✔
202	current: Point,
203	cameFrom: Record<ID, Point>,
204	scaleStartPoint: Point,
205	endPoint: Point,
206	startPoints: Point[],
207	scaleEndPoint: Point,
208	gridSize: number,
209	) => {
210	const controlPoints: Point[] = [];	22✔
211
212	// append endPoint
213	let pointZero: Point = [	22✔
214	scaleEndPoint[0] === endPoint[0] ? endPoint[0] : current[0] * gridSize,	11!
215	scaleEndPoint[1] === endPoint[1] ? endPoint[1] : current[1] * gridSize,	11!
216	];
217	controlPoints.unshift(pointZero);	22✔
218
219	let _current = current;	22✔
220	let _currentCameFrom = cameFrom[keyOf(_current)];	22✔
221
222	while (_currentCameFrom) {	22✔
223	const prePoint = _currentCameFrom;	444✔
224	const point = _current;	444✔
225	const directionChange = getDirectionChange(prePoint, point, cameFrom, scaleStartPoint);	444✔
226
227	if (directionChange) {	444✔
228	pointZero = [	38✔
229	prePoint[0] === point[0] ? pointZero[0] : prePoint[0] * gridSize,	19✔
230	prePoint[1] === point[1] ? pointZero[1] : prePoint[1] * gridSize,	19✔
231	];
232	controlPoints.unshift(pointZero);	38✔
233	}
234	_currentCameFrom = cameFrom[keyOf(prePoint)];	444✔
235	_current = prePoint;	444✔
236	}
237
238	// append startPoint
239	const realStartPoints = startPoints.map((point) => [point[0] * gridSize, point[1] * gridSize] as Point);	76✔
240	const startPoint = getNearestPoint(realStartPoints, pointZero, manhattanDistance);	22✔
241
242	controlPoints.unshift(startPoint);	22✔
243
244	return controlPoints;	22✔
245	};
246
247	/**
248	* Find the shortest path between a given source node to a destination node according to A* Search Algorithm：https://www.geeksforgeeks.org/a-search-algorithm/
249	* @param sourceNode - <zh/> 源节点 \| <en/> source node
250	* @param targetNode - <zh/> 目标节点 \| <en/> target node
251	* @param nodes - <zh/> 图上所有节点 \| <en/> all nodes on the graph
252	* @param config - <zh/> 路由配置 \| <en/> router options
253	* @returns <zh/> 控制点数组 \| <en/> control point array
254	*/
255	export function aStarSearch(	26✔
256	sourceNode: Node,
257	targetNode: Node,
258	nodes: Node[],
259	config: ShortestPathRouterOptions,
260	): Point[] {
261	const startPoint = toVector2(sourceNode.getCenter());	26✔
262	const endPoint = toVector2(targetNode.getCenter());	26✔
263
264	const options = Object.assign(defaultCfg, config) as Required<ShortestPathRouterOptions>;	26✔
265
266	const { gridSize } = options;	26✔
267
268	const obstacles = options.enableObstacleAvoidance ? nodes : [sourceNode, targetNode];	26✔
269	const obstacleMap = getObstacleMap(obstacles, options);	26✔
270
271	const scaleStartPoint = alignToGrid(startPoint, gridSize);	26✔
272	const scaleEndPoint = alignToGrid(endPoint, gridSize);	26✔
273
274	const startPoints = getBoxPoints(startPoint, sourceNode, options.startDirections, options);	26✔
275	const endPoints = getBoxPoints(endPoint, targetNode, options.endDirections, options);	26✔
276
277	startPoints.forEach((point) => delete obstacleMap[keyOf(point)]);	92✔
278	endPoints.forEach((point) => delete obstacleMap[keyOf(point)]);	92✔
279
280	const openList: Record<string, Point> = {};	26✔
281	const closedList: Record<string, boolean> = {};	26✔
282	const cameFrom: Record<string, Point> = {};	26✔
283
284	// The movement cost to move from the starting point to the current point on the grid.
285	const gScore: Record<string, number> = {};	26✔
286
287	// The estimated movement cost to move from the starting point to the end point after passing through the current point.
288	// f = g + h
289	const fScore: Record<string, number> = {};	26✔
290
291	const sortedOpenSet = new SortedArray();	26✔
292
293	for (let i = 0; i < startPoints.length; i++) {	26✔
294	const firstStep = startPoints[i];	92✔
295	const key = keyOf(firstStep);	92✔
296	openList[key] = firstStep;	92✔
297	gScore[key] = 0;	92✔
298	fScore[key] = estimateCost(firstStep, endPoints, options.distFunc);	92✔
299
300	// Push start point to sortedOpenSet
301	sortedOpenSet.add({	92✔
302	id: key,
303	value: fScore[key],
304	});
305	}
306
307	const endPointsKeys = endPoints.map((point) => keyOf(point));	92✔
308
309	let remainLoops = options.maximumLoops;	26✔
310	let current: Point;
311	let curCost = Infinity;	26✔
312
313	for (const [id, value] of Object.entries(openList)) {	26✔
314	if (fScore[id] <= curCost) {	92✔
315	curCost = fScore[id];	58✔
316	current = value;	58✔
317	}
318	}
319
320	while (Object.keys(openList).length > 0 && remainLoops > 0) {	26✔
321	const minId = sortedOpenSet.minId(false);	14,536✔
322	if (minId) {	14,536!
323	current = openList[minId];	14,536✔
324	} else {
NEW 325	break;	×
326	}
327	const key = keyOf(current);	14,536✔
328
329	// If currentNode is final, return the successful path
330	if (endPointsKeys.includes(key)) {	14,536✔
331	return getControlPoints(current, cameFrom, scaleStartPoint, endPoint, startPoints, scaleEndPoint, gridSize);	22✔
332	}
333
334	// Set currentNode as closed
335	delete openList[key];	14,514✔
336	sortedOpenSet.remove(key);	14,514✔
337	closedList[key] = true;	14,514✔
338
339	// Get the neighbor points of the next step
340	for (const dir of Object.values(options.directionMap)) {	14,514✔
341	const neighbor = add(current, [dir.stepX, dir.stepY]);	58,056✔
342	const neighborId = keyOf(neighbor);	58,056✔
343	if (closedList[neighborId]) continue;	58,056✔
344
345	const directionChange = getDirectionChange(current, neighbor, cameFrom, scaleStartPoint);	32,822✔
346	if (directionChange > options.maxAllowedDirectionChange) continue;	32,822✔
347
348	if (obstacleMap[neighborId]) continue; // skip if intersects	32,746✔
349
350	// Add neighbor points to openList, and calculate the cost of each neighbor point
351	if (!openList[neighborId]) {	32,056✔
352	openList[neighborId] = neighbor;	20,224✔
353	}
354
355	const directionPenalties = options.penalties[directionChange];	32,056✔
356	const neighborCost =
357	options.distFunc(current, neighbor) + (isNaN(directionPenalties) ? gridSize : directionPenalties);	32,056✔
358	const costFromStart = gScore[key] + neighborCost;	32,056✔
359	const neighborGScore = gScore[neighborId];	32,056✔
360
361	if (neighborGScore && costFromStart >= neighborGScore) continue;	32,056✔
362
363	cameFrom[neighborId] = current;	22,796✔
364	gScore[neighborId] = costFromStart;	22,796✔
365	fScore[neighborId] = costFromStart + estimateCost(neighbor, endPoints, options.distFunc);	22,796✔
366
367	sortedOpenSet.add({	22,796✔
368	id: neighborId,
369	value: fScore[neighborId],
370	});
371	}
372	remainLoops -= 1;	14,514✔
373	}
374
375	return [];	4✔
376	}
377
378	type Item = {
379	id: string;
380	value: number;
381	};
382
383	/**
384	* <zh/> 有序数组，按升序排列
385	*
386	* <en/> Sorted array, sorted in ascending order
387	*/
NEW 388	export class SortedArray {	×
389	public arr: Item[] = [];	26✔
390
391	private map: Record<string, boolean> = {};	26✔
392
393	constructor() {
394	this.arr = [];	26✔
395	this.map = {};	26✔
396	}
397
398	private _innerAdd(item: Item, length: number) {
399	let low = 0,	22,632✔
400	high = length - 1;	22,632✔
401	while (high - low > 1) {	22,632✔
402	const mid = Math.floor((low + high) / 2);	62,634✔
403	if (this.arr[mid].value > item.value) {	62,634✔
404	high = mid;	30,854✔
405	} else if (this.arr[mid].value < item.value) {	31,780✔
406	low = mid;	11,504✔
407	} else {
408	this.arr.splice(mid, 0, item);	20,276✔
409	this.map[item.id] = true;	20,276✔
410	return;	20,276✔
411	}
412	}
413	this.arr.splice(high, 0, item);	2,356✔
414	this.map[item.id] = true;	2,356✔
415	}
416
417	/**
418	* <zh/> 将新项添加到适当的索引位置
419	*
420	* <en/> Add the new item to the appropriate index
421	* @param item - <zh/> 新项 \| <en/> new item
422	*/
423	public add(item: Item) {
424	// 已经存在，先移除
425	// If exists, remove it
426	delete this.map[item.id];	22,888✔
427
428	const length = this.arr.length;	22,888✔
429	// 如果为空或者最后一个元素小于当前元素，直接添加到最后
430	// If empty or the last element is less than the current element, add to the end
431	if (!length \|\| this.arr[length - 1].value < item.value) {	22,888✔
432	this.arr.push(item);	256✔
433	this.map[item.id] = true;	256✔
434	return;	256✔
435	}
436
437	// 按照升序排列，找到合适的位置插入
438	// Find the appropriate position to insert in ascending order
439	this._innerAdd(item, length);	22,632✔
440	}
441
442	public remove(id: string) {
443	if (!this.map[id]) return;	14,514!
444	delete this.map[id];	14,514✔
445	}
446
447	private _clearAndGetMinId() {
448	let res;
NEW 449	for (let i = this.arr.length - 1; i >= 0; i--) {	×
NEW 450	if (this.map[this.arr[i].id]) res = this.arr[i].id;	×
NEW 451	else this.arr.splice(i, 1);	×
452	}
NEW 453	return res;	×
454	}
455
456	private _findFirstId() {
457	while (this.arr.length) {	14,536✔
458	const first = this.arr.shift()!;	14,608✔
459	if (this.map[first.id]) return first.id;	14,608✔
460	}
461	}
462
463	public minId(clear: boolean) {
464	if (clear) {	14,536!
NEW 465	return this._clearAndGetMinId();	×
466	} else {
467	return this._findFirstId();	14,536✔
468	}
469	}
470	}

antvis / G6 / 10397997272

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous