System and method for automatically routing a line in a graphics chart

• US 5,943,062 A
• Filed: 02/13/1996
• Issued: 08/24/1999
• Est. Priority Date: 02/13/1996
• Status: Expired due to Term

• Current Assignee: Igrafx LLC
• Original Assignee: Micrografx LLC
• Inventors: Schanel, Scott J.
• Primary Examiner(s): BUCHEL JR, RUDOLPH JOHN
• Application Number:
  US08/600,887
• Time in Patent Office: 1,288 Days
• Field of Search: 395/140, 395/143, 395/440-43, 364/423.098, 364/424.027, 364/424.032, 364/424.029, 364/424.031
• US Class Current: 345/440
• CPC Class Codes: G06F 2111/12 Symbolic schematics
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

A method for automatically routing a line (54) through a graphics chart (28) from a starting point (70) to an ending point (71) in the chart is provided. The method includes collecting data for the chart (28) representing the location of each symbol (30, 32, 34, 36, 38, 40, & 42) in the chart (28) and the starting (70) and ending (71) points for the line. The method further includes determining a number of paths for the line (54) from the starting point (70) to the ending point (71) and scoring each of the lines. The method also includes selecting the line (54) with the best score as the line to route from the starting point (70) to the ending point (71).

Claims

1. A method for automatically routing a line through a graphics chart from a starting point to an ending point in the chart to connect graphically two symbols, the method comprising the steps of:

collecting data for the chart representing the location of each symbol in the chart and the starting and ending points for the line;

determining a number of paths for the line from the starting point to the ending point;

scoring each of the paths from the determining step;

selecting the path with the best score as the path to route the line from the starting point to the ending point; and

displaying the line along the path with the best score.

2. The method of claim 1 wherein the scoring step further comprises counting the number of points in the path and the number of symbols pierced by the path.

3. The method of claim 1 wherein the selecting step further comprises selecting the path with the lowest score.

4. The method of claim 1 wherein the determining step further comprises determining paths for the line from the starting point to the ending point that do not pierce any symbols in the chart.

5. The method of claim 1 wherein the determining and scoring steps further comprise:

determining each path as a series of orthogonal segments from the starting point to the ending point;

scoring each segment as it is completed and adding the segment'"'"'s score to the path'"'"'s current score;

comparing the path'"'"'s current score to a best score for all other completed paths from the starting point to the ending point; and

abandoning the path if the current path'"'"'s score exceeds the best score.

6. The method of claim 1 wherein the determining, scoring, and selecting steps further comprise:

identifying open corridors in the chart from the starting point to the ending point, wherein each corridor represents a beginning location and an ending location for a segment in the line;

calculating a next direction for the path from the segment'"'"'s ending location based on the segment'"'"'s ending location and the line'"'"'s ending point and the direction at the segment'"'"'s ending location and the direction at the line'"'"'s ending point;

scoring each segment; and

selecting the path whose segments have the best score from the line'"'"'s starting point to the ending point.

7. A method for automatically routing a line through a graphics chart from a starting point to an ending point in the chart, the method comprising the steps of:

collecting data for the chart representing the location of each symbol in the chart and the starting and ending points for the line;

identifying an inner region defined by the starting and the ending points of the line;

extending the inner region;

truncating the extended inner region for any symbols presenting a barrier to routing the line in the extended region;

searching for open corridors in the truncated extended inner region;

calculating a beginning location and an ending location of a segment for each open corridors;

calculating a next direction for the path from the segment'"'"'s ending location based on the segment'"'"'s ending location and the line'"'"'s ending point and the direction at the segment'"'"'s ending location and the direction at the line'"'"'s ending point;

scoring each segment;

selecting the path whose segments have the best score from the line'"'"'s starting point to the ending point; and

displaying the line along the path with the best score.

8. A computer program for automatically routing a line through a graphics chart from a starting point to an ending point in the chart to connect graphically two symbols, the program comprising:

computer implemented instructions for collecting data for the chart representing the location of each symbol in the chart and the starting and ending points for the line;

computer implemented instructions for determining a number of paths for the line as a series of orthogonal segments from the starting point to the ending point;

computer implemented instructions for scoring each of the paths;

computer implemented instructions for selecting the path with the best score as the path to route the line from the starting point to the ending point; and

computer implemented instructions for displaying the line along the path with the best score.

9. The program of claim 8 wherein the computer implemented instructions for scoring each of the paths further comprises instructions for counting the number of points in the path and the number of symbols pierced by the path.

10. The program of claim 8 wherein the computer implemented instructions for selecting the path with the best score further comprises instructions for selecting the path with the lowest score.

11. The program of claim 8 wherein the computer implemented instructions for determining a number of paths further comprises instructions for determining paths for the line from the starting point to the ending point that do not pierce any symbols in the chart.

12. The program of claim 8 wherein the computer implemented instructions for determining and scoring further comprise:

instructions for determining each path as a series of segments from the starting point to the ending point;

instructions for scoring each segment as it is completed and adding the segment'"'"'s score to the current path'"'"'s score;

instructions for comparing the path'"'"'s current score to a best score for all other completed paths from the starting point to the ending point; and

instructions for abandoning the path if the path'"'"'s current score exceeds the best score.

13. The program of claim 8 wherein the computer implemented instructions for determining, scoring, and selecting further comprise:

instructions for identifying open corridors in the chart from the starting point to the ending point, wherein each corridor represents a beginning location and an ending location for a segment in the line;

instructions for calculating a next direction for the path from the segment'"'"'s ending location based on the segment'"'"'s ending location and the line'"'"'s ending point and the direction at the segment'"'"'s ending location and the direction at the line'"'"'s ending point;

instructions for scoring each segment; and

instructions for selecting the path whose segments have the best score from the line'"'"'s starting point to the ending point.

14. A computer program for automatically routing a line through a graphics chart from a starting point to an ending point in the chart. the program comprising:

instructions for collecting data for the chart representing the location of each symbol in the chart and the starting and ending points for the line;

instructions for identifying an inner region defined by the starting and the ending points of the line;

instructions for extending the inner region;

instructions for truncating the extended inner region for any symbols presenting a barrier to routing the line in the extended region;

instructions for searching for open corridors in the truncated extended inner region;

instructions for calculating a beginning location and an ending location of a segment for each open corridors;

instructions for calculating a next direction for the path from the segment'"'"'s ending location based on the segment'"'"'s ending location and the line'"'"'s ending point and the direction at the segment'"'"'s ending location and the direction at the line'"'"'s ending point;

instructions for scoring each segment;

instructions for selecting the path whose segments have the best score from the line'"'"'s starting point to the ending point; and

instructions for displaying the line along the path whose segments have the best score.

15. A computer graphics system for automatically routing a line through a graphics chart from a starting point to an ending point to connect graphically two symbols, the system comprising:

a computer-readable medium;

a processor;

a visual display; and

a computer program encoded on the computer-readable medium for execution on the processor, the computer program comprising;

instructions for collecting data for a chart representing the location of each symbol in the chart;

instructions for determining a number of paths for the line as a series of orthoaonal segments from the starting point to the ending point;

instructions for calculating a score for each of the paths;

instructions for selecting the path with the best score as the path to route the line from the starting point to the ending point; and

instructions for displaying on the visual display the line along the path with the best score.

16. The computer graphics system of claim 15, wherein the instructions for calculating further comprise instructions for counting the number of points in the path.

17. The computer graphics system of claim 15, wherein the instructions for calculating further comprise instructions for counting the number of symbols pierced by the path.

18. The computer graphics system of claim 15, wherein the instructions for determining a number of paths further comprise instructions for determining paths for the line from the starting point to the ending point that do not pierce any symbols in the chart.

19. The computer graphics system of claim 15, wherein the instructions for determining and scoring further comprise:

instructions for determining each path as a series of segments from the starting point to the ending point;

instructions for scoring each segment as it is completed and adding the segment'"'"'s score to the current path'"'"'s score;

instructions for comparing the path'"'"'s current score to a best score for all other completed paths from the starting point to the ending point; and

instructions for abandoning the path if the path'"'"'s current score exceeds the best score.

20. The computer graphics system of claim 15, wherein the instructions for determining, scoring, and selecting further comprise:

instructions for identifying open corridors in the chart from the starting point to the ending point, wherein each corridor represents a beginning location and an ending location for a segment in the line;

instructions for calculating a next direction for the path from the segment'"'"'s ending location based on the segment'"'"'s ending location and the line'"'"'s ending point and the direction at the segment'"'"'s ending location and the direction at the line'"'"'s ending point;

instructions for scoring each segment; and

instructions for selecting the line whose segments have the best score from the line'"'"'s starting point to the ending point.

21. A computer graphics system for automatically routing a line through a graphics chart from a starting point to an ending point, the system comprising:

a computer-readable medium;

a processor;

a visual display; and

a computer program encoded on the computer-readable medium for execution on the processor, the computer program comprising;

instructions for collecting data for a chart representing the location of each symbol in the chart;

instructions for identifying an inner region defined by the starting and the ending points of the line;

instructions for extending the inner region;

instructions for truncating the extended inner region for any symbols presenting a barrier to routing the line in the extended region;

instructions for searching for open corridors in the truncated extended inner region;

instructions for calculating a beginning location and an ending location of a segment for each open corridors;

instructions for calculating a next direction for the path from the segment'"'"'s ending location based on the segment'"'"'s ending location and the line'"'"'s ending point and the direction at the segment'"'"'s ending location and the direction at the line'"'"'s ending point;

instructions for scoring each segment;

instructions for selecting the line whose segments have the best score from the line'"'"'s starting point to the ending point; and

instructions for displaying on the visual display the line along the path with the best score.

22. A computer readable medium encoded with instructions to execute, on a computer, the following steps:

collecting data for a chart representing the location of each symbol in the chart;

obtaining a starting point and an ending point of a line to be routed in the chart to connect graphically two symbols;

determining a number of paths for the line as a series of orthogonal line segments from the starting point to the ending point;

calculating a score for each of the paths, wherein calculating the score includes counting the number of orthogonal line segments;

selecting the path with the best score as the path to route the line from the starting point to the ending point; and

displaying the line along the path with the best score.

23. The computer readable medium of claim 22, wherein the calculating step further comprises counting the number of points in the path.

24. The computer readable medium of claim 22, wherein the calculating step further comprises counting the number of symbols pierced.

25. The computer readable medium of claim 22, wherein the determining step further comprises determining paths for the line from the starting point to the ending point that do not pierce any symbols in the chart.

26. The computer readable medium of claim 22, wherein the determining and calculating steps further comprise:

determining each path as a series of segments from the starting point to the ending point;

scoring each segment as it is completed and adding the segment'"'"'s score to the path'"'"'s current score;

comparing the path'"'"'s current score to a best score for all other completed paths from the starting point to the ending point; and

abandoning the path if the current path'"'"'s score exceeds the best score.

27. The computer readable medium of claim 22, wherein the determining, calculating, and selecting steps further comprise:

identifying open corridors in the chart from the starting point to the ending point, wherein each corridor represents a beginning location and an ending location for a segment in the line;

calculating a next direction for the path from the segment'"'"'s ending location based on the segment'"'"'s ending location and the line'"'"'s ending point and the direction at the segment'"'"'s ending location and the direction at the line'"'"'s ending point;

scoring each segment; and

selecting the path whose segments have the best score from the line'"'"'s starting point to the ending point.

28. A computer readable medium encoded with instructions to execute, on a computer, the following steps:

collecting data for a chart representing the location of each symbol in the chart;

obtaining a starting point and an ending point of a line to be routed in the chart;

identifying an inner region defined by the starting and the ending points of the line;

extending the inner region;

truncating the extended inner region for any symbols presenting a barrier to routing the line in the extended region;

searching for open corridors in the truncated extended inner region;

calculating a beginning location and an ending location of a segment for each open corridors;

calculating a next direction for the path from the segment'"'"'s ending location based on the segment'"'"'s ending location and the line'"'"'s ending point and the direction at the segment'"'"'s ending location and the direction at the line'"'"'s ending point;

scoring each segment; and

selecting the path whose segments have the best score from the line'"'"'s starting point to the ending point;

displaying the line along the path with the best score.