v1 e2 e1 v2 v3 e3 e4 f6 f1 e5 f2 e6 f3 v6 v4 e7 e9 e10 f4 v7 e8 v5 f5 v9 e12 e13 v8 e11 e14 v10 Preliminaries Planar straight line graph A planar straight line graph PSLG is a planar embedding of a planar graph G V E with 1 each vertex v V mapped to a distinct point in the plane 2 and each edge e E mapped to a segment between the points for the endpoint vertices of the edge such that no two segments intersect except at their endpoints edge 14 vertex 10 face 6 Observe that PSLG is defined by mapping a mathematical object planar graph to a geometric object PSLG That mapping introduces the notion of coordinates or location which was not present in the graph despite its planarity We will see later that PSLGs will be useful objects For now we focus on a data structure to represent a PSLG Preliminaries Doubly connected edge list DCEL The DCEL data structure represents a PSLG It has one entry edge node in Preparata for each edge in the PSLG Each entry has 6 fields V1 Origin of the edge V2 Terminus destination of the edge implies an orientation F1 Face to the left of edge relative to V1V2 orientation F2 Face to the right of edge relative to V1V2 orientation P1 Index of entry for first edge encountered after edge V1V2 when proceeding counterclockwise around V1 P2 Index of entry for first edge after edge V1V2 when proceeding counterclockwise around V2 v3 f4 e3 V1 V2 F1 F2 P1 P2 f2 e5 v2 e1 v1 e4 f1 e2 v4 f3 e1 v1 v2 f1 f2 e2 e3 e2 v4 v1 f1 f3 e4 e3 v2 v3 f4 f2 e5 Example both PSLG and DCEL are partial 2 13 F6 1 1 F1 9 8 10 7 7 2 F2 12 3 9 4 11 F3 F4 3 6 6 F5 5 5 4 8 Edge V1 V2 LeftF RightF PredE NextE 1 1 2 F6 F1 7 13 2 2 3 F6 F2 1 4 3 3 4 F6 F3 2 5 4 3 9 F3 F2 3 12 5 4 6 F5 F3 8 11 6 6 7 F5 F4 5 10 7 1 5 F5 F6 9 8 8 4 5 F6 F5 3 7 9 1 7 F1 F5 1 6 10 7 8 F1 F4 9 12 11 6 9 F4 F3 6 4 12 9 8 F4 F2 11 13 13 2 8 F2 F1 2 10 Preliminaries Supplementary data structures If the PSLG has N vertices M edges and F faces then we know N M F 2 by Euler s formula DCEL can be described by six arrays V1 1 M V2 1 M LeftF 1 M Right 1 M PredE 1 M and NextE 1 M Since both the number of faces and edges are bounded by a linear function of N we need O N storage for all these arrays Define array HV 1 N with one entry for each vertex entry HV i denotes the minimum numbered edge that is incident on vertex vi and is the first row or edge index in the DCEL where vi is in V1 or V2 column Thus for our example in the preceding slide HV 1 1 2 3 7 5 6 10 4 Similarly define array HF 1 F where F M N 2 with one entry for each face HF i is the minimum numbered edge of all the edges that make the face HF i and is the first row or edge index in the DCEL where Fii is in LeftF or RightF column For our example HF 1 2 3 6 5 1 Both HV and HF can be filled in O N time each by scanning DCEL DCEL operations Procedure EdgesIncident VERTEX in Preparata use a DCEL to report the edges incident to a vertex vj in a PSLG The edges incident to vj are given as indexes to the DCEL entries for those edges in array A 1 3N 6 since M 3N 6 Preliminaries 1 procedure EdgesIncident j VERTEX in text 2 begin 3 a HV j Get first DCEL entry for vj a is index 4 a0 a Save starting index 5 A 1 a 6 i 2 i is index for A 7 if V1 a j then vertex j is the origin 8 a PredE a Go on to next incident edge 9 else vertex j is the destination vertex of edge a 10 a NextE a Go on to next incident edge 11 endif 12 while a a0 do Back to starting edge 13 A i a 14 if V1 a j then 15 a PredE a Go on to next incident edge 16 else 17 a NextE a Go on to next incident edge 18 endif 19 i i 1 20 endwhile 21 end NextE a V2 a a V1 a PredE a Preliminaries DCEL notes If we make the following changes it will become a procedure Faceincident j giving all the edges that constitute a face 3 a HF j And sustitute HV by HF and V1 by F1 A will have a size A 1 N Both EdgesIncident and Faceincident requires time proportional to the number of incident edges reported How does that relate to N the number of vertices in the PSLG We have these facts about planar graphs and thus PSLGs 1 v e f 2 Euler s formula 2 e 3v 6 3 f 2 3e 4 f 2v 4 where v number of vertices N e number of edges M f number of faces F v O N by definition e O N by 2 EdgesIncident requires time O N and DCEL requires storage O N one entry per edge Preliminaries Vector algebra An ordered pair x y can be a point in the plane or a vector x y 0 Vector addition Given vectors a xa ya and b xb yb vector addition is defined as a b xa xb ya yb Geometrically vectors a and b determine a parallelogram with vertices 0 a b and a b a b b a Preliminaries Scalar multiplication Multiplication of vector b by a scalar a real number t Scalar multiplication is defined as tb txb tyb The vector length is scaled by t If t 0 the direction is reversed 2b b 0 b Preliminaries Vector subtraction Given vectors a xa ya and b xb yb vector subtraction is defined as b a b 1 a carried out as b a xb xa yb ya b b a a Vector length Length of vector a xa ya is defined as a sqrt xa2 ya2 Vector Translation q b p a b a o a Let a op and b oq Then b a is a translation of the vector pq at the origin o Thus two line segments having same length and direction are translates of each other and can be identified with the same canonical line segment originating at the origin o Preliminaries Vector direction The direction …