C. General Algorithm for Polygon-Biasing

This algorithm is only valid for convex polygons. For concave polygons (polygons where at least one point has an internal angle ) this algorithm may fail because of point collisions or generation of loops. However, for small bias and suitable geometries the following simple algorithm is applicable.

The line segment can be described by the general parametric line equation:

Furthermore, the normal vector is given by

(C.2) |

and thus the second equation

must be fulfilled too. Substituting the start and end coordinates of the vector , and into (C.1) and (C.3) gives three equations which have to be solved to get the parameters of the line segment.

(C.4) | |

(C.5) | |

(C.6) |

with the solutions

Per definition the normal vector is positive if the line segment is rotated counterclockwise into the normal vector. This means

(C.9) |

which yields the criteria

The relation (C.11) is only fulfilled with the solution

of the (C.8),(C.9). To determine the vector by which each point is shifted during biasing (by the distance d), the two line segments and attached to the point are moved parallel and thus form the new intersection point . The normal vectors remain the same, but the parameters of the general line equations change accordingly to the parallel shift. The initial intersection point is moved by the vector to the point (see Figure C.1). The parameters of the shifted line equations are calculated from their respective line equations and the unchanged line parameters .

(C.13) | |

(C.14) |

The new intersection point must satisfy both line equations and thus by solving the equations the new intersection point coordinates yield

Substituting (C.12),(C.13) in (C.17),(C.18) and using the substitutions , , , , and gives finally

(C.17) | |

(C.18) |

R. Minixhofer: Integrating Technology Simulation into the Semiconductor Manufacturing Environment