Generating a lattice graph from line segments

Question

I have two rectangles and I'm trying to find a visually pleasing route between them that is purely rectilinear.

To do that I would like to generate the following lattice / mesh as a graph structure (list of vertices connected to other vertices) so I can run a pathfinding algorithm like Djikstra's on it:

This is gotten by padding each of the rectangles to get a new rectangle (red and blue above), taking the bounding box of these new rectangles (green). Then casting rays from the center of each side of the rectangles and subdividing the lines that these touch.

However I'm having trouble working out how to generate this lattice as a graph structure in an efficient manner.

Ideally I'm looking for an algorithm and a data structure that allows me to build the graph line segment by line segment, subdividing existing line segments (edges) where new line segments intersect them.

Answer 1

I found a solution by tackling this a different way. Instead of thinking in lines instead I gathered all the points from both the start and end of my lines and the points of their intersections.

I then added each unique point as a node to the graph.

Then I made a set for each of all the unique X values in all my nodes and another for the Y values.

I sorted these sets in ascending order.

I then iterated through each possible combination of X and Y values (a small search space because all the lines that created the intersections are orthogonal).

When I found a node, I iterated backwards in the X values until I hit another node and linked them and did the same for the Y values.

Here's my resulting code:

function pointId(x: number, y: number) {
  return `${x},${y}`;
}

function pointsToGraph(points: Point[]) {
  const xValues: Set<number> = new Set();
  const yValues: Set<number> = new Set();
  const graph = createGraph<{ point: Point }>();

  points.forEach((point) => {
    const [x, y] = point;
    xValues.add(x);
    yValues.add(y);
    graph.addNode(pointId(x, y), { point });
  });

  const sortedXValues = Array.from(xValues).sort((a, b) => a - b);
  const sortedYValues = Array.from(yValues).sort((a, b) => a - b);
  for (let i = 0; i < sortedYValues.length; i++) {
    for (let j = 0; j < sortedXValues.length; j++) {
      const x = sortedXValues[j];
      const y = sortedYValues[i];
      const currentId = pointId(x, y);
      // eslint-disable-next-line no-continue
      if (!graph.hasNode(currentId)) continue;

      for (let k = j - 1; k >= 0; k--) {
        const previousXId = pointId(sortedXValues[k], y);
        if (graph.hasNode(previousXId)) {
          graph.addLink(previousXId, currentId);
          break;
        }
      }

      for (let k = i - 1; k >= 0; k--) {
        const previousYId = pointId(x, sortedYValues[k]);
        if (graph.hasNode(previousYId)) {
          graph.addLink(previousYId, currentId);
          break;
        }
      }
    }
  }

  return graph;
}