Method for routing breakouts

Claim 2

A computer-assisted method for routing breakouts between pins and vias, comprising: reading coordinates of pins and vias from memory of a programmed computer system; creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from the coordinates of the pins and the vias; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; and routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair.

Claim 6

A computer-readable medium on which is stored a computer program for routing breakouts, said computer program comprising instructions, which when executed by a computer, perform the steps of: creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from coordinates of the pins and the vias; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; and routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair.

Claim 7

A computer-readable medium on which is stored a computer program for routing breakouts, said computer program comprising instructions, which when executed by a computer, perform the steps of: creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from coordinates of the pins and the vias; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; and routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair.

Claim 8

A computer-assisted method for routing breakouts between pins and vias, comprising: reading coordinates of pins and vias from memory of a programmed computer system; creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from the coordinates of the pins and the vias; determining whether the pins nest within the vias, and determining whether the vias nest within the pins; and if either the pins nest the vias, or the vias nest the vias, then splitting the first and second convex hull structures so that the pins and vias do not nest; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; and routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair.

Claim 9

A computer-assisted method for routing breakouts between pins and vias, comprising: reading coordinates of pins and vias from memory of a programmed computer system; creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from the coordinates of the pins and the vias; determining whether the pins nest within the vias, and determining whether the vias nest within the pins; and if either the pins nest the vias, or the vias nest the vias, then splitting the first and second convex hull structures so that the pins and vias do not nest; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; and routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair.

Claim 10

A computer-assisted method for routing breakouts between pins and vias, comprising: reading coordinates of pins and vias from memory of a programmed computer system; creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from the coordinates of the pins and the vias; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair; and swapping the first and second routing paths to reduce total routing length.

Claim 11

A computer-assisted method for routing breakouts between pins and vias, comprising: reading coordinates of pins and vias from memory of a programmed computer system; creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from the coordinates of the pins and the vias; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair; and swapping the first and second routing paths to reduce total routing length.

Claim 12

A computer-assisted method for routing breakouts between pins and vias, comprising: reading coordinates of pins and vias from memory of a programmed computer system; creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from the coordinates of the pins and the vias; creating a binary tree structure representing an ordered set of the pins and vias, the binary tree structure having leaves representing the coordinates of pins or vias, wherein the first and second convex hull structures are created from the binary tree structure; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; and routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair.

Claim 13

A computer-assisted method for routing breakouts between pins and vias, comprising: reading coordinates of pins and vias from memory of a programmed computer system; creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from the coordinates of the pins and the vias; creating a binary tree structure representing an ordered set of the pins and vias, the binary tree structure having leaves representing the coordinates of pins or vias, wherein the first and second convex hull structures are created from the binary tree structure; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; and routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair.

Claim 14

A computer-assisted method for routing breakouts between pins and vias, comprising: reading coordinates of pins and vias from memory of a programmed computer system; creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from the coordinates of the pins and the vias; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; and routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair; wherein the first and second convex hull structures are binary tree structures including: leaves having data fields for representing the coordinates of pins or vias; nodes having data fields for representing an upper convex hull for the descendant leaves of the nodes; and a root node having a data field for representing an upper convex hull of all active pins or vias in the convex hull structure.

Claim 15

A computer-assisted method for routing breakouts between pins and vias, comprising: reading coordinates of pins and vias from memory of a programmed computer system; creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from the coordinates of the pins and the vias; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; and routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair; wherein the first and second convex hull structures are binary tree structures including: leaves having data fields for representing the coordinates of pins or vias; nodes having data fields for representing an upper convex hull for the descendant leaves of the nodes; and a root node having a data field for representing an upper convex hull of all active pins or vias in the convex hull structure.

Claim 16

A computer-assisted method for routing breakouts between pins and vias, comprising: reading coordinates of pins and vias from memory of a programmed computer system; creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from the coordinates of the pins and the vias; before creating the first and second convex hull structures, placing the vias on a mounting surface according to predefined design constraints, and storing the coordinates of the vias; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; and routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair.

Claim 17

A computer-assisted method for routing breakouts between pins and vias, comprising: reading coordinates of pins and vias from memory of a programmed computer system; creating a first convex hull structure representing the pins and a second convex hull structure representing the vias from the coordinates of the pins and the vias; before creating the first and second convex hull structures, placing the vias on a mounting surface according to predefined design constraints, and storing the coordinates of the vias; finding a common tangent between the first and second convex hull structures having a first endpoint in the first convex hull structure and a second endpoint in the second convex hull structure; storing the first and second endpoints of the common tangent between the first and second convex hull structures as a first matching pin and via pair; removing the first and second endpoints from the first and second convex hull structures respectively; reconstructing the first and second convex hull structures to find first and second reconstructed convex hull structures; finding a common tangent between the first and second reconstructed convex hull structures having a first endpoint in the first reconstructed convex hull structure and a second endpoint in the second reconstructed convex hull structure; storing the first and second endpoints of the common tangent between the first and second reconstructed convex hull structures as a second matching pin and via pair; and routing a first path between the first pin and via pair, and routing a second path between the second pin and via pair.