Lecture Notes for CS 245 - Data Struct & Algorithms with Galles at University of San Francisco (USF)

Notes Information

 Material Type: Class Note Professor: Galles Class: CS 245 - Data Struct & Algorithms Subject: Computer Science University: University of San Francisco (CA) Term: Spring 2009 Keywords: Highest PointLowest PointLine SegmentsCross ProductConvex Polygon

Sample Document Text

CS245-2009S-24 Computational Geometry 1 24-0: Cross Products . Given any two points p1 = (x1,y1) and p2 = (x2,y2) . Cross Product: p1×p2 = x1y2?x2y1 p1×p2 = x1y2?x2y1 = ?1?(x2y1?x1y2) = ?p2×p1 24-1: Cross Products p1 p2 p2 p1 p1 2p p1 p2 > 0 p1 p2 < 0 p1 p2 = 0 . Cross Product is positive if p1 is clockwise of p2 . Cross Product is negative if p1 is counterclickwise of p2 . Cross Product is zero if p1 and p2 are colinear 24-2: Cross Products . Given two vectors that share an origin: .???p0p1 and???p0p2 . Is???p0p2 clockwise or counterclockwise relative to???p0p2 ? 24-3: Cross Products p1 p2 p0 p2 p1 p0 Counterclockwise Clockwise 24-4: Cross Products CS245-2009S-24 Computational Geometry 2 . Given two vectors that share an origin: .???p0p1 and???p0p2 . Is???p0p2 clockwise or counterclockwise relative to???p0p2 ? . (p1?p0)×(p2?p0) is positive,???p0p2 is counterclockwise from???p0p1 24-5: Cross Products . Given two line segments p0p1 and p1p2, which direction does angle ne...