Computational Geometry

Resources

• Check: Geometry Basics
• See the book: “Competitive Programming 3” by Steven Halim, Felix Halim (can bring a hard copy to Regional!)
• Or Prepare your own library!

Basic

1. Line Representation
2. What is the angle between two lines?
3. Are the lines intersected?
4. What is the distance from a point to a line/segment?
5. What is the area of a polygon?

Convex Hull

• Convex: Polygons with angles less than 180 degrees.

• Finding Convex Hull problem: Given $n$ points, find the smallest convex polygon that contains all $n$ points.
  

• Graham Scan

  • Start with the point with smallest y, connect to the next point counter-clock wise. If the polygon becomes not convex, then skip this point.
  • Implementation: keep a stack of all the points
  • Time Complexity: $O(n\log n)$
  • How to find the next point counter-clock wise: cross product
  • See pseudocode @Wikipedia

• Convex Hull Trick

Few Announcement

1. Additional Team Practice on 12:00 - 17: 00 on this Saturday.

Java API

• Calculate distance from a point to a line.

  Line2D line = new Line2D.Double(x1, y1, x2, y2)
  Point2D point = new Point2D.Double(x, y);
  line.ptLineDist(point);
  

• Calculate distance from a point to a line segment.

  line.ptLineDist(point);
  

• Chek whether two lines intersect or not

  line1.intersectsLine(line2);
  

• Check the relative position of a point

  line.relativeCCW(point);
  

• Rotate a point about a point

  Point2D point = new Point2D.Double(x, y);
  AffineTransform rotate = AffineTransform.getRotateInstance(theta, x0, y0);
  point = rotate.transform(point, null);
  

• Compute intersection of two rectangles

  Rectangle rectangle1 = new Rectangle(x1, y1, x2, y2)
  Rectangle rectangle2 = new Rectangle(x3, y3, x4, y4)
  Rectangle intersection = rectangle1.intersection(rectangle2)
  

• Check polygon-point containment

  Polygon polygon = new Polygon();
  polygon.addPoint(x1, y1);
  polygon.addPoint(x2, y2);
  polygon.addPoint(x3, y3);
  polygon.contains(point)
  

• Check rectangle containment

  Area area = new Area();
  area.add(new Area(polygon));
  area.add(new Area(triangle));
  area.add(new Area(rectangle));
  area.contains(new Rectangle(x, y, w, h))