Skip to content

Walk Through Shadow Area

Level: L3-L5 Topics: Graphs, Shortest Path, Dijkstra, Computational Geometry

Problem Statement

A person needs to walk from a start point to an end point on a 2D plane. The plane contains several rectangular shadow areas (axis-aligned rectangles). While inside a shadow area, the person is shielded from the sun. While outside shadow areas, the person is exposed to the sun.

The person can walk in any direction at a constant speed. Find the minimum total distance the person must walk while exposed to the sun (i.e., outside all shadow areas).

Background & Constraints

  • The start and end points are given as (x, y) coordinates.
  • Each shadow area is an axis-aligned rectangle defined by its bottom-left and top-right corners.
  • The person can enter and exit rectangles freely at any point along their boundary.
  • Walking inside a rectangle costs zero "sun distance."
  • Walking outside any rectangle costs the Euclidean distance traveled.
  • Rectangles may or may not overlap.
  • There can be up to a few hundred rectangles.

Examples

Example 1:

Start: (0, 0)
End: (10, 0)
Shadow areas: Rectangle from (3, -1) to (5, 1), Rectangle from (7, -1) to (9, 1)

The person walks from (0,0) to (3,0) in the sun (distance 3),
passes through the first rectangle (free),
walks from (5,0) to (7,0) in the sun (distance 2),
passes through the second rectangle (free),
walks from (9,0) to (10,0) in the sun (distance 1).

Minimum sun exposure distance: 6

Example 2:

Start: (0, 0)
End: (10, 0)
Shadow areas: Rectangle from (2, -2) to (8, 2)

The person walks from (0,0) to (2,0) in the sun (distance 2),
passes through the large rectangle (free),
walks from (8,0) to (10,0) in the sun (distance 2).

Minimum sun exposure distance: 4

Hints & Common Pitfalls

  • Model as a graph problem. The key nodes in the graph are: the start point, the end point, and all corners of every rectangle. Edges between nodes have weight equal to the Euclidean distance spent outside any rectangle along the straight line connecting them.
  • Dijkstra's algorithm on this graph gives the minimum sun-exposure distance.
  • Computing edge weights is the tricky part: for a straight line between two points, you need to subtract the portions of the line that pass through shadow rectangles.
  • Common mistake: Only considering rectangle centers or midpoints of edges. You need all four corners of each rectangle as potential waypoints.
  • Optimization: You don't need edges between all pairs of points. If two points are inside the same rectangle, the edge weight is 0. Prune edges that are clearly suboptimal.
  • If the start or end point is already inside a rectangle, that portion is free.

Follow-Up Questions

  1. How does the solution change if the shadow areas are triangles instead of rectangles?
  2. What if shadow areas can overlap? Does your algorithm still work correctly?
  3. Can you handle the case where the person can also walk along the boundary of rectangles for free (not just through the interior)?
  4. What is the time complexity of your solution in terms of the number of rectangles R?
  5. How would you adapt the solution if there were circular shadow areas?