Patent ID: 8713505

Claim:
A pattern generation method comprising: extracting a first segment which is not on grids by a segment extraction unit; extracting a second segment opposite to the first segment by the segment extraction unit; determining whether the second segment is on the grids by a determination unit; selecting, from the grids, a first grid which is adjacent to the first segment and a second grid which is adjacent to the second segment so that a space between the first grid and the second grid is closest to a target line width which is a line width between the first segment and the second segment by a grid shift unit, if the second segment is not on the grids; and shifting the first segment onto the first grid and the second segment onto the second grid by the grid shift unit, wherein: the shifting of the first segment and the second segment includes, obtaining a space between each of the grids adjacent to the first segment and each of the grids adjacent to the second segment; comparing the space between each of the grids adjacent to the first segment and each of the grids adjacent to the second segment with the target line width; and selecting the first grid and the second grid from each of the grids adjacent to the first segment and each of the grids adjacent to the second segment respectively after the comparing.