JPS6364902B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a route determination processing system, particularly a route determination processing system for automatically creating a mask diagram in LSI, a printed circuit board pattern diagram, an electric circuit diagram, etc. , based on the coordinates of the start point and end point of the route and the state of existence of the obstacle pattern, exclude in advance the route existence check process for route patterns that cannot exist or do not require the execution of the route existence check process. The present invention relates to a route determination processing system that speeds up route determination processing.

In the process of automatically creating the electrical circuit diagram, the route is automatically determined while avoiding obstacle patterns such as the hatched area, which will be described later with reference to FIG. In determining this route, for example, one of the routes such as routes A to J, which will be described later with reference to FIG. The route is determined according to the route. Of course, as will be described later with reference to FIG.
For example, one edge of the obstacle pattern is the starting point and/or
Or, if it is the end point, select a point extended in a predetermined direction from the start point and/or end point as the temporary start point and/or end point,
A check for the existence of the above routes is also performed.

However, in the conventional case described above, each route pattern is checked one by one, and even if it is foreseeable that a certain route pattern cannot exist, the above check is performed one by one. There is a drawback that the processing speed is slow due to the slowness of the process.

In order to solve the above-mentioned problems, the present invention provides a route that can be foreseen to not exist based on a given obstacle pattern and designated starting and ending points.
The purpose of this method is to exclude patterns in advance and execute the above-mentioned check processing to improve processing speed.
To this end, the route determination processing system of the present invention is characterized by having the configuration described in the claims. This will be explained below with reference to the drawings.

FIG. 1 is an explanatory diagram illustrating the concept of route determination processing executed by the system of the present invention, FIG. 2 is an explanatory diagram illustrating an example route pattern used in the present invention, and FIG. FIG. 4 is an explanatory diagram illustrating problems in route determination processing taken into consideration in the system of the present invention, and FIG. 5 shows the configuration of an embodiment of the present invention.

In FIG. 1, 1-1 to 1-8 represent obstacle patterns, and 2-1, 2-2, . . . represent determined routes, respectively. When determining a route using the system of the present invention, information corresponding to the illustrated obstacle pattern 1-i is stored in advance in the obstacle pattern memory shown in FIG. 5 and is displayed on the display. For example, route 2-
The process starts when the starting point coordinates (x ₁ , y ₁ ) and the ending point coordinates (x ₂ , y ₂ ) are indicated by the light pen in order to determine the coordinates 2.

In determining the above route 2-i, the second
Route patterns such as illustrated route patterns A to J are prepared in advance, and by using any of the route patterns, for example, the above-mentioned starting point (x ₁ , y ₁ ) and ending point (x ₂ , y ₂ ) can be determined. Check whether you can connect the two. Note that the illustrated route patterns I and J have coordinates of the starting point and ending point of x ₁ = x ₂ or
It is selected when y ₁ = y ₂ , and generally route patterns A to H are used to determine the route, so below route pattern A is selected.
to H, problems with route determination by the system of the present invention will be explained.

In determining the above route, it is assumed that a starting point 3 and an ending point 4 are given as shown in FIG. 3A.
In such a case, even with any of the route patterns A to H shown in FIG. 2, the route cannot be determined without being interfered with by the obstacle patterns 1-j and 1-k. In such a case, the starting point 3 is open on the left side in the figure, and the ending point 4 is open on the right side in the figure, so the points 3-0, 3-
1. Set the tentative starting point to other obstacle patterns 1-
1, and similarly select tentative starting points such as points 4-0, 4-1, . . . to determine whether a route based on the above route patterns A to H can be determined. I'll try to find out.
For example, (1) Extend point 4 on the left side of the figure to 4-0, extend point 3 on the right side of the figure to point 3-0, and then
Check whether the route can be determined between 0 and 3-0. In this case, even if route pattern G is used, other routes 2-m
already exists, the corresponding route cannot be determined. Therefore, point 4
Even if you check -1 and point 3-0, point 4-2 and point 3-0, etc., it is foreseeable that the route cannot be determined.

(2) Therefore, the above points 4-1 and 3-0,...
The route determination check based on the above is discontinued, and the score is further extended from 3-0 to 3-1.

(3) Therefore, the route based on points 4-0 and 3-1 is checked, and since the desired route 2-l is found, the route 2-l is determined.

The direction in which the starting point 3, ending point 4, etc. are extended is indicated by extension direction information 1 to 4, as shown in FIG. 3B. In the case of the illustrated starting point 3, the left side in the figure is open, so extension direction information 1 is given, and in the case of the illustrated end point 4, the right side in the figure is open, so it can be considered that the extension direction information 2 is given. .

As described above, in addition to the process of selecting a temporary starting point and temporary ending point and applying a route pattern, the system of the present invention also performs the above-mentioned process when the obstacle pattern and the coordinates of the starting point or temporary starting point and the end point or temporary ending point are given. A route pattern that can never exist among route patterns A to H is predicted and excluded from a route determination check in advance. That is,
Now, if we assume that the starting point 3 and the ending point 4 are given as shown in FIG. 4A, the tentative starting point 3 -
Even if 0, 3-1... or the temporary end points 4-0, 4-1 are extended, it is foreseen that route patterns E and F will never exist. For this purpose, the use of route patterns E and F to perform the above check is excluded in advance.

In addition, in the case shown in Figure 4A, considering that the above-mentioned provisional starting point and provisional ending point are selected, the route
It can be seen that pattern A is included in route pattern C, and route pattern B is included in route pattern D. Therefore, it is not necessary to perform the above-mentioned check using route patterns A and B.

In consideration of these matters, information as shown in FIG. 4B is stored in advance in the processing mode memory shown in FIG. 5, corresponding to the processing mode as shown in FIG. 4A. Note that the reference numeral 5 in the figure represents extension direction information, and the reference numeral 6 represents processing target route pattern information. Then, the route patterns E and F corresponding to the cross marks in the processing target route pattern information and the route patterns A and B corresponding to the circle marks are excluded from the route determination check described above.

As a result, when checking route pattern C, for example, (i) check whether point 3 and point 4-0 can be connected by route pattern C; (ii) if not, check whether point 3 and point 4-0 can be connected by route pattern C; Check point 3 and point 4-1, and (iii) if it is still not possible, check point 3.
and point 4-2, ...(iv) then check point 3-0 and point 4-0, and (v) if not possible, check point 3-0 and point 4-1. ,..., (vi) If the connection cannot be made in the end, it is assumed that the route cannot be determined depending on the route pattern C, and the next route pattern D, for example, is used.
I'm going to check about it.

In the above-mentioned check for route pattern C, etc., it is always checked whether or not there is any value in performing the subsequent check, and if there is no value, the subsequent check is discontinued. In the case of the above route pattern C, the above points 3 and 4-
If the route cannot be determined by applying route pattern C to a series of checks for points 0 to 3 and points 4-n, then tentative starting points 3-0, 3-1, . . . The route cannot be determined in the same way even if ... is taken into account. Therefore, the above check is canceled.

FIG. 5 shows the configuration of an embodiment of the present invention, in which reference numeral 7 is a start point/end point coordinate input unit, and 8 is an obstacle pattern memory, the beginning of which corresponds, for example, to the shaded area shown in FIG. 1. 9 is a route determination calculation unit, 10 is a processing mode selection processing unit, and 11 is a unit in which obstacle patterns such as the following are stored, and as the route is determined, the line on the route is written as an obstacle pattern. Illustrated in the processing mode memory
12, in which extension direction information and processing target route/pattern information as explained with reference to FIG. 3B are stored corresponding to each processing mode of a ₁ to p ₂ ;
1 is a read register; 13 is a direction extension/route determination processing unit which performs route determination check processing as described with reference to FIG. 4A;
4 is a display processing unit which writes the determined route onto the obstacle pattern memory 8;
This refers to the display that displays information based on the content of the .

When the start point (x ₁ , y ₁ ) and end point (x ₂ , y ₂ ) are given from the start point/end point coordinate input unit 7, the obstacle pattern memory 8 is read out correspondingly, and the above points and the obstacle are read out. The positional relationship with the object pattern can be investigated.
Based on this information, the processing mode selection processing unit 10 checks whether the value of x ₁ or x ₂ is larger or not, and also checks which direction is open for each point, and selects the processing mode a ₁ , a ₂ , b ₁ , b ₂ , ...p ₁ ,
Select p ₂ . The processing modes a ₁ , b _{1 ,} . . . p ₁ correspond to the case where y ₁ < y ₂ , and the processing modes _{a 2 ,} b _{2 ,} .

In the case shown in FIG. _{4A , the} processing _mode e ₂ is selected and memory 11 is accessed. As a result, the direction extension/route determination processing unit 13 (i) extends the temporary starting point for point 3 in the direction 2 shown in FIG. 3B, (ii) extends the temporary ending point for point 4 in the direction 1, (iii) Perform the above checks for route patterns C, D, G, and H. The determined route is then written into the obstacle pattern memory 8 and displayed on the display.

As explained above, according to the present invention, it is possible to omit checking for route patterns for which there is no possibility of determining a route when an obstacle pattern and starting and ending points are given. When checking for extension, if there is no possibility of subsequent processing, the subsequent processing is omitted. Therefore, it is possible to increase the route determination processing speed.

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram illustrating the concept of route determination processing executed by the system of the present invention, FIG. 2 is an explanatory diagram illustrating an example route pattern used in the present invention, and FIG. FIG. 4 is an explanatory diagram illustrating problems in route determination processing taken into consideration in the system of the present invention, and FIG. 5 shows the configuration of an embodiment of the present invention. In the figure, 1 is the obstacle pattern, 2 is the route, A,
B is the route pattern, 3 and 4 are the starting point and ending point, 3-0, 3-1, ...4-0, 4-1... are the temporary starting point and temporary ending point, respectively, 5 is the extension direction information, 6
is the route pattern information to be processed, 7 is the start point/end point coordinate input section, 8 is the obstacle pattern memory, 9
Reference numeral 10 represents a route determination calculation section, 10 a processing mode selection processing section, 11 a processing mode memory, 13 a direction extension/route determination processing section, and 14 a display processing section.

Claims (1)

[Claims] 1. A route is determined by selecting one of a plurality of predetermined route patterns on a two-dimensional plane where the obstacle pattern exists, avoiding the obstacle pattern. In the route determination processing system, (1) an obstacle pattern memory that stores obstacle pattern information corresponding to an obstacle pattern given on a two-dimensional plane; Extension direction information that instructs the direction in which to set the starting point and temporary end point, and processing target route pattern information that instructs whether or not to process each of the plurality of route patterns, which cannot exist. A route pattern and a route pattern that corresponds to a predetermined route pattern and does not need to be processed if the predetermined route pattern is set as a processing target are selected in advance from among the plurality of route patterns described above. (3) a processing mode memory that stores a plurality of pieces of route determination processing mode information that instructs route determination processing modes; Based on the coordinate values of the starting point and ending point of the route to be attempted, and the obstacle pattern information, a direction in which a temporary starting point and a temporary ending point can be set is checked among a plurality of predetermined directions for the starting point and ending point. Processing mode selection for selecting specific route determining processing mode information from among the plurality of route determining processing mode information stored in the processing mode memory, based on the direction in which the tentative starting point and tentative ending point can be set as determined by the check. (4) The starting point and/or the starting point and/or the route determination processing mode information selected from the processing mode memory and the direction in which the temporary starting point and the temporary ending point can be set, which are determined by the processing mode selection processing section; Alternatively, by extending from the end point by one unit in the direction specified by the extension direction information, the temporary starting point and/or the temporary ending point are sequentially selected, and the selected starting point or temporary starting point and the end point or temporary ending point are connected. a direction extension/route determination processing unit that checks whether or not a route can be determined and determines a route according to a route pattern designated as a processing target by the processing target route pattern information; (5) A display processing unit that writes the determined route as an obstacle pattern into an obstacle pattern memory and displays the contents of the obstacle pattern memory; and a route determination processing system.