I have the following problem:
In a 2D space with polygonal obstacles, find the shortest path between two given point.
Without additional constraints, we can reduce it to a graph problem by constructing a visibility graph and then solve it by searching.
If the following constraints are added, how can we solve it?
Let's define a path as a set of line segments.
- Each segment must be longer than a given value.
- Each segment must be horizontal or vertical. (simplified version)
Each segment must be parallel or perpendicular to other segments. (general version)
- The problem is in continuous 2D space.
- To simply the problem, the direction of the first and the last segments is given.
This can be considered as a routing problem. I am going to use the algorithm for MEP services routing (e.g. duct, pipe, cable tray).
We need a connector to connect two services when the direction is changed.
- As the connector consumes some space, we have constraint (1).
- As we only have limited choices of the connector (90°, 60°, 45°, 30°), we have constraint (2). To simplified the problem, I only use connector for right angle.