Asteroids

From programming_contest
Jump to: navigation, search
  1. fix one of the polygons and adjust the other one's path accordingly (just for simplicity)
  2. Determine if the polygons ever intersect
    1. Calculate the path of every vertex on the moving polygon
    2. if every line passes on the same side of every vertex in the other polygon, they don't intersect
      1. use X-product to determine which side of line a point is on
  3. Compute the earliest and latest times any point on the moving polygon intersects a line on fixed polygon.
  4. Ternary search the area of intersection to find maximum. Area is computed by
    1. Finding the intersecting polygon
      1. Find all points of either polygon which are contained (inclusively) in the other or line intersections of the two
        1. use X-product and iterate over all edges of other polygon
        2. if sign is the same, point is contained
      2. Sort points by angle from minimum Y point to get ordering (or just run convex hull on them...we already know they're convex since intersection of two convex things is convex)
      3. run polygon area formula

Will run faster if you only examine times when one vertex crosses an edge of the other polygon