Stair-step line constructing algorithm

Question

For a 2D graph, there are two points, A and B, and a set of rectangles (R₀, .., R_k-1).

Starting conditions:

A and B are not inside any rectangle.
Edges of each rectangle are parallel to X-Y axes.

I have to develop an algorithm that constructs a stair-climbing (or step function) line.

The line has to satisfy these constraints:

all parts of step line are parallel to X-Y axes
the step line doesn't intersect any rectangle
step line has minimal length
step line has minimal amount of kinks (corners) among all step lines of minimal length

I've read some books on computational geometry, but did not find an algorithm to solve this problem.

What if you have a situation where you can reduce the number of links, but only by increasing the length? — Scott Hunter
This is a simple visability graph search in a 4-connected (manhattan-distance) descrete 2D space. In the general sense, using A*in a 4-connected space with manhattan-distance as the heuristic/cost should give you the correct solution if distance/kinks are equally weighted. — aruisdante
If kinks are weighted more than minimum path length, you need to bias the cost function to account for changes in direction and make them more expensive. — aruisdante
How many rectangles are we talking about? A* seems to be a good idea. You can execute it on a rectilinear grid. The x-coordinates of all rectangles' corners will be the vertical splits of the grid and the y-coordinates the horizontal ones. You just have to efficiently check if a vertex is blocked by a rectangle. This can be achieved with appropriate hash sets. — Nico Schertler
@Alexander_KH I've tried to improve the formatting and wording of your question, please let me know if I made any mistakes. — mctylr

Nico Schertler Nico Schertler · Accepted Answer · 2014-07-29T11:27:13

Consider the following scenario:

+----+         B
|    |
|    |    
+----+    +-------+
          |       |
  +---+   |       |
  |   |   |       |
  +---+   +-------+

   A

There is always a minimal path that goes along the rectangles' edges. In the optimal solution, you could always push a line segment farther to the center of a passing without changing the path length, because the segment before the pushed line segment will be changed by the negative amount of the segment after the pushed line segment.

So in order to run A*, you can generate a grid with vertices at the intersection of rows or columns on which the rectangles' corners lie, plus A and B:

o-oo-oo---o----o--o
|    ||   |    |  |
|    ||   |    |  |
o-oo-oo---o----o--o
| || ||   |       |
o-oo-oo---o    o  o
| |   |   |       |
o-oo-oo---o----o--o
| || ||   |    |  |        
o-oo-oo---o----o--o

You could even remove vertices that lie within a rectangle. Run A* on that grid with the manhattan distance. In order to reduce kinks, you could introduce an artificial penalty. I.e. when you proceed from a vertex to another vertex in the other direction than you came from, add a very small penalty (e.g. 0.01). This allows you to include kink minimization without changing the penalty for the path length (for sufficiently small kink penalty).

Stair-step line constructing algorithm

1 Answers