Patent Document ID: 20060271898
Application ID: 11440679
Patent Status: 0

Claim One:
1. An automatic trace determination apparatus for determining a trace route, on a substrate, that does not intersect with at least one obstacle on such substrate, automatically and by computation, comprising: first candidate route setting means for, when the obstacle exists on a straight line connecting two points that are to be a starting point and an end point of a trace, setting straight routes from said starting point that is tangent to said obstacle as candidate starting routes and setting straight routes from said end point that is tangent to said obstacle as candidate ending routes; second candidate route setting means for, when a plurality of obstacles exist on the straight line connecting between the two points that are to be the starting point and the end point of the trace, setting, with respect to each pair of two of the obstacles, straight routes, each of which is tangent only to such two obstacles and does not intersect with any obstacle other than such two obstacles as candidate intermediate routes; tentative route setting means for setting tentative routes, each of which includes at least any one of said candidate starting routes and any one of said candidate ending routes and, when said plurality of obstacles exist, may further include any one of said candidate intermediate routes selected with respect to each pair of said two obstacles; and optimal route determination means for, among said tentative routes, determining the tentative route that has the shortest distance between said starting point and said end point as an optimal trace route.