The U-Shape That Wasn't — RPolygon Even-Index Representation

---

# 🐛 The U-Shape That Wasn’t

### Debugging `RPolygon`’s even-index representation  
### across C++, Python, and Rust

📐 🔍 🛠️ 🧪

@luk036 · 2026 · ⏱️ 30 min

---

### 🗺️ Agenda

**Part 1 — The symptom** 🐛

- One U-shape, one piece
- The first suspect

**Part 2 — The representation** 🧩

- Even-index storage
- Implicit odd vertices
- The 2/3-node base cases

]
.pull-right[

**Part 3 — Re-testing & fixes** 🛠️

- C++: no algorithm change needed
- Python: input-mutation fix
- Rust: stub → implementation

**Part 4 — Verification** 🧪

**Part 5 — Lessons** 💡

]

---

## Part 1 — The Symptom 🐛

---

### 📋 The bug report

```python
from physdes.point import Point
from physdes.rpolygon import rpolygon_is_convex
from physdes.rpolygon_cut import rpolygon_cut_convex

full = [Point(x, y) for x, y in [
    (0, 0), (3, 0), (3, 3), (2, 3),
    (2, 1), (1, 1), (1, 3), (0, 3),
]]

print(rpolygon_is_convex(full))               # False
print(len(rpolygon_cut_convex(full, True)))   # 1
```

- 🐛 The polygon is correctly non-convex, yet the cut returns one piece.
- ❓ Is the algorithm broken — or is the input not what we think it is?

---

### 🕵️ The first suspect

For the **expanded** 8-vertex polygon, every turn is 90°:

$$
\color{firebrick}{v_{1x}v_{2x} = 0},
\qquad
\color{firebrick}{v_{1y}v_{2y} = 0}
$$

- The direction-reversal guard never fires.
- `find_concave_point` returns `None`.
- The polygon is declared “convex” and returned whole.

That explains the symptom — but only if the expanded list is the real input.

---

## Part 2 — The Representation 🧩

---

### 🧠 What `RPolygon` actually stores

$$
\color{steelblue}{RPolygon} =
\{\color{steelblue}{v_0},
\color{steelblue}{v_2},
\color{steelblue}{v_4},
\ldots\}
$$

- Only **even-index vertices** are stored.
- The odd-index vertices are **implicit**.
- This is a 50% storage reduction.

$$
\color{seagreen}{v_{2i+1}} =
\begin{cases}
\color{seagreen}{(x_{2i},\; y_{2i+2})} & \text{vertical edge}\\
\color{seagreen}{(x_{2i+2},\; y_{2i})} & \text{horizontal edge}
\end{cases}
$$

---

### 🖼️ Expanded vs compressed U-shape

<p align="center">
<svg width="440" height="390" viewBox="0 0 440 390" xmlns="http://www.w3.org/2000/svg" style="background:#fafafa;border:1px solid #d0d0d0;border-radius:8px">
  <text x="12" y="24" font-family="sans-serif" font-size="15" font-weight="bold" fill="#2e3440">Expanded U-shape: 8 vertices · 4 stored</text>
  <g stroke="#e5e9f0" stroke-width="1">
    <line x1="60" y1="60" x2="300" y2="60"/>
    <line x1="60" y1="140" x2="300" y2="140"/>
    <line x1="60" y1="220" x2="300" y2="220"/>
    <line x1="60" y1="300" x2="300" y2="300"/>
    <line x1="60" y1="60" x2="60" y2="300"/>
    <line x1="140" y1="60" x2="140" y2="300"/>
    <line x1="220" y1="60" x2="220" y2="300"/>
    <line x1="300" y1="60" x2="300" y2="300"/>
  </g>
  <path d="M60,300 L300,300 L300,60 L220,60 L220,220 L140,220 L140,60 L60,60 Z" fill="#81a1c1" fill-opacity="0.30" stroke="#2e3440" stroke-width="3"/>
  <g fill="#9aa5b1" stroke="#4c566a" stroke-width="1.5">
    <circle cx="300" cy="300" r="4"/>
    <circle cx="220" cy="60" r="4"/>
    <circle cx="140" cy="220" r="4"/>
    <circle cx="60" cy="60" r="4"/>
  </g>
  <g fill="#5e81ac" stroke="#2e3440" stroke-width="2">
    <circle cx="60" cy="300" r="7"/>
    <circle cx="300" cy="60" r="7"/>
    <circle cx="220" cy="220" r="7"/>
    <circle cx="140" cy="60" r="7"/>
  </g>
  <g font-family="sans-serif" font-size="12" font-weight="bold" fill="#2e3440">
    <text x="42" y="322">v0</text>
    <text x="310" y="50">v2</text>
    <text x="232" y="216">v4</text>
    <text x="120" y="48">v6</text>
  </g>
  <g font-family="sans-serif" font-size="12" fill="#4c566a">
    <text x="20" y="360">● large: stored even-index vertex</text>
    <text x="235" y="360">● small: implicit odd-index vertex</text>
  </g>
</svg>
</p>

```text
expanded: (0,0),(3,0),(3,3),(2,3),(2,1),(1,1),(1,3),(0,3)
stored:   (0,0),      (3,3),      (2,1),      (1,3)
```

---

### 🧩 The 2/3-node base cases were the clue

.mermaid[
<pre>
graph LR
    R["Rectangle"] --> R2["2 stored points"]
    M["Monotone / L"] --> M3["3 stored points"]
    style R fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style R2 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style M fill:#ffe0b2,stroke:#ef6c00,stroke-width:3px
    style M3 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
</pre>
]

- These are **not** degenerate cases.
- A 2-point rectangle expands back to four corners.
- A 3-point piece expands back to a monotone corner sequence.

---

### 🔁 What `to_polygon` reconstructs

Consecutive stored points may be diagonal. The implicit corner is inserted:

.mermaid[
<pre>
graph LR
    A["(0,0)"] -->|"stored"| B["(3,3)"]
    A --> C["(3,0)"]
    C --> B
    style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style B fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style C fill:#fff9c4,stroke:#f57f17,stroke-width:3px
</pre>
]

- `(0,0) → (3,3)` becomes `(0,0) → (3,0) → (3,3)`.
- The diagonal edges in the input are expected, not a bug.

---

## Part 3 — Re-testing with the Correct Input 🛠️

---

### ✅ Compressed U-shape: the original algorithm works

<p align="center">
<svg width="420" height="380" viewBox="0 0 420 380" xmlns="http://www.w3.org/2000/svg" style="background:#fafafa;border:1px solid #d0d0d0;border-radius:8px">
  <text x="12" y="24" font-family="sans-serif" font-size="15" font-weight="bold" fill="#2e7d32">Compressed U-shape: 2 pieces · total area 7</text>
  <g stroke="#e5e9f0" stroke-width="1">
    <line x1="60" y1="60" x2="300" y2="60"/>
    <line x1="60" y1="140" x2="300" y2="140"/>
    <line x1="60" y1="220" x2="300" y2="220"/>
    <line x1="60" y1="300" x2="300" y2="300"/>
    <line x1="60" y1="60" x2="60" y2="300"/>
    <line x1="140" y1="60" x2="140" y2="300"/>
    <line x1="220" y1="60" x2="220" y2="300"/>
    <line x1="300" y1="60" x2="300" y2="300"/>
  </g>
  <path d="M220,220 L220,300 L300,300 L300,60 L220,60 Z" fill="#b48ead" fill-opacity="0.60" stroke="#2e3440" stroke-width="3"/>
  <path d="M220,220 L140,220 L140,60 L60,60 L60,300 L220,300 Z" fill="#a3be8c" fill-opacity="0.55" stroke="#2e3440" stroke-width="3"/>
  <line x1="220" y1="220" x2="220" y2="300" stroke="#d08770" stroke-width="5" stroke-dasharray="9,5"/>
  <g fill="#5e81ac" stroke="#2e3440" stroke-width="2">
    <circle cx="220" cy="220" r="6"/>
    <circle cx="140" cy="60" r="6"/>
    <circle cx="60" cy="300" r="6"/>
    <circle cx="220" cy="300" r="6"/>
    <circle cx="300" cy="60" r="6"/>
  </g>
  <text x="82" y="185" font-size="13" font-family="sans-serif" fill="#2e7d32" font-weight="bold">3 stored points · area 4</text>
  <text x="238" y="150" font-size="13" font-family="sans-serif" fill="#6b4a8a" font-weight="bold">2 stored points · area 3</text>
  <text x="228" y="262" font-size="12" font-family="sans-serif" fill="#d08770">cut</text>
</svg>
</p>

| Piece | Stored vertices | Area |
|:------|:----------------|:----:|
| L-shape | `(2,1), (1,3), (0,0)` | 4 |
| Rectangle | `(2,0), (3,3)` | 3 |

- **C++ original algorithm already does this.**
- Both pieces pass `rpolygon_is_convex`.
- Total area = 7 = original.

---

### 🐍 Python: convex worked; explicit exposed a mutation bug

```python
def rpolygon_cut_impl(lst, is_anticlockwise, recur):
    lst = list(lst)          # do not mutate caller's list
    ...
```

- The cut appends new points to `lst`.
- Without the copy, calling convex first corrupted the list used by explicit.
- After the copy, both variants return **2 pieces** with total area **7**.

| Call sequence | Before | After |
|:--------------|:------:|:-----:|
| convex → explicit, same list | area 1 | area 7 |

---

### 🦀 Rust: a stub became a compressed-representation cut

.mermaid[
<pre>
graph TD
    S["Rust: stub"] --> I["recursive cut\non compressed points"]
    I --> C["convex"]
    I --> E["explicit"]
    I --> X["implicit\n(still stub)"]
    style S fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style I fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style C fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style E fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style X fill:#eeeeee,stroke:#616161,stroke-width:3px
</pre>
]

- Ported `find_concave_point`, `find_min_dist_point`, `insert_cut`, and the index cycle.
- Preserved the 2/3-node base cases.
- `rpolygon_cut_implicit` remains a stub.

---

### 🇹 T-shape: already orthogonally convex

- A T is both x-monotone and y-monotone.
- Its compressed form has **4 stored points**.
- The explicit cut correctly returns **1 piece** (area 14).
- The C++ tests cover T-shape both orientations.

```text
compressed T: (2,0), (4,4), (6,5), (0,4)
```

---

### 🧪 Tests had to use the compressed representation

| Project | Test input | Result |
|:--------|:-----------|:-------|
| C++ | compressed U / F / T | 7 cases · 90 assertions |
| Python | compressed U / F / comb / serpentine | 12 tests passed |
| Rust | compressed U | 2 tests passed |

- The earlier full-vertex tests were testing the wrong representation.
- Existing test files were left unchanged.

---

## Part 4 — Verification 🧪

---

### 🛠️ C++ verified with xmake

```bash
xmake build test_recti
xmake run test_recti "--test-case=*compressed*"
xmake run test_recti
```

- Compressed suite: **7 cases, 90 assertions**
- Full suite: **141 cases, 816 assertions**
- **0 failures**
- No CMake used.

---

### 🐍 Python verified with pytest

- New compressed tests: **12 passed**
- Existing cut tests: **8 passed**
- Full suite: **627 passed**
- One unrelated pre-existing failure:
  - `test_vector2_hypothesis.py::test_scalar_multiplication_additivity`
- ⚠️ Explicit on the large serpentine stress shape still recurses; the stress test exercises the convex cut.
- `mypy` and `pre-commit`: pass

---

### 🦀 Rust verified with cargo

| Check | Result |
|:------|:-------|
| unit tests | 299 passed |
| cross-language tests | 11 passed |
| regression tests | 2 passed |
| doctests | 66 passed |
| `cargo fmt --check` | pass |
| `cargo clippy` | only 2 pre-existing `vlsi_ops` warnings |

**378 tests passed.**

---

<p align="center">
<svg width="700" height="130" viewBox="0 0 700 130" xmlns="http://www.w3.org/2000/svg" style="background:#fafafa;border:1px solid #d0d0d0;border-radius:8px">
  <rect x="15" y="24" width="156" height="78" rx="12" fill="#c8e6c9" stroke="#2e7d32" stroke-width="3"/>
  <text x="93" y="58" font-family="sans-serif" font-size="14" font-weight="bold" fill="#1b5e20" text-anchor="middle">C++ compressed</text>
  <text x="93" y="80" font-family="sans-serif" font-size="13" fill="#1b5e20" text-anchor="middle">7 cases · 90 asserts</text>
  <rect x="186" y="24" width="156" height="78" rx="12" fill="#c8e6c9" stroke="#2e7d32" stroke-width="3"/>
  <text x="264" y="58" font-family="sans-serif" font-size="14" font-weight="bold" fill="#1b5e20" text-anchor="middle">C++ full</text>
  <text x="264" y="80" font-family="sans-serif" font-size="13" fill="#1b5e20" text-anchor="middle">141 cases · 816 asserts</text>
  <rect x="357" y="24" width="156" height="78" rx="12" fill="#fff9c4" stroke="#f57f17" stroke-width="3"/>
  <text x="435" y="58" font-family="sans-serif" font-size="14" font-weight="bold" fill="#e65100" text-anchor="middle">Python</text>
  <text x="435" y="80" font-family="sans-serif" font-size="13" fill="#e65100" text-anchor="middle">627 pass · 1 unrelated</text>
  <rect x="528" y="24" width="156" height="78" rx="12" fill="#c8e6c9" stroke="#2e7d32" stroke-width="3"/>
  <text x="606" y="58" font-family="sans-serif" font-size="14" font-weight="bold" fill="#1b5e20" text-anchor="middle">Rust</text>
  <text x="606" y="80" font-family="sans-serif" font-size="13" fill="#1b5e20" text-anchor="middle">378 tests pass</text>
</svg>
</p>

---

## Part 5 — Lessons 💡

---

### 💡 What we learned

.mermaid[
<pre>
graph LR
    L1["Representation"] --> L2["Input contract"]
    L2 --> L3["Algorithm"]
    L3 --> L4["Tests"]
    style L1 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style L2 fill:#fff9c4,stroke:#f57f17,stroke-width:3px
    style L3 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style L4 fill:#d1c4e9,stroke:#5e35b1,stroke-width:3px
</pre>
]

- Know the representation before touching the algorithm.
- The 2/3-node base cases were the clue: even-index compression.
- A predicate that never fires on a non-representation input is a red herring.
- Copy mutable inputs; do not corrupt the caller.
- Tests must use the real representation.
- Keep sibling implementations aligned.

---

## Q&A 💬

---

# 🎉 Thank you!

### The bug was not in the cut — it was in the shape we handed to it.

📐 physdes-py issue #5 · C++ / Python / Rust