Okay, let's break down the derivation of the parking rectangle algorithm in an intuitive, step-by-step manner. We'll focus on the core logic and avoid getting bogged down in heavy matrix notation.

The Goal:

Imagine you have a street segment defined by its center point and direction. You want to draw two parking rectangles, one on each side of the street, with a specified width, height, and offset from the street's center.

The Challenge:

The world isn't flat! We're dealing with latitude and longitude on a (roughly) spherical Earth. So, simply adding distances in meters to coordinates won't work accurately, especially as we move further away from the equator.

The Solution: A Series of Transformations

We'll achieve our goal by performing a sequence of transformations, essentially moving between a simplified "flat-Earth" model for calculations and the real-world geographic coordinates.

1. The "Flat-Earth" Playground: Local Cartesian Coordinates

• Imagine a flat plane: We start by pretending the small area around our street segment is perfectly flat. This is our local Cartesian coordinate system (East-North-Up or ENU).
• Origin at the street center: The center point of the street segment is the origin (0, 0) of this plane.
• North and East axes: The Y-axis points North, and the X-axis points East.
• Distances in meters: We can now comfortably work with distances in meters within this flat world.

2. Building the Template Rectangle (Before Scaling and Rotation)

• Unit rectangle centered at origin: We start with a simple rectangle with a width of W and height of H centered at the origin of our flat plane. The vertices of the rectangle are given by the matrix V_base.
• Offsetting the rectangle: We want to place the rectangle adjacent to the street center line, not directly on it. The K parameter is the distance from the street center line to the nearer edge of the rectangle.

  V_base = [[-W/2, K],
            [-W/2, K+H],
            [W/2, K+H],
            [W/2, K]]
  

  • Each row in this matrix is a vertex (x, y).
  • -W/2 and W/2 define the left and right edges of the rectangle respectively.
  • K shifts the rectangle upwards (northwards) by K meters.
  • K + H defines the top edge of the rectangle.
  • This ensures that the rectangle is placed adjacent to the street center line, with its bottom edge K meters away from the origin.

3. Rotating the Rectangle to Align with the Street

• Street orientation (θ): We know the direction the street is pointing, measured as an angle θ clockwise from true north.

• Rotation matrix (R(θ)): We use a standard rotation matrix to rotate our template rectangle by this angle θ counter-clockwise in our flat plane:

  R(θ) = [[cos(θ), -sin(θ)],
         [sin(θ), cos(θ)]]
  

• Applying the rotation: Multiply the V_base matrix by the transpose of the rotation matrix (R(θ)^T) to get the rotated vertices (V_rotated). The transpose is necessary due to how matrix multiplication works with row and column vectors. We are essentially rotating each vertex of the rectangle.

  • V_rotated = V_base * R(θ)^T

4. Stepping Back into the Real World: Geographic Normalization

• Meters to degrees: Now we need to convert our rotated rectangle's coordinates from meters (in our flat plane) to latitude and longitude (degrees).

• Geographic Normalization Matrix (G): This matrix handles the conversion. It's based on the idea that a meter corresponds to a different change in latitude/longitude depending on where you are on Earth.

  G = [[1/g_lat, 0],
       [0, 1/g_lon]]
  

  where:

  g_lat = R_lat * (π / 180)
  g_lon = R_lon * cos(v_lat * π / 180) * (π / 180)
  

  • R_lat and R_lon are the Earth's radii of curvature at the street's latitude (v_lat). These values are calculated for an accurate ellipsoidal model of the Earth.
  • g_lat tells you how many meters correspond to one degree of latitude change.
  • g_lon tells you how many meters correspond to one degree of longitude change. The cos(v_lat) term accounts for the fact that longitude lines converge as you move towards the poles.
  • (π / 180) converts degrees to radians, as required by the trigonometric functions and the definition of the radius of curvature.

• Applying the normalization: Multiply V_rotated by the transpose of the G matrix (G^T) to get the geographically normalized vertices (V_geo). Again, the transpose is needed for correct matrix multiplication.

  • V_geo = V_rotated * G^T

5. Placing the Rectangle on the Map

• Translation to the street center: We now have the coordinates of the rectangle in degrees, but they're still relative to our flat plane's origin. We need to shift them to the actual street center point.
• Adding the street center coordinates (v): Simply add the latitude and longitude of the street center point v to each vertex in V_geo. This places the rectangle correctly on the map.
  • R₁ = V_geo + v (this is element-wise addition).

6. Creating the Symmetric Rectangle on the Other Side of the Street

• Mirroring: To get the second rectangle on the opposite side of the street, we want to mirror the first one across the street center.
• Rotation by 180 degrees: In our flat plane, this is equivalent to rotating the V_rotated vertices by 180 degrees before we convert them to geographic coordinates. Rotating by 180 degrees is the same as multiplying by -1.
• Applying the same steps: We then apply the geographic normalization (G^T) and translation (v) as before.
  • R₂ = -V_rotated * G^T + v

In a Nutshell

1. Build: Create a template rectangle with the desired dimensions, offset from the origin in a simplified, flat coordinate system.
2. Rotate: Rotate the rectangle to align with the street's direction.
3. Convert: Transform the rotated coordinates from meters to latitude and longitude.
4. Place: Translate the rectangle to the actual street center location.
5. Mirror: Generate a symmetric rectangle on the other side of the street by rotating the rotated coordinates by 180 degrees before converting and translating.

Important Notes

• Approximation: The "flat-Earth" assumption introduces errors, especially for large rectangles or at higher latitudes.
• Radii of Curvature: Using accurate values for the Earth's radii of curvature is crucial for minimizing errors.
• Matrix Operations: The order of matrix multiplication and the use of transposes are essential for the correct geometric transformations.

This intuitive explanation should give you a good grasp of the underlying logic of the parking rectangle algorithm. By understanding each step, you can better appreciate the algorithm's strengths, limitations, and how to use it effectively.