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)ClarificationThe problem is in continuous 2D space.To simply the problem, the direction of the first and the last segments is given.ApplicationThis 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.
Any algorithm for finding Euclidean shortest path with specific constraints in 2D?
algorithms;computational geometry;shortest path