Drawing Straight Lines

Carroll, Jeremy J.

HP Development Company

关键词: lines;    pseudo-lines;    polar coordinates;    trilinear coordinates;    non-linear programming;    geometry;   

RP-ID  :  HPL-2000-72

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

We present a graph-drawing algorithm which respects extended co-linearity constraints. These are expressed as a set of 'straight' paths in a planar graph. Constraints of this sort are translated into a set of inequalities over polar coordinates of lines. These inequalities provide necessary and sufficient conditions for the lines to be an appropriate drawing of the graph. Combined with a formula expressing some aesthetic parameter these inequalities then express the graph drawing problem as a classic non-linear program. These inequalities are solved by first solving linear inequalities in the angles, and then tackling the full non-linear program. The solution is a drawing of the graph. The algorithm has been used to draw all the solutions to the 6-Venn triangle problem. 17 Pages