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 ]; 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]; PolygonExtractor: PROC [v, w: VertexHandle] RETURNS [ImagerPolygonAndStateList]; ClearVisitedFields: PROC [v, w: VertexHandle]; 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]; FindVertexForPoint: PROC [v: VertexHandle, test: Point] RETURNS [w: VertexHandle]; SetPolygonState: PROC [v, w: VertexHandle, state: CSI.State, setLRE: BOOL _ FALSE]; ThreeOrMoreVertices: PROC [w: VertexHandle] RETURNS [BOOL]; END. VRVHandleUtils.mesa Last Edited by: Arnon, February 26, 1985 2:21:53 pm PST General notes on this Vertex-Adjacency data structure: (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. Test whether points p and q are the same. Test whether the edge [p,q] is vertical. No check is made for coincidence of p and q. Compute the square of the distance between two points. Determine the relation of the point test to the line [start, end]. The line may be trivial, i.e. start = end; if so, and if test # start = end, then LEFTOFLINE returned. Determine if the test point lies in the sector of a polygon determined by leftvertex, rightvertex, centerOfMass A sector is defined as the (interior of the) triangle having as vertices the center of mass of p, the ith vertex of p (rightvertex as you face out from the center of mass) and the i+1st vertex of p (leftvertex). Rational arithmetic version. Check edges [p1, p2] and [q1, q2] for proper intersection, i.e. check whether the endpoints of each edge are distinct, whether the edges have at most one point in common, and if so, that the common point is interior to both edges; if no proper intersection, then just classifies the edge relationship and returns intPoint _ [0, 0]. Assuming that w is a vertex on the outline of some Figure containing at least two vertices, find the vertex v which precedes w in the counterclockwise ordering of vertice.s Assuming that [v,w] is an edge on the outline of some Figure containing at least two vertices, find the vertex z which precedes w in the counterclockwise ordering of vertices (we think of this counterclockwise ordering as being defined with respect to the INTERIOR of the figure on whose outline w lies). Create an empty VertexHandle. vhandlefirst is thought of as being on the polygonal outline of a figure. The new vertex [x,y] is added so as to come after the vertex which precedes vhandlefirst (call it vhandlelast), and before vhandlefirst, in the counterclockwise ordering of vertices. vhandlefirst is returned, so that subsequently added vertices will always be inserted just before vhandlefirst. Sausify: PROC [brush: VertexHandle, start, end: Point] RETURNS [sausage: VertexHandle]; Cartesian Product of brush and vector [start, end] to make a sausage. brush is assumed to be a convex polygon with counterclockwise ordered vertices. sausage is the same sort of polygon. Ngon: PROC [N: CARDINAL, xCenter, yCenter, radius: RN.RatNum] RETURNS [VertexHandle]; Make an N-gon as per the input parameters DiamondLeftUp: PROC [v, w: VertexHandle, state: CSI.State]; Make a diamond of height scale and width 1/2 scale, downwards from top. Slope: PROC[p1, p2: Point] RETURNS [slope: RN.RatNum]; Compute the slope of the line determined by two points. Bundle up two RatNums as an point Bundle up two Reals as a (rational) point Constructor: PROC [convexpolygon: Imager.Trajectory, interiorstate, exteriorstate: CSI.State ] RETURNS [v: VertexHandle]; Convert a Trajectory representing a convex polygon to the Combiner's data structure. Assumes that the vertices occur in clockwise order in the trajectory, that is, if we peel off convexpolygon.lp, then go back to convexpolygon.prev, peel off its lp, etc. that we get the vertices in counterclockwise order. [v, w] is a (counterclockwise) directed edge of an internal polygon. Obtain the polygon's state. [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. [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. Dump a VertexHandle to a file. Does Depth First Search. Convert an IOVertexHandleList to a VertexHandle. The particular VertexHandle v returned will be chosen so as to be on the outline of the figure. numberVertices is the number of vertices encountered in the converted IOVertexHandleList. Search vHList for the element whose index is key; [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. Find vertex closest to test point [v, w] is a (counterclockwise) directed edge of an internal polygon. Its state is set. setLRE controls whether leftRegionExterior fields are set to FALSE. Κυ˜šœ™J™7J™—šΟk ˜ Jšœœœ˜Jšœœœ˜Jšœœ ˜Jšœœœ˜Jšœ˜Jšœ˜—šœœ ˜ Jšœ˜J˜—šœœœœ ˜-J˜—Jšœœœ œ ˜*Jšœ œœœ˜ J˜Jšœœœœ˜.J•StartOfExpansion[]šœœœ˜ šœœœ˜J˜JšœœΟc&˜6Jšœ'ž8˜_Jšœ œž-˜Jšœ7™7—Jš Ÿœœœœœœ ˜ošŸœœ œ#œ˜eJšœκ™κ—šŸ œœ!œœ˜LJšœ1™1J™—JšŸ œœœ˜IJšŸœœœœœœœ˜tšŸœœ#œœ˜cKšœκ™κK™—šŸœœ œ˜RKšœ!™!—š Ÿœœœœœ˜SKšœš™šK˜—KšŸœœœœ˜;šœ˜J™——…—Ξ;