@tscircuit/routing - npm Package Compare versions

Comparing version 1.0.3 to 1.1.0

dist/index.d.ts

@@ -45,2 +45,3 @@ type Obstacle = {
     grid: Grid;
+    allowDiagonal?: boolean;
 };
@@ -65,3 +66,3 @@ type FoundPath = Path & {
 
-declare const findTwoPointGranularRoute: ({ pointsToConnect, obstacles, grid, }: PathFindingParameters) => PathFindingResult;
+declare const findTwoPointGranularRoute: ({ pointsToConnect, obstacles, grid, allowDiagonal, }: PathFindingParameters) => PathFindingResult;
 
@@ -72,2 +73,3 @@ type Parameters = {
     grid: Grid;
+    allowDiagonal?: boolean;
 };
@@ -81,5 +83,5 @@ /**
  */
-declare const findRoute: ({ pointsToConnect, obstacles, grid, }: Parameters) => PathFindingResult;
+declare const findRoute: ({ pointsToConnect, obstacles, grid, allowDiagonal, }: Parameters) => PathFindingResult;
 
-declare const findTwoPointMixedGranularityRoute: ({ pointsToConnect, obstacles, grid, }: PathFindingParameters) => PathFindingResult;
+declare const findTwoPointMixedGranularityRoute: ({ pointsToConnect, obstacles, grid, allowDiagonal, }: PathFindingParameters) => PathFindingResult;
 
@@ -90,6 +92,19 @@ /**
  */
-declare const findTwoPointNearBiasRoute: ({ pointsToConnect, obstacles, grid, depth, }: PathFindingParameters & {
+declare const findTwoPointNearBiasRoute: ({ pointsToConnect, obstacles, grid, allowDiagonal, depth, }: PathFindingParameters & {
     depth?: number;
 }) => PathFindingResult;
 
-export { FoundPath, Grid, Obstacle, Path, PathFindingParameters, PathFindingResult, Point, findRoute, findTwoPointGranularRoute, findTwoPointMixedGranularityRoute, findTwoPointNearBiasRoute, getPointDistance, isInObstacle };
+/**
+ * Find a the optimal route between two points with as few unnecessary turns
+ * as possible.
+ *
+ * We do this by finding solving for the route, then removing unnecessary turns.
+ *
+ * Note: This approach is inconsistent if you change the order of the points,
+ *       the first point is used as the start point and turns are removed
+ *       by analyzing each of it's next turns.
+ * Note: This isn't guaranteed to be the optimal schematic route.
+ */
+declare const findTwoPointSchematicRoute: ({ grid, obstacles, pointsToConnect, }: PathFindingParameters) => PathFindingResult;
+
+export { FoundPath, Grid, Obstacle, Path, PathFindingParameters, PathFindingResult, Point, findRoute, findTwoPointGranularRoute, findTwoPointMixedGranularityRoute, findTwoPointNearBiasRoute, findTwoPointSchematicRoute, getPointDistance, isInObstacle };

dist/index.js

@@ -36,2 +36,3 @@ var __create = Object.create;
   findTwoPointNearBiasRoute: () => findTwoPointNearBiasRoute,
+  findTwoPointSchematicRoute: () => findTwoPointSchematicRoute,
   getPointDistance: () => getPointDistance,
@@ -71,3 +72,4 @@ isInObstacle: () => isInObstacle
   obstacles,
-  grid
+  grid,
+  allowDiagonal
 }) => {
@@ -126,3 +128,3 @@ if (pointsToConnect.length !== 2)
   const finder = new PF.AStarFinder({
-    diagonalMovement: PF.DiagonalMovement.OnlyWhenNoObstacles
+    diagonalMovement: allowDiagonal ?? true ? PF.DiagonalMovement.OnlyWhenNoObstacles : PF.DiagonalMovement.Never
   });
@@ -196,3 +198,4 @@ const path = finder.findPath(
   distantTarget,
-  distanceToBorder
+  distanceToBorder,
+  allowDiagonal
 }) => {
@@ -257,9 +260,4 @@ const { roundToNearestGridPoint } = computeGridTransform({ grid });
       obstacles,
-      grid
-    });
-    console.log({
-      pointsToConnect: [point, borderPoint],
-      obstacles,
       grid,
-      result
+      allowDiagonal
     });
@@ -281,2 +279,3 @@ if (result.pathFound === true) {
   grid,
+  allowDiagonal,
   depth
@@ -293,3 +292,4 @@ }) => {
       obstacles,
-      grid
+      grid,
+      allowDiagonal
     });
@@ -308,3 +308,4 @@ }
     distanceToBorder,
-    distantTarget: B
+    distantTarget: B,
+    allowDiagonal
   });
@@ -316,3 +317,4 @@ const BBP = findBestBorderTargetPaths({
     distanceToBorder,
-    distantTarget: A
+    distantTarget: A,
+    allowDiagonal
   });
@@ -326,3 +328,4 @@ const routes = [];
         grid,
-        depth: depth + 1
+        depth: depth + 1,
+        allowDiagonal
       });
@@ -347,3 +350,2 @@ if (middleRoute.pathFound === false)
     return { pathFound: false };
-  console.log({ routes });
   return routes.reduce((a, b) => a.length < b.length ? a : b);
@@ -356,3 +358,4 @@ };
   obstacles,
-  grid
+  grid,
+  allowDiagonal
 }) => {
@@ -373,3 +376,4 @@ pointsToConnect.sort((a, b) => {
       obstacles,
-      grid
+      grid,
+      allowDiagonal
     });
@@ -392,3 +396,4 @@ if ("pathFound" in pathResult && pathResult.pathFound) {
   obstacles,
-  grid
+  grid,
+  allowDiagonal
 }) => {
@@ -413,3 +418,4 @@ if (pointsToConnect.length !== 2)
         obstacles,
-        grid
+        grid,
+        allowDiagonal
       });
@@ -420,3 +426,4 @@ const middleEnd = result.points[result.points.length - 2];
         obstacles,
-        grid
+        grid,
+        allowDiagonal
       });
@@ -442,2 +449,144 @@ if (startPath.pathFound && endPath.pathFound) {
 };
+
+// src/lib/is-intersecting-obstacle.ts
+var isIntersectingObstacle = (params) => {
+  const { obstacles, margin = 0 } = params;
+  let { x1, x2, y1, y2, points } = params;
+  const clipLine = (x12, y12, x22, y22, left, right, bottom, top) => {
+    let u1 = 0, u2 = 1, dx = x22 - x12, dy = y22 - y12;
+    const p = [-dx, dx, -dy, dy];
+    const q = [x12 - left, right - x12, y12 - bottom, top - y12];
+    for (let i = 0; i < 4; i++) {
+      if (p[i] === 0) {
+        if (q[i] < 0)
+          return false;
+      } else {
+        const u = q[i] / p[i];
+        if (p[i] < 0 && u1 < u)
+          u1 = u;
+        else if (p[i] > 0 && u2 > u)
+          u2 = u;
+      }
+    }
+    return u1 <= u2;
+  };
+  if (points.length > 2) {
+    return isIntersectingObstacle({
+      points: points.slice(0, 2),
+      obstacles,
+      margin
+    }) && isIntersectingObstacle({
+      points: points.slice(1),
+      obstacles,
+      margin
+    });
+  }
+  if (points) {
+    x1 = points[0].x;
+    x2 = points[1].x;
+    y1 = points[0].y;
+    y2 = points[1].y;
+  }
+  for (const obstacle of obstacles) {
+    const leftEdge = obstacle.center.x - obstacle.width / 2 - margin;
+    const rightEdge = obstacle.center.x + obstacle.width / 2 + margin;
+    const bottomEdge = obstacle.center.y - obstacle.height / 2 - margin;
+    const topEdge = obstacle.center.y + obstacle.height / 2 + margin;
+    if (clipLine(x1, y1, x2, y2, leftEdge, rightEdge, bottomEdge, topEdge)) {
+      return true;
+    }
+  }
+  return false;
+};
+
+// src/lib/remove-unnecessary-points.ts
+var removeUnnecessaryPoints = (points) => {
+  if (points.length <= 3)
+    return points;
+  const newPoints = [points[0]];
+  for (let i = 1; i < points.length - 1; i++) {
+    const P = newPoints[newPoints.length - 1];
+    const A = points[i];
+    const B = points[i + 1];
+    if (P.x === A.x && A.x === B.x) {
+      continue;
+    }
+    if (P.y === A.y && A.y === B.y) {
+      continue;
+    }
+    newPoints.push(A);
+  }
+  newPoints.push(points[points.length - 1]);
+  return newPoints;
+};
+
+// src/lib/find-two-point-schematic-route.ts
+var removeUnnecessaryTurns = ({
+  points,
+  obstacles
+}) => {
+  if (points.length <= 3)
+    return points;
+  const newPoints = [points[0], points[1]];
+  for (let i = 1; i < points.length - 3; i++) {
+    const P = newPoints[i - 1];
+    const A = newPoints[i];
+    const B = points[i + 1];
+    const C = points[i + 2];
+    if (P.x === A.x && A.x === B.x) {
+      newPoints.push(B);
+      continue;
+    }
+    if (P.y === A.y && A.y === B.y) {
+      newPoints.push(B);
+      continue;
+    }
+    const B_opt = A.x === B.x ? { x: C.x, y: A.y } : {
+      x: A.x,
+      y: C.y
+    };
+    const newPathPossible = !isIntersectingObstacle({
+      obstacles,
+      points: [A, B_opt]
+    }) && !isIntersectingObstacle({
+      obstacles,
+      points: [B_opt, C]
+    });
+    if (newPathPossible) {
+      newPoints.push(B_opt);
+    } else {
+      newPoints.push(B);
+    }
+  }
+  newPoints.push(...points.slice(-2));
+  return newPoints;
+};
+var findTwoPointSchematicRoute = ({
+  grid,
+  obstacles,
+  pointsToConnect
+}) => {
+  const route = findTwoPointNearBiasRoute({
+    grid,
+    obstacles,
+    pointsToConnect,
+    allowDiagonal: false
+  });
+  if (!route.pathFound)
+    return { pathFound: false };
+  let currentBest = route.points;
+  while (true) {
+    let newPoints = removeUnnecessaryTurns({ points: currentBest, obstacles });
+    newPoints = removeUnnecessaryPoints(newPoints);
+    if (newPoints.length === currentBest.length) {
+      break;
+    } else {
+      currentBest = newPoints;
+    }
+  }
+  return {
+    ...route,
+    points: currentBest
+  };
+};
 // Annotate the CommonJS export names for ESM import in node:
@@ -449,4 +598,5 @@ 0 && (module.exports = {
   findTwoPointNearBiasRoute,
+  findTwoPointSchematicRoute,
   getPointDistance,
   isInObstacle
 });

package.json

 {
   "name": "@tscircuit/routing",
-  "version": "1.0.3",
+  "version": "1.1.0",
   "description": "",
   "main": "dist/index.js",
   "scripts": {
-    "start": "next dev",
+    "start": "storybook dev -p 6006",
     "build": "tsup ./src/index.ts --dts --outDir ./dist",
     "storybook": "storybook dev -p 6006",
-    "build-storybook": "storybook build"
+    "build-storybook": "storybook build",
+    "test": "ava"
   },
@@ -30,2 +31,3 @@ "keywords": [],
     "@types/react": "18.2.14",
+    "ava": "^5.3.1",
     "next": "^13.4.8",
@@ -32,0 +34,0 @@ "react": "^18.2.0",

README.md

@@ -5,3 +5,3 @@ # @tscircuit/routing
 
-[Examples](https://routing-tsc.vercel.app/) · [TSCircuit](https://tscircuit.com)
+[Examples](https://routing-tsc.vercel.app/) · [TSCircuit](https://tscircuit.com) · [Open in CodeSandbox](https://codesandbox.io/p/github/tscircuit/routing)
 
@@ -8,0 +8,0 @@ This library has deterministic routing algorithms for PCB autorouting inside

src/lib/find-best-border-target-paths.ts

@@ -36,2 +36,3 @@ import { computeGridTransform } from "./compute-grid-transform"
   distanceToBorder,
+  allowDiagonal,
 }: {
@@ -43,2 +44,3 @@ grid: Grid
   distanceToBorder: number
+  allowDiagonal?: boolean
 }): Array<FoundPath & { borderTarget: Point }> => {
@@ -134,3 +136,3 @@ const { roundToNearestGridPoint } = computeGridTransform({ grid })
   // First borderPoint with a path to the distantTarget is the best borderPoint
-  const resultPaths: Array<FoundPath<{ borderTarget: Point }>> = []
+  const resultPaths: Array<FoundPath & { borderTarget: Point }> = []
   for (const borderPoint of closestBorderPoints) {
@@ -141,9 +143,4 @@ const result = findTwoPointGranularRoute({
       grid,
+      allowDiagonal,
     })
-    console.log({
-      pointsToConnect: [point, borderPoint],
-      obstacles,
-      grid,
-      result,
-    })
     if (result.pathFound === true) {
@@ -150,0 +147,0 @@ resultPaths.push({

src/lib/find-route.ts

@@ -10,2 +10,3 @@ import * as PF from "pathfinding"
   grid: Grid
+  allowDiagonal?: boolean
 }
@@ -24,2 +25,3 @@
   grid,
+  allowDiagonal,
 }: Parameters): PathFindingResult => {
@@ -47,2 +49,3 @@ // Sort the points to connect in ascending order of their distances
       grid,
+      allowDiagonal,
     })
@@ -49,0 +52,0 @@

src/lib/find-two-point-granular-route.ts

@@ -15,2 +15,3 @@ import * as PF from "pathfinding"
   grid,
+  allowDiagonal,
 }: PathFindingParameters): PathFindingResult => {
@@ -81,3 +82,6 @@ if (pointsToConnect.length !== 2)
   const finder = new PF.AStarFinder({
-    diagonalMovement: PF.DiagonalMovement.OnlyWhenNoObstacles,
+    diagonalMovement:
+      allowDiagonal ?? true
+        ? PF.DiagonalMovement.OnlyWhenNoObstacles
+        : PF.DiagonalMovement.Never,
   })
@@ -84,0 +88,0 @@ const path = finder.findPath(

src/lib/find-two-point-mixed-granularity-route.ts

@@ -17,2 +17,3 @@ import { computeGridTransform } from "./compute-grid-transform"
   grid,
+  allowDiagonal,
 }: PathFindingParameters): PathFindingResult => {
@@ -41,2 +42,3 @@ if (pointsToConnect.length !== 2)
         grid,
+        allowDiagonal,
       })
@@ -48,2 +50,3 @@ const middleEnd = result.points[result.points.length - 2]
         grid,
+        allowDiagonal,
       })
@@ -50,0 +53,0 @@ if (startPath.pathFound && endPath.pathFound) {

src/lib/find-two-point-near-bias-route.ts

@@ -17,2 +17,3 @@ import { findBestBorderTargetPaths } from "./find-best-border-target-paths"
   grid,
+  allowDiagonal,
   depth,
@@ -33,2 +34,3 @@ }: PathFindingParameters & { depth?: number }): PathFindingResult => {
       grid,
+      allowDiagonal,
     })
@@ -50,2 +52,3 @@ }
     distantTarget: B,
+    allowDiagonal,
   })
@@ -59,2 +62,3 @@
     distantTarget: A,
+    allowDiagonal,
   })
@@ -72,2 +76,3 @@
         depth: depth + 1,
+        allowDiagonal,
       })
@@ -92,4 +97,3 @@ if (middleRoute.pathFound === false) continue
   // Return shortest route
-  console.log({ routes })
   return routes.reduce((a, b) => (a.length < b.length ? a : b))
 }

src/lib/find-two-point-route.ts

@@ -17,4 +17,10 @@ import { findBestBorderTargetPaths } from "./find-best-border-target-paths"
   grid,
+  allowDiagonal,
 }: PathFindingParameters): PathFindingResult => {
-  return findTwoPointGranularRoute({ pointsToConnect, obstacles, grid })
+  return findTwoPointGranularRoute({
+    pointsToConnect,
+    obstacles,
+    grid,
+    allowDiagonal,
+  })
 }

src/lib/index.ts

@@ -8,1 +8,2 @@ export * from "./is-in-obstacle"
 export * from "./find-two-point-near-bias-route"
+export * from "./find-two-point-schematic-route"

src/lib/types.ts

@@ -41,2 +41,3 @@ export type Obstacle = {
   grid: Grid
+  allowDiagonal?: boolean
 }
@@ -43,0 +44,0 @@

No alert changes

Improved metrics

Total package byte prevSize

71366

increased by33.21%

Number of package files

40

increased by33.33%

Lines of code

2435

increased by35.5%

Worsened metrics

Dev dependency count

22

increased by4.76%

No dependency changes