[_CDMiwok_01_]<cedarcommon2.0>Lines2d>Lines2d.mesa!1

Lines2d.mesa

Author: Eric Bier on June 4, 1985 4:58:33 pm PDT

Contents: Routines for finding the intersections of various types of lines and line segments

Pier, December 6, 1985 10:01:40 am PST

Bier, June 24, 1987 11:27:38 am PDT

DIRECTORY

Imager, ImagerTransformation, Lines2dTypes;

Lines2d: CEDAR DEFINITIONS =

BEGIN

Point: TYPE = Lines2dTypes.Point;

Edge: TYPE = Lines2dTypes.Edge;

Line: TYPE = Lines2dTypes.Line;

Ray: TYPE = Lines2dTypes.Ray;

Transformation: TYPE = ImagerTransformation.Transformation;

Vector: TYPE = Lines2dTypes.Vector;

Making Lines

CreateEmptyLine: PROC RETURNS [line: Line];

CopyLine: PROC [from: Line, to: Line];

EqualLine: PROC [a: Line, b: Line] RETURNS [BOOL];

Are these lines mathematically identical?

AlmostEqualLine: PROC [a: Line, b: Line, errorDegrees: REAL, errorDistance: REAL] RETURNS [BOOL];

Returns TRUE if the lines differ in slope by no more than errorDegrees and differ in distance from the origin by no more than errorDistance.

These procedures allocate a new Line.

LineFromPoints: PROC [v1, v2: Point] RETURNS [line: Line];

LineFromPointAndVector: PROC [pt: Point, vec: Vector] RETURNS [line: Line];

LineFromCoefficients: PROC [sineOfTheta, cosineOfTheta, distance: REAL] RETURNS [line: Line];

LineFromPointAndAngle: PROC [pt: Point, degrees: REAL] RETURNS [line: Line];

LineNormalToLineThruPoint: PROC [line: Line, pt: Point] RETURNS [normalLine: Line];

LineLeftOfLine: PROC [line: Line, dist: REAL] RETURNS [parallelLine: Line];

LineRightOfLine: PROC [line: Line, dist: REAL] RETURNS [parallelLine: Line];

LineTransform: PROC [fixed: Line, transform: Transformation] RETURNS [transformedLine: Line];

Makes a new line that results by transforming fixed by transform.

Since lines are fairly large data structures, you may prefer to allocate one with CreateEmptyLine and repeatedly fill it with new data instead of allocating a new one each time.

FillLineFromPoints: PROC [v1, v2: Point, line: Line];

FillLineFromPointAndVector: PROC [pt: Point, vec: Vector, line: Line];

FillLineFromCoefficients: PROC [sineOfTheta, cosineOfTheta, distance: REAL, line: Line];

FillLineFromPointAndAngle: PROC [pt: Point, degrees: REAL, line: Line];

FillLineNormalToLineThruPoint: PROC [line: Line, pt: Point, normalLine: Line];

FillLineLeftOfLine: PROC [line: Line, dist: REAL, parallelLine: Line];

FillLineRightOfLine: PROC [line: Line, dist: REAL, parallelLine: Line];

FillLineTransform: PROC [fixed: Line, transform: Transformation, line: Line];

DrawLine: PROC [dc: Imager.Context, line: Line, clippedBy: Imager.Rectangle, strokeWidth: REAL ← 1.0];

transform is applied to fixed. The resulting transformed line is stored in line. It is OK if fixed and line are the same.

Making Edges

CreateEmptyEdge: PROC RETURNS [edge: Edge];

CopyEdge: PROC [from: Edge, to: Edge];

These procedures allocate a new edge.

CreateEdge: PROC [v1, v2: Point] RETURNS [edge: Edge];

EdgeTransform: PROC [fixed: Edge, transform: ImagerTransformation.Transformation] RETURNS [edge: Edge];

Since Edges are fairly large data structures, you may prefer to allocate one with CreateEmptyEdge and repeatedly fill it with new data instead of allocating a new one each time.

FillEdge: PROC [v1, v2: Point, edge: Edge];

FillEdgeTransform: PROC [fixed: Edge, transform: ImagerTransformation.Transformation, edge: Edge];

Making Rays

CreateRay: PROC [basePoint: Point, direction: Vector] RETURNS [ray: Ray];

CreateRayFromPoints: PROC [p1, p2: Point] RETURNS [ray: Ray];

Computations on Lines

Intersections

LineMeetsLine: PROC [line1, line2: Line] RETURNS [intersection: Point, parallel: BOOL];

LineMeetsYAxis: PROC [line: Line] RETURNS [yInt: REAL, parallel: BOOL];

LineMeetsEdge: PROC [line: Line, edge: Edge] RETURNS [intersection: Point, noHit: BOOL];

EdgeMeetsEdge: PROC [e1, e2: Edge] RETURNS [intersection: Point, noHit: BOOL];

Direction and Distance for Lines

DirectionOfLine: PROC [line: Line] RETURNS [direction: Vector];

Returns the unit direction vector of line.

SignedLineDistance: PROC [pt: Point, line: Line] RETURNS [d: REAL];

All lines are directed. For instance, lines that are made with LineFromPoints are directed from the first point to the second point. So they have a left side and a right side. SignedLineDistance returns a positive value if pt is on the left side and a negative value if point is on the right side. For other line types, DirectionOfLine will indicate which way the line is directed.

LineDistance: PROC [pt: Point, line: Line] RETURNS [d: REAL];

Equivalent to ABS[SignedLineDistance[pt, line];

DropPerpendicular: PROC [pt: Point, line: Line] RETURNS [projectedPt: Point];

We drop a normal from the point onto the line and find where it hits. The line equation of the normal we drop can be found using FillLineNormalToLineThruPoint above.

PointOnLine: PROC [line: Line] RETURNS [pt: Point];

Finds any old point on line and returns it.

Distance for Edges

NearestEndpoint: PROC [pt: Point, edge: Edge] RETURNS [endpoint: Point];

DistanceSquaredPointToEdge: PROC [pt: Point, edge: Edge] RETURNS [distanceSquared: REAL];

DistanceSquared[pt, NearestPointOnEdge[pt, edge]].

DistancePointToEdge: PROC [pt: Point, edge: Edge] RETURNS [distance: REAL];

Square root of the above.

DistanceSquaredToNearestEndpoint: PUBLIC PROC [pt: Point, edge: Edge] RETURNS [distanceSquared: REAL];

Computes the distance to each of the two endpoints and takes the smaller of the two.

NearestPointOnEdge: PROC [pt: Point, edge: Edge] RETURNS [onEdge: Point];

Drop a perpendicular to the line of the edge. If the resulting point is on the edge, use it. Otherwise, find the nearest endpoint.

OnEdge: PROC [pt: Point, edge: Edge] RETURNS [BOOL];

Returns TRUE if pt is within a very small distance from edge.

LinePointOnEdge: PROC [pt: Point, edge: Edge] RETURNS [BOOL];

Assumes pt is on the line that includes edge. Is it on edge itself?

Distance for Points

DistancePointToPoint: PROC [p1, p2: Point] RETURNS [distance: REAL];

DistanceSquaredPointToPoint: PROC [p1, p2: Point] RETURNS [distance: REAL];

PointLeftOfLine: PROC [distance: REAL, pOnLine: Point, line: Line] RETURNS [point: Point];

Return a point left of the directed line, on the normal to the line which intersects the line at pOnLine. If distance is positive, the point will be to the left of the directed line.

Ray Routines

LineRayMeetsBox: PROC [ray: Ray, xmin, ymin, xmax, ymax: REAL] RETURNS [count: NAT, params: ARRAY[1..2] OF REAL];

Finds the intersection of a line (the semi-infinite property of rays is not used) with a box. The ray representation is used instead of the line for ease of implementation.

EvalRay: PROC [ray: Ray, param: REAL] RETURNS [point: Point];

Positive values of param gives values on the positive side of the ray base point. Negative values on the negative side.

END.