search

ChrisVilches / Algorithms

Solutions for competitive programming problems in various online judges such as Kattis, SPOJ, URI Online Judge, etc.
5 stars 0 forks source link

Map Tiles - method is weird #21

Closed ChrisVilches closed 2 years ago

ChrisVilches commented 2 years ago

kattis/maptiles.cpp

Method generate_offsets is a bit weird. It works and I don't know why. It also has some hard-coded heuristic numbers that shouldn't be there. Make it more exact.

For example:

TILE_N / 2 if (p.x > 6 * tile_x || p.y > 6 * tile_y) return;

I think it's important to fully understand how the method works.

Also optimize it and implement the pruning correctly.

ChrisVilches commented 2 years ago

Almost fixed. Post here all my notes once it's finished. <---- IMPORTANT TODO

Explain how I refactored it, etc.

ChrisVilches commented 2 years ago

Only need to understand the "- pivot_vertex" bit now.

UPDATE: Done. It's just some arithmetic to obtain the final offset.

ChrisVilches commented 2 years ago

Some notes about how to obtain the offsets:

Put a vertex centered on (0, 0), and then slide it across the adjacent edge, while finding these things:

  1. Intersections of grid points with the polygon edges.
  2. Intersections of polygon vertices with grid lines (horizontal and vertical lines).

These are the two things my code does. It was refactored so that it's easier to see what it's doing.