Method for routing multiple paths through polygonal obstacles

• US 20060224304A1
• Filed: 03/29/2005
• Published: 10/05/2006
• Est. Priority Date: 03/29/2005
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Sorenson, Michael Whitney, Hudson, Thomas Randall Jr.
• Granted Patent: US 7,512,485 B2
• Time in Patent Office: Days
• US Class Current: 701/202
• CPC Class Codes: G05B 19/4061 Avoiding collision or forbidden zones

Abstract

The present invention provides a method, system and computer program product for routing multiple paths through polygonal obstacles. In a preferred embodiment, the method begins by offsetting the initial paths through the obstacles from the obstacles to form adjusted paths. If it is determined that any adjusted path encounters a new intersection, the adjusted path or paths are modified to form revised paths. The vertices of each obstacle are labeled. All the revised and all the adjusted paths are sorted. Then, according to their sorted order, the revised and the adjusted paths are reconstructed to form offset paths.

Claims

1. A method, in a data processing system, for routing multiple paths through polygonal obstacles, the method comprising:

offsetting initial paths from obstacles to form adjusted paths;

responsive to a determination that the adjusted paths encounter new intersections, modifying the adjusted paths to form revised paths;

sorting all the revised and all the adjusted paths; and

reconstructing the revised and the adjusted paths according to a sorted order to form offset paths.

2. The method of claim 1, wherein the step of determining that the adjusted paths encounter new intersections comprises:

comparing an offset area for each obstacle against a segment offset region, wherein the offset area for each obstacle is the area created by deforming the shape of the obstacles to represent the offset area through which the adjusted paths will be traveling, and wherein the segment offset region is defined by the locations of the original and deformed vertex at either end.

3. The method of claim 2, wherein the step of modifying the adjusted paths to form revised paths, comprises:

splitting a segment into two or more new segments.

4. The method of claim 3, wherein the segment is split into two or more new segments by adding a point that is chosen from one of the four vertices of the obstacle that intersected the segment.

5. The method of claim 4, wherein the offset area encompasses two diagonal lines forming an X and wherein only vertices from a line intersected by the obstacle may be used as the point at which to split the segment.

6. The method of claim 1, further comprising:

labeling vertices of each obstacle.

7. The method of claim 6, wherein each vertex encountered by each revised or adjusted path is labeled either IN or OUT.

8. The method of claim 7, wherein if a vertex'"'"'s obstacle is to the right side of the revised or adjusted path, the vertex will be labeled IN, or, if the revised or adjusted path is inverted, the vertex will be labeled OUT, and wherein if a vertex'"'"'s obstacle is to the left side of the revised or adjusted path, the vertex will be labeled OUT, or, if the revised or adjusted path is inverted, the vertex will be labeled IN.

9. The method of claim 1, wherein the step of sorting all the revised and all the adjusted paths comprises:

comparing the revised and the adjusted paths at one or more shared vertices, wherein the comparison is based on the vertex'"'"'s label and the angle at which the revised or adjusted path goes through the vertex.

10. The method of claim 9, wherein all angles are measured using the right-hand rule, in a counter-clockwise direction, starting from the segment that is closer to the starting point of the revised or adjusted path.

11. The method of claim 7, wherein the step of sorting all the revised and all the adjusted paths comprises:

comparing the revised and the adjusted paths at one or more shared vertices, wherein the comparison is based on the vertex'"'"'s label and the angle at which the revised or adjusted path goes through the vertex.

12. The method of claim 11, wherein all angles are measured using the right-hand rule, in a counter-clockwise direction, starting from the segment that is closer to the starting point of the revised or adjusted path.

13. The method of claim 12, further comprising:

iterating over the revised and the adjusted paths in order; and

offsetting the revised or adjusted path'"'"'s bend point at each vertex.

14. The method of claim 13, further comprising:

responsive to vertices being labeled IN, offsetting the revised and the adjusted paths starting closest to the vertex; and

responsive to vertices being labeled OUT, offsetting the revised and the adjusted paths starting at the point furthest from the vertex.

15. The method of claim 1, further comprising:

generating initial paths through a set of obstacles

16. The method of claim 15, wherein the initial paths are generated incrementally.

17. The method of claim 15, wherein the step of generating the initial paths comprises creating an ellipse containing the starting and ending points of the initial path, wherein the boundaries of the ellipse are determined by multiplying the length of the straight line between the starting and ending point of the initial path by a certain percentage.

18. A data processing system for routing multiple paths through polygonal obstacles, the data processing system comprising:

determining mechanism for determining paths through a set of obstacles;

offsetting mechanism for offsetting the paths from the obstacles to form adjusted paths;

modifying mechanism, responsive to a determination that the adjusted paths encounter new intersections, for modifying the adjusted paths to form revised paths;

labeling mechanism for labeling vertices of each obstacle;

sorting mechanism for sorting all the revised and all the adjusted paths; and

reconstructing mechanism for reconstructing the revised and the adjusted paths according to a sorted order to form offset paths.

19. The data processing system of claim 18, wherein the step of determining that the adjusted paths encounter new intersections comprises:

comparing an offset area for each obstacle against a segment offset region, wherein the offset area for each obstacle is the area created by deforming the shape of all obstacles to represent the offset area through which the adjusted paths will be traveling, and wherein the segment offset region is defined by the locations of the original and deformed vertex at either end.

20. A computer program product, in a computer readable medium, for routing multiple paths through polygonal obstacles, comprising:

first instructions for determining paths through a set of obstacles;

second instruction for offsetting the paths from the obstacles to form adjusted paths;

third instructions, responsive to a determination that the adjusted paths encounter new intersections, for modifying the adjusted paths to form revised paths;

fourth instructions for labeling vertices of each obstacle;

fifth instructions for sorting all the revised and adjusted paths; and

sixth instructions for reconstructing the revised and adjusted paths according to a sorted order to form offset paths.