3
$\begingroup$

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.

  1. Each segment must be longer than a given value.
  2. Each segment must be horizontal or vertical. (simplified version)
    Each segment must be parallel or perpendicular to other segments. (general version)

Clarification

  • The problem is in continuous 2D space.
  • To simply the problem, the direction of the first and the last segments is given.

Application

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.
$\endgroup$
  • 1
    $\begingroup$ My first reference is ece.northwestern.edu/~haizhou/357/lec6.pdf I am thinking about using line search. $\endgroup$ – TatePoon Jan 8 '14 at 15:14
  • $\begingroup$ Cool. Thanks. This might be better split into two questions, because I suspect the answer might be quite different for the two problems. Do you have any objection/problem with doing that? Also, now that I see the lecture notes, are you thinking about a discrete 2D grid, or a continuous 2D space? The lecture notes are for a discrete grid. The problem looks quite different in a continuous space. $\endgroup$ – D.W. Jan 8 '14 at 20:17
  • $\begingroup$ It is in continuous 2D space. With the constraint 2, we may construct a grid on the space. The application is about MEP service routing. I will edit the question to add more detail. $\endgroup$ – TatePoon Jan 9 '14 at 1:22
  • $\begingroup$ Thanks. An edit would be great. For constraint 2, it's still not clear to me how you construct a grid: What is the grid spacing? (You haven't restricted segments to have a length that is a multiple of some unit length.) Also, it's not clear what angle the grid should be at. (You haven't specified the angle, so presumably each possible angle yields a possible grid.) $\endgroup$ – D.W. Jan 9 '14 at 1:44
  • $\begingroup$ let us continue this discussion in chat $\endgroup$ – TatePoon Jan 9 '14 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.