Patent Document ID: 7673269
Application ID: 11440679
Patent Status: 1

Claim One:
1. An automatic trace determination apparatus for determining, on a substrate, a trace route that does not intersect with any obstacle on the substrate, automatically and by computation, comprising: first candidate route setting means for, when an obstacle exists on a straight line connecting a starting point and an ending point of a trace, setting a plurality of straight routes originated from the starting point that are tangent to the obstacle as candidate starting routes and a plurality of straight routes originated from the ending point that are tangent to the obstacle as candidate ending routes, and for, when at least an additional obstacle exists on the straight line closer to the ending point, setting a plurality of straight routes originated from the ending point that are tangent to the additional obstacle as secondary candidate ending routes; second candidate route setting means for, when the additional obstacle exists on the straight line, setting a plurality of straight routes each of which is tangent only to each of the obstacle and the additional obstacle and does not intersect with any other obstacle as candidate intermediate routes; tentative route setting means for setting a plurality of tentative routes, each of which includes at least one of the candidate starting routes and one of the candidate ending routes when only the obstacle exists on the straight line, and, for setting a plurality of tentative routes, each of which includes at least one of the candidate starting routes, one of the secondary candidate ending routes and one of the candidate intermediate routes when the additional obstacle exists on the straight line; and optimal route determination means for, among the plurality of tentative routes, determining one of the plurality of tentative routes that has the shortest distance between the starting point and the end point as an optimal route.