Search code examples
algorithmmath2dpolygonlight

Algorithm for inverting a polygon within a rectangle?

I'm trying to make a "flashlight" effect in my game where the player can only see places that are in his line of sight.

I've got most of the effect done by raycasting to each vertex in the game world and added and extra raycasts +-0.0001 rad, then connecting them in clockwise order to form this shape in red. I'm trying to get the inverse of this polygon within the bounds of the rectangular level similar to the "Inverse Selection" option in programs like Photoshop (example)

Solution

  • Construct a set for both rectangle and polygon and calculate the symmetric difference (vertices in either rectangle or polygon but not in both), for example:

    rectangle = [(0, 0), (13, 0), (13, 10), (0, 10)]
polygon = [(0, 5), (0, 10), (2, 6), (8, 6), (11, 0), (13, 0), (13, 10)]
# "^" is the symmetric difference operator in python
set(rectangle) ^ (set(polygon))

    Returns:

    set([(11, 0), (2, 6), (0, 5), (0, 0), (8, 6)])

    Which corresponds to the green area (vertices A, I, E, H, J) in the following picture:

    enter image description here

    Beware that it will get the complement of the red polygon which does not include the intersection with the wall in your original image:

    enter image description here

    If you want your result to be the yellow polygon of the next figure instead:

    enter image description here

    Then you will have to do a rectangle-polygon intersection for every wall/block in the stage with the complement polygon using some method like the ones described in the following question:

    Method to detect intersection between a rectangle and a polygon?