Koofers

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 Point
  • Lowest Point
  • Line Segments
  • Cross Product
  • Convex Polygon
Login / Sign Up to View Document
Preview Page 1Preview Page 2Preview Page 3Preview Page 4Preview Page 5Preview Page 6

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: p1p2 = x1y2?x2y1 p1p2 = x1y2?x2y1 = ?1?(x2y1?x1y2) = ?p2p1 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...
155, "/var/app/current/tmp/"