<> <> <<>> DIRECTORY Rope USING [ROPE], IO USING [STREAM], RatNums USING [RatNum], Imager USING [VEC, Trajectory], ClientStateInfo; RVHandleUtils: CEDAR DEFINITIONS IMPORTS ClientStateInfo = BEGIN OPEN CSI: ClientStateInfo, RN: RatNums; Point: TYPE = RECORD[ x , y : RN.RatNum ]; PointList: TYPE = LIST OF Point; VertexHandleList: TYPE = LIST OF VertexHandle; VertexHandle: TYPE = REF Vertex; Vertex: TYPE = RECORD[ coordinates: Point, index: INT _ 0, -- used only for display and debugging adjacentVertices: AdjacencyHandleList, -- circular list of adjacent vertices in clockwise order visited: BOOL -- flag used by depth-first search algorithms ]; AdjacencyHandleList: TYPE = LIST OF AdjacencyHandle; AdjacencyHandle: TYPE = REF Adjacency; Adjacency: TYPE = RECORD[ vertex: VertexHandle, leftState: CSI.State, -- state of the region to the left of edge to this point leftRegionExterior: BOOLEAN, -- true if region to the left of edge to this point is exterior to the (convex) outline of the containing figure. leftRegionVisited: BOOLEAN, -- mark visit to region to the left of edge to this vertex (used mainly by search algorithms) intersectionPolygonEdge: BOOLEAN -- mark an edge that lies along the intersection polygon formed by the input polygon and the outline of the current figure ]; <> <<(1) Note that we keep track of the outline of the current figure (by setting leftRegionExterior fields of appropriate edges); the reasons for doing so are: to be able to do point location with respect to wedges of the current outline, and to be able to terminate depth first searches of the internal polygons of the current figure. Outline maintainance necessitates updating when new edges (i.e. directed edge pairs) are added which enlarge the outline: one of the new edges must be identified as an outline edge (its leftRegionExterior field set), and (possibly) certain edges which previously had their leftRegionExterior field set must have them cleared. >> <<>> <<(2) We store leftState to be consistent with the convention of counterclockwise orientation of polygon edges: when the edges on the boundary of a polygon have a counterclockwise orientation, the state of the polygon is the state to the left of an edge.>> PointLineRelation: TYPE = {ONLINE, LEFTOFLINE, RIGHTOFLINE}; PointDirectedEdgeRelation: TYPE = {BEFORESTART, EQUALSTART, BETWEENSTARTEND, EQUALEND, AFTEREND, LEFTOFEDGE, RIGHTOFEDGE}; PointSectorRelation: TYPE = {EQUALCOM, RIGHTSPOKEINTERIOR, EQUALRIGHTVERTEX, LEFTSPOKEINTERIOR, EQUALLEFTVERTEX, POLYGONEDGEINTERIOR, SECTORINTERIOR, RIGHTRAYINTERIOR, LEFTRAYINTERIOR, SUBTENDINTERIOR, RIGHTOFSUBTEND, LEFTOFSUBTEND}; DirectedEdgeIntersectionStatus: TYPE = LIST OF DirectedEdgeIntersectionStatusValue; DirectedEdgeIntersectionStatusValue: TYPE = { START1EQEND1, START2EQEND2, START1EQSTART2, START1EQEND2, END1EQSTART2, END1EQEND2, START1INEDGE2, END1INEDGE2, START2INEDGE1, END2INEDGE1, OVERLAP, PROPERINTERSECT, DISJOINT}; -- outcome of intersection computation vertexIndex: CARDINAL; -- count of vertices allocated ImagerPolygonAndStateList: TYPE = LIST OF ImagerPolygonAndStateHandle; ImagerPolygonAndStateHandle: TYPE = REF ImagerPolygonAndStateRecord; ImagerPolygonAndStateRecord: TYPE = RECORD [ trajectory: Imager.Trajectory, -- should be a convex polygon. state: CSI.State -- state of the polygon ]; IOVertexHandleList: TYPE = LIST OF IOVertexHandle; IOVertexHandle: TYPE = REF IOVertex; IOVertex: TYPE = RECORD[ coordinates: Point, index: INT _ 0, -- expected to be used only in debugging or verbosity modes adjacentVertices: IOAdjacencyHandleList -- circular list, vertices in clockwise order ]; IOAdjacencyHandleList: TYPE = LIST OF IOAdjacencyHandle; IOAdjacencyHandle: TYPE = REF IOAdjacency; IOAdjacency: TYPE = RECORD[ vertex: INT _ 0, -- use of INT here rather than VertexHandle distinguishes IO* structures leftState: CSI.State, -- state of the region to the left of edge to this point leftRegionExterior: BOOLEAN -- true if region to the left of edge to this point is exterior ]; ConvexPolygonOnOutline: PROC[ prew2, w2, prew1, w1: VertexHandle, outline:BOOL _ TRUE] RETURNS [BOOL]; CenterOfMass: PROC[ v, w : VertexHandle, outline: BOOL ] RETURNS [Point]; ConvexPolygon: PROC[ v, w : VertexHandle, outline: BOOL ] RETURNS [BOOL]; ConvexHull: PROC [L: PointList] RETURNS [M: PointList]; PointEqual: PROC[ p, q: Point ] RETURNS[BOOLEAN]; <> VerticalEdge: PROC[ p, q: Point ] RETURNS[BOOLEAN]; <> DistanceSquare: PROC[ p, q: Point ] RETURNS[d: RN.RatNum]; <> PointLineTest: PROC [start, end, test: Point] RETURNS[PointLineRelation]; <> PointDirectedEdgeTest: PROC [start, end, test: Point] RETURNS[PointDirectedEdgeRelation]; PointSectorTest: PROC [rightvertex, leftvertex, centerOfMass, test: Point] RETURNS[PointSectorRelation]; <> FindSubtendForPoint: PROC[v, w: VertexHandle, centerOfMass, test: Point, outline: BOOL ] RETURNS [status: PointSectorRelation, t, u: VertexHandle]; XOR: PROC[a, b: BOOLEAN] RETURNS[BOOLEAN]; DEISValuePresent: PROC[v: DirectedEdgeIntersectionStatusValue, L: DirectedEdgeIntersectionStatus] RETURNS[BOOLEAN]; IntersectDirectedEdges: PROC [start1, end1, start2, end2: Point] RETURNS [outcome: DirectedEdgeIntersectionStatus, intPoint: Point ]; <> StepVertex: PROC[ v1, w1: VertexHandle, outline: BOOL] RETURNS [ v2, w2: VertexHandle]; NextVertex: PROC[ v, w: VertexHandle, outline: BOOL] RETURNS [ z: VertexHandle]; PreviousVertex: PROC[v, w: VertexHandle, outline: BOOL] RETURNS [z: VertexHandle]; NextOutlineVertex: PROC[ v, w: VertexHandle] RETURNS [ z: VertexHandle]; NextPolygonVertex: PROC[ v, w: VertexHandle] RETURNS [ VertexHandle]; PreviousOutlineVertex: PROC [w: VertexHandle] RETURNS [v:VertexHandle]; PreviousPolygonVertex: PROC [v, w: VertexHandle] RETURNS [z:VertexHandle]; <> NewPrevOutlineVertex: PROC [v, w: VertexHandle] RETURNS [z: VertexHandle]; <> FindAdjacency: PROC[ v, w: VertexHandle] RETURNS [vTow, wTov: AdjacencyHandle]; InitVertexHandle: PROC RETURNS [VertexHandle]; <> AddVertexToPolygon: PROC [vhandlefirst: VertexHandle, x,y: RN.RatNum, state: CSI.State _ CSI.defaultState] RETURNS [VertexHandle]; <> <<>> <> <> <<>> <> <> Diamond: PROC [top: Point, scale: RN.RatNum, state: CSI.State] RETURNS [diamond:VertexHandle]; DiamondRightUp: PROC [v, w: VertexHandle, state: CSI.State]; <> <> DiamondGrid: PROC [top: Point, scale: RN.RatNum, state: CSI.State, size: CARDINAL, visitedValue: BOOL] RETURNS [diamondGrid: VertexHandle]; <> <> MakePointFromRatNums: PROC[x1, y1: RN.RatNum] RETURNS [p: Point]; <> MakePointFromReals: PROC[x1, y1: REAL] RETURNS [p: Point]; <> <<>> ImagerVecFromPoint: PROC[p: Point] RETURNS [q: Imager.VEC]; <> <> <<>> GetPolygonState: PROC [v, w: VertexHandle] RETURNS [state: CSI.State]; <<[v, w] is a (counterclockwise) directed edge of an internal polygon. Obtain the polygon's state.>> <<>> PolygonExtractor: PROC [v, w: VertexHandle] RETURNS [ImagerPolygonAndStateList]; <<[v,w] is a counterclockwise oriented edge of a polygon contained in the outline of the current figure. Extract the internal polygons and their state from a VertexHandle, assumed by this particular Extractor to be an VertexHandle. Uses Depth First Search. The state of the exterior of the plane structure is assumed to be recorded in the backgroundColor field of the CombinerViewerDataRec, and hence is not retrieved by PolygonExtractor.>> ClearVisitedFields: PROC [v, w: VertexHandle]; <<[v,w] is a counterclockwise oriented edge of a polygon contained in the outline of the current figure. Clear the leftRegionVisited fields of all edges of all polygons interior to a VertexHandle, assumed by this particular ClearVisitedFields to be an VertexHandle. Uses Depth First Search.>> AppendImagerPolygonAndStateList: PROC [l1: ImagerPolygonAndStateList, l2: ImagerPolygonAndStateList _ NIL] RETURNS[val: ImagerPolygonAndStateList]; DumpVertexHandle: PROC [v: VertexHandle, filename: Rope.ROPE]; <> ReadIOVHLFromFile: PROC [filename: Rope.ROPE, MessageStream: IO.STREAM] RETURNS [ioVHList: IOVertexHandleList]; VHandleFromIOVHL: PROC [ioVHList: IOVertexHandleList] RETURNS [v: VertexHandle, numberVertices: INT]; <> SearchVHL: PROC [vHList: VertexHandleList, key: INT] RETURNS [VertexHandle]; <> <<>> ReverseVHL: PROC [list: VertexHandleList] RETURNS[val: VertexHandleList]; VertexVerifyIOVHLFromFile: PROC [filename: Rope.ROPE, MessageStream: IO.STREAM] RETURNS [ maxVertexIndex: CARDINAL]; FindPolygonForPoint: PROC [v, w: VertexHandle, test: Point] RETURNS [ok: BOOL, y, z: VertexHandle]; <<[v, w] is a (counterclockwise) directed edge of an internal polygon. If test is found within the closure of the current structure (i.e. in its interior or on its outline), then ok = TRUE, and [y, z] is a (counterclockwise) directed edge of the unique internal polygon in whose interior test lies, or a (counterclockwise) directed edge of an internal polygon in whose boundary test lies. If test is not found within the closure of the current structure, then ok = FALSE, y = v, and z = w. >> <<>> FindVertexForPoint: PROC [v: VertexHandle, test: Point] RETURNS [w: VertexHandle]; <> SetPolygonState: PROC [v, w: VertexHandle, state: CSI.State, setLRE: BOOL _ FALSE]; <<[v, w] is a (counterclockwise) directed edge of an internal polygon. Its state is set. setLRE controls whether leftRegionExterior fields are set to FALSE.>> ThreeOrMoreVertices: PROC [w: VertexHandle] RETURNS [BOOL]; END. <<>>