RPolygon Representation & Robust Cutting

---

# 📐 RPolygon Representation
## & Robust Rectilinear Cutting

### Even-index · x-first · 2-node split

@luk036 · PhysDes C++ / Recti · 2026

???
⏱️ 0:00–0:01 — Welcome. This is a 30-minute tour of a representation bug that looked like a cutting bug, and the standalone rewrite plus degenerate 2-node split that fixed it.

---

### 🗺️ Agenda

**Part 1 — The Representation Contract** 📐
- Full vertex list vs even-index
- x-first reconstruction
- 2-point and 3-point pieces
- Representation checklist

**Part 2 — The Bug Hunt** 🐛
- Issue #7 and the 8-point list
- What the algorithm actually saw

]

**Part 3 — Standalone Cut & 2-Node Split** 🧹
- Standalone C++ without Policy
- Keep the original scan
- Degenerate 2-node split
- Python follows C++

**Part 4 — Verification & Lessons** 🧪
- 12-point fixture: 1 + 10 + 9
- xmake debug/release results
- Stress test and Python parity
- What we learned

]

???
⏱️ 0:01–0:02 — Four parts. The key idea: keep the original algorithm, make the convex path standalone, and split the existing 2-node piece when the cut point duplicates the target.

---

## Part 1 — The Representation Contract 📐

???
⏱️ 0:02–0:10 — Eight minutes on the contract. If the audience remembers one thing, it should be the x-first rule and the fact that a 2-point piece is a rectangle, not a degenerate polygon.

---

### 🧱 What is a rectilinear polygon?

> A **rectilinear polygon** (orthogonal polygon) has only horizontal and vertical edges.

.mermaid[
<pre>
graph TD
    A["Polygon types"] --> B["General polygon"]
    A --> C["Rectilinear polygon"]
    B --> D["Any-angle edges"]
    C --> E["Only H/V edges"]
    C --> F["90 and 270 degree corners"]
    classDef root fill:#88c0d0,stroke:#5e81ac,stroke-width:3px,color:#2e3440;
    classDef good fill:#a3be8c,stroke:#2e7d32,stroke-width:3px,color:#2e3440;
    classDef neutral fill:#e5e9f0,stroke:#4c566a,stroke-width:2px,color:#2e3440;
    class A root;
    class C,E,F good;
    class B,D neutral;
</pre>
]

]

#### Where it shows up

- 🧩 VLSI floorplanning
- 🛣️ Manhattan routing
- 📦 Module packing
- 🔬 Physical-design geometry

#### Why it is special

- ✅ Simple area formulas
- ✅ Grid-friendly predicates
- ✅ Natural convex decomposition

]

???
⏱️ 0:02–0:04 — Rectilinear polygons are the native geometry of VLSI. The simplification is real: every edge is axis-aligned, so predicates and cuts can be exact integer operations.

---

### 🧩 Two ways to store the same polygon

Every corner is explicit:

```text
8 vertices
(0,0) (3,0) (3,3) (2,3)
(2,1) (1,1) (1,3) (0,3)
```

- Easy to draw
- Redundant for rectilinear cuts
- Consecutive points share an axis

]

Store every other corner:

```text
4 stored points
(0,0) (3,3) (2,1) (1,3)
```

- Half the storage
- The omitted corners are implicit
- **This is what the cut functions consume**

]

---

<p align="center">
<svg width="760" height="340" viewBox="0 0 760 340" xmlns="http://www.w3.org/2000/svg" style="background:#fafafa;border:1px solid #d0d0d0;border-radius:8px">
  <text x="20" y="28" font-family="sans-serif" font-size="16" font-weight="bold" fill="#2e3440">Same U-shape: 8 full vertices → 4 stored points</text>
  <polygon points="80,280 440,280 440,70 320,70 320,210 200,210 200,70 80,70" fill="#e5e9f0" stroke="#5e81ac" stroke-width="3"/>
  <g fill="#4c566a">
    <circle cx="440" cy="280" r="4"/><circle cx="320" cy="70" r="4"/><circle cx="200" cy="210" r="4"/><circle cx="80" cy="70" r="4"/>
  </g>
  <g fill="#5e81ac">
    <circle cx="80" cy="280" r="8"/><circle cx="440" cy="70" r="8"/><circle cx="320" cy="210" r="8"/><circle cx="200" cy="70" r="8"/>
  </g>
  <g font-family="sans-serif" font-size="13" fill="#2e3440">
    <text x="52" y="305">S0 (0,0)</text>
    <text x="450" y="62">S1 (3,3)</text>
    <text x="330" y="205">S2 (2,1)</text>
    <text x="120" y="62">S3 (1,3)</text>
    <text x="450" y="300" fill="#4c566a">I0 (3,0)</text>
    <text x="300" y="55" fill="#4c566a">I1 (2,3)</text>
    <text x="210" y="230" fill="#4c566a">I2 (1,1)</text>
    <text x="50" y="60" fill="#4c566a">I3 (0,3)</text>
  </g>
  <g font-family="sans-serif" font-size="14" fill="#2e3440">
    <circle cx="510" cy="120" r="8" fill="#5e81ac"/><text x="525" y="125">stored (even-index)</text>
    <circle cx="510" cy="150" r="4" fill="#4c566a"/><text x="525" y="155">implicit (x-first)</text>
  </g>
  <text x="510" y="200" font-family="sans-serif" font-size="14" fill="#bf616a">cut functions receive</text>
  <text x="510" y="220" font-family="sans-serif" font-size="14" fill="#bf616a" font-weight="bold">only the 4 stored points</text>
  <text x="510" y="260" font-family="sans-serif" font-size="13" fill="#4c566a">2 points = rectangle</text>
  <text x="510" y="280" font-family="sans-serif" font-size="13" fill="#4c566a">3 points = L-shape</text>
</svg>
</p>

???
⏱️ 0:04–0:05 — This is the slide that explains the whole bug report. The 8-point list is a full vertex list. The cut functions expect the 4 blue points. Same shape, different contract.

---

### 🔁 Canonical even-index encoding

.mermaid[
<pre>
graph LR
    A["Full vertex list\n8 points"] --> B["Remove collinear"]
    B --> C["Rotate:\nfirst edge horizontal"]
    C --> D["Take every other\nvertex"]
    D --> E["Even-index\n4 stored points"]
    E --> F["x-first\nreconstruct"]
    F --> G["Full boundary"]
    classDef input fill:#88c0d0,stroke:#5e81ac,stroke-width:3px,color:#2e3440;
    classDef step fill:#ebcb8b,stroke:#d08770,stroke-width:3px,color:#2e3440;
    classDef out fill:#a3be8c,stroke:#2e7d32,stroke-width:3px,color:#2e3440;
    class A input;
    class B,C,D step;
    class E,F,G out;
</pre>
]

$$ S_i = \text{full}\left[(\text{start} + 2i) \bmod n\right] \qquad i = 0,\ldots,\frac{n}{2}-1 $$

- Start on a vertex whose **outgoing edge is horizontal**
- Store every **other** corner
- Keep the boundary order
- Do **not** reverse the stored list
]

- Half the points
- Still enough to reconstruct the boundary
- Cut functions have a stable, checkable contract
]

???
⏱️ 0:05–0:06 — The start vertex matters. If you start on a vertical edge, the x-first rule reconstructs a different polygon. That is exactly the phase trap we hit.

---

### ➡️ Reconstruct with x-first

<p align="center">
<svg width="760" height="300" viewBox="0 0 760 300" xmlns="http://www.w3.org/2000/svg" style="background:#fafafa;border:1px solid #d0d0d0;border-radius:8px">
  <text x="20" y="28" font-family="sans-serif" font-size="16" font-weight="bold" fill="#2e3440">Between two stored points: move x first, then y</text>
  <text x="60" y="60" font-family="sans-serif" font-size="15" font-weight="bold" fill="#2e7d32">x-first ✅</text>
  <line x1="60" y1="240" x2="260" y2="240" stroke="#5e81ac" stroke-width="4"/>
  <line x1="260" y1="240" x2="260" y2="60" stroke="#5e81ac" stroke-width="4"/>
  <circle cx="60" cy="240" r="8" fill="#5e81ac"/><text x="20" y="270" font-family="sans-serif" font-size="13" fill="#2e3440">S0 (x0,y0)</text>
  <circle cx="260" cy="60" r="8" fill="#5e81ac"/><text x="278" y="55" font-family="sans-serif" font-size="13" fill="#2e3440">S1 (x1,y1)</text>
  <circle cx="260" cy="240" r="7" fill="#a3be8c"/><text x="185" y="265" font-family="sans-serif" font-size="13" fill="#2e7d32">implicit (x1,y0)</text>
  <text x="60" y="290" font-family="sans-serif" font-size="13" fill="#4c566a">same shape as the original full list</text>

<text x="430" y="60" font-family="sans-serif" font-size="15" font-weight="bold" fill="#bf616a">y-first ❌</text>
  <line x1="430" y1="240" x2="430" y2="60" stroke="#bf616a" stroke-width="4" stroke-dasharray="9 6"/>
  <line x1="430" y1="60" x2="630" y2="60" stroke="#bf616a" stroke-width="4" stroke-dasharray="9 6"/>
  <circle cx="430" cy="240" r="8" fill="#5e81ac"/><text x="390" y="270" font-family="sans-serif" font-size="13" fill="#2e3440">S0</text>
  <circle cx="630" cy="60" r="8" fill="#5e81ac"/><text x="648" y="55" font-family="sans-serif" font-size="13" fill="#2e3440">S1</text>
  <circle cx="430" cy="60" r="7" fill="#bf616a"/><text x="445" y="50" font-family="sans-serif" font-size="13" fill="#bf616a">(x0,y1)</text>
  <text x="430" y="105" font-family="sans-serif" font-size="13" fill="#bf616a">different polygon</text>
  <text x="430" y="290" font-family="sans-serif" font-size="13" fill="#4c566a">do not do this</text>
</svg>
</p>

$$ I_i = \left(x_{i+1},\, y_i\right) \qquad \text{full} = S_0, I_0, S_1, I_1, S_2, \ldots $$

???
⏱️ 0:06–0:07 — This is the single most important equation. The implicit vertex is (next.x, current.y). The y-first version looks similar but reconstructs a different polygon.

---

### 🧪 Worked example: the U-shape

```text
S0 = (0,0)
S1 = (3,3)
S2 = (2,1)
S3 = (1,3)
```

#### x-first reconstruction

```text
(0,0) → (3,0) → (3,3)
(3,3) → (2,3) → (2,1)
(2,1) → (1,1) → (1,3)
(1,3) → (0,3) → (0,0)
```

]

```text
(0,0) (3,0) (3,3) (2,3)
(2,1) (1,1) (1,3) (0,3)
```

#### What the cutter sees

- 4 stored points
- 8 full vertices
- 2 convex pieces ✅

> This 4-point input already works. The 8-point list is a different contract.

]

???
⏱️ 0:07–0:08 — Walk through the four x-first steps. Then point out: the canonical 4-point U returns two convex pieces. The reported 8-point list is not the same input.

---

### 📦 2 points = rectangle, 3 points = L-shape

<p align="center">
<svg width="760" height="300" viewBox="0 0 760 300" xmlns="http://www.w3.org/2000/svg" style="background:#fafafa;border:1px solid #d0d0d0;border-radius:8px">
  <text x="20" y="28" font-family="sans-serif" font-size="16" font-weight="bold" fill="#2e3440">Pieces are already canonical even-index polygons</text>
  <rect x="60" y="70" width="200" height="160" fill="#e5e9f0" stroke="#5e81ac" stroke-width="3" stroke-dasharray="7 5"/>
  <circle cx="60" cy="230" r="8" fill="#5e81ac"/><circle cx="260" cy="70" r="8" fill="#5e81ac"/>
  <text x="75" y="260" font-family="sans-serif" font-size="15" font-weight="bold" fill="#2e3440">2 stored points</text>
  <text x="75" y="282" font-family="sans-serif" font-size="14" fill="#2e7d32">rectangle ✅</text>
  <text x="275" y="155" font-family="sans-serif" font-size="13" fill="#4c566a">opposite corners</text>

<polygon points="430,230 630,230 630,70 530,70 530,150 430,150" fill="#e5e9f0" stroke="#5e81ac" stroke-width="3"/>
  <circle cx="430" cy="230" r="8" fill="#5e81ac"/><circle cx="630" cy="70" r="8" fill="#5e81ac"/><circle cx="530" cy="150" r="8" fill="#5e81ac"/>
  <text x="445" y="260" font-family="sans-serif" font-size="15" font-weight="bold" fill="#2e3440">3 stored points</text>
  <text x="445" y="282" font-family="sans-serif" font-size="14" fill="#2e7d32">L-shape / orthogonally convex ✅</text>
</svg>
</p>

---

- 2 points: opposite corners
- 3 points: consecutive points differ in both coordinates
- More points: larger orthogonally convex piece
]

- `(2,0)` and `(2,1)` as a 2-point piece
- Same `x` → zero width
- Same `y` → zero height

> A 2-point or 3-point piece is **not** a degenerate polygon. It is the representation.

]

???
⏱️ 0:08–0:09 — This is the slide that makes the invalid output obvious. A 2-point piece must be a rectangle: different x and different y. Same-x points are a zero-width line, not a polygon.

---

### ✅ Representation checklist

| Check | Why it matters |
|---|---|
| At least 2 stored points | A rectangle needs two opposite corners |
| Consecutive pts differ in `x` and `y` | This is the even-index invariant |
| Stored order follows the boundary | Reversing changes orientation and shape |
| Start on a horizontal outgoing edge | x-first otherwise reconstructs a different polygon |
| x-first reconstruction is simple | The cut algorithm assumes a simple orthogonal polygon |

.mermaid[
<pre>
graph LR
    A["Full polygon"] --> B["Canonical even-index"]
    B --> C["Cut functions"]
    C --> D["Convex pieces"]
    D --> E["Pieces are even-index again"]
    classDef good fill:#a3be8c,stroke:#2e7d32,stroke-width:3px,color:#2e3440;
    classDef step fill:#88c0d0,stroke:#5e81ac,stroke-width:3px,color:#2e3440;
    class A,B,C,D,E step;
    class E good;
</pre>
]

> If `find_concave_point` never fires, check the representation before changing the concavity predicate. 🔍

???
⏱️ 0:09–0:10 — The checklist is the debugging tool. When a cut fails, first ask whether the input is canonical even-index. Only then inspect the algorithm.

---

## Part 2 — The Bug Hunt 🐛

???
⏱️ 0:10–0:20 — Ten minutes on the representation bug: a full vertex list was fed to the even-index cutter.

---

### 🐛 Issue #7: the 8-point list

.mermaid[
<pre>
graph LR
    I["Issue 7\n8-point list"] --> Q{"Canonical\neven-index?"}
    Q -->|No| N["Full vertex list\nconsecutive points share axes"]
    N --> C["Close issue 7\nrepresentation problem"]
    Q -->|Yes| T["4-point U\n(0,0),(3,3),(2,1),(1,3)"]
    T --> P["2 convex pieces\n✅ works"]
    classDef bad fill:#f8bbd0,stroke:#bf616a,stroke-width:3px,color:#2e3440;
    classDef good fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px,color:#2e3440;
    classDef warn fill:#ffe0b2,stroke:#d08770,stroke-width:3px,color:#2e3440;
    class N,C bad;
    class T,P good;
    class Q warn;
</pre>
]

```text
(0,0) (3,0) (3,3) (2,3)
(2,1) (1,1) (1,3) (0,3)
```

- 8 points
- Consecutive points share axes
- This is a **full vertex list**

]

```text
(0,0) (3,3) (2,1) (1,3)
```

- 4 stored points
- Every consecutive pair differs in both coordinates
- This is the **canonical even-index** form

]

???
⏱️ 0:10–0:12 — This is the triage. Issue 7 was closed as a representation problem: the report used a full vertex list, while the cutter expects canonical even-index.

---

### 🔍 What the algorithm actually saw

- The cutter treats every point as stored
- Edges are diagonal in the stored representation
- The concavity predicate looks at the wrong turns
- Result: **one non-convex piece** ❌

]

- The implicit vertices are reconstructed x-first
- The concavity predicate sees the real turns
- Result: **two convex pieces** ✅

]

$$ \text{full list} \;\ne\; \text{even-index list} $$

> Same U-shape. Different contract. Different result. 🎯

???
⏱️ 0:12–0:13 — This is the “aha” moment. The algorithm did not fail on the shape; it failed on the encoding. The 8-point list is not a valid even-index input.

---

## Part 3 — Standalone Cut & 2-Node Split 🧹

???
⏱️ 0:20–0:29 — The fix has two parts: make the convex path standalone and split the existing 2-node piece when the cut point duplicates the target. No Policy, no new scan, no general repair pass.

---

### 🧹 Standalone convex cut (no Policy)

.font-sm[
```cpp
rpolygon_cut_convex(...)
  -> rpolygon_cut_impl<
       T, ConvexCutPolicy<T>>(...)
  -> shared Policy skeleton
```
]

- One skeleton for convex / explicit / implicit
- Convex behavior hidden in `ConvexCutPolicy`
- Hard to trace the convex path alone

]

.font-sm[
```cpp
rpolygon_cut_convex(...)
  -> rpolygon_cut_convex_recur(...)
     -> find_concave_point_convex(...)
     -> find_min_dist_point_convex(...)
     -> try_degenerate_two_node_split(...)
     -> insert_cut_convex(...)
```
]

- Convex path is self-contained
- Explicit / implicit keep their Policy code
- Same scan, plus a degenerate-split hook

]

???
⏱️ 0:21–0:23 — This is a structural refactor plus a degenerate-split hook. The convex path no longer goes through Policy, while explicit and implicit keep their existing implementation.

---

### ➡️ Keep the original C++ scan

.font-sm[
```cpp
auto result = _find_min_dist_point<T>(
    lst, vcurr, vcurr->next, lst[vcurr->data]);
```
]

- Start at `vcurr->next`
- Stop at `vcurr`
- Half-open range tests
- Includes `vnext` and `vprev`

]

- Small subpolygons still have candidates
- No empty-scan degenerate cut
- 100-point stress terminates
- 7-point fixture still works

]

$$ \text{start} = v_{\text{curr.next}} \;\longrightarrow\; \text{stop} = v_{\text{curr}} $$

???
⏱️ 0:23–0:25 — Python's inclusive scan excludes the two neighbors. On a 4-node subpolygon that leaves no candidate, and the 100-point stress hangs. The original C++ scan includes those neighbors, so it terminates.

---

### 🧷 Degenerate cut → 2-node split

```text
(-1,1) (0,0) (1,-1) (3,0)
(4,1) (6,2) (5,5) (4,4)
(3,2) (2,3) (1,2) (0,3)
```

- Concave vertex `(3,2)`
- Target `v_min = (1,2)`
- `p_new = (1,2) = v_min` → duplicate
- Old code appended `(1,2)` and left a non-convex piece ❌

]

.font-sm[
```cpp
if (vertical && v_min->prev == vcurr->next
    && p_min.ycoord() == p_curr.ycoord()) {
    auto* first = vcurr->next;   // (2,3)
    auto* rest  = v_min->next;   // (0,3)
    const auto& first_point = lst[first->data];
    if (first_point.xcoord() != p_min.xcoord()
        && first_point.ycoord() != p_min.ycoord()) {
        first->next = first->prev = v_min;
        v_min->next = v_min->prev = first;
        vcurr->next = rest;
        rest->prev = vcurr;
    }
}
```
]

- 2-node piece: `[(2,3),(1,2)]`
- Remainder: `(3,2) → (0,3) → …`
- No `lst.emplace_back`
- Horizontal cuts use the symmetric branch

]

$$ p_{\text{new}} = p_{\min} \;\land\; \text{2-node piece valid} \;\Longrightarrow\; \text{split existing nodes} $$

???
⏱️ 0:25–0:27 — This is the new guard. When the cut point duplicates v_min, the old code appended a second copy of (1,2), leaving the remainder non-canonical. The fix splits the existing 2-node piece [(2,3),(1,2)] and connects (3,2) directly to (0,3). No (2,2) is created, and no point is appended.

---

### ✅ 12-point fixture after the split

<p align="center">
<svg width="500" height="431" viewBox="0 0 580 500" xmlns="http://www.w3.org/2000/svg" style="background:#fafafa;border:1px solid #d0d0d0;border-radius:8px">
  <text x="20" y="28" font-family="sans-serif" font-size="15" font-weight="bold" fill="#2e3440">12-point even-index fixture: 3 convex pieces</text>
  <polygon points="355,210 190,210 190,155 135,155 135,265 190,265 190,320 245,320 245,375 355,375 355,320" fill="#d08770" stroke="#2e3440" stroke-width="1.5" opacity="0.8"/>
  <polygon points="355,320 410,320 410,265 520,265 520,210 465,210 465,45 410,45 410,100 355,100" fill="#a3be8c" stroke="#2e3440" stroke-width="1.5" opacity="0.8"/>
  <polygon points="245,210 300,210 300,155 245,155" fill="#88c0d0" stroke="#2e3440" stroke-width="1.5" opacity="0.9"/>
  <polygon points="135,265 190,265 190,320 245,320 245,375 355,375 355,320 410,320 410,265 520,265 520,210 465,210 465,45 410,45 410,100 355,100 355,210 300,210 300,155 245,155 245,210 190,210 190,155 135,155" fill="none" stroke="#2e3440" stroke-width="2.5" stroke-dasharray="7 5"/>
  <g font-family="sans-serif" font-size="12" fill="#2e3440" text-anchor="middle">
    <text x="272.5" y="178.5">piece 0</text>
    <text x="272.5" y="194.5">area 1</text>
    <text x="228.5" y="272.0">piece 1</text>
    <text x="228.5" y="288.0">area 10</text>
    <text x="432.0" y="173.00000000000003">piece 2</text>
    <text x="432.0" y="189.00000000000003">area 9</text>
  </g>
  <g font-family="sans-serif" font-size="12" fill="#bf616a">
    <text x="150" y="105">split (2,3)-(1,2)</text>
    <text x="150" y="120">no new point</text>
  </g>
  <g font-family="sans-serif" font-size="12" fill="#4c566a">
    <rect x="40" y="455" width="18" height="12" fill="#d08770" opacity="0.8"/>
    <text x="66" y="465">piece 1</text>
    <rect x="140" y="455" width="18" height="12" fill="#a3be8c" opacity="0.8"/>
    <text x="166" y="465">piece 2</text>
    <rect x="240" y="455" width="18" height="12" fill="#88c0d0" opacity="0.9"/>
    <text x="266" y="465">piece 0</text>
    <line x1="350" y1="461" x2="380" y2="461" stroke="#2e3440" stroke-width="2.5" stroke-dasharray="7 5"/>
    <text x="388" y="465">original boundary</text>
  </g>
  <text x="20" y="488" font-family="sans-serif" font-size="12" fill="#4c566a">(2,2) is implicit in piece 0; neither piece stores (2,2).</text>
</svg>
</p>

- `1 + 10 + 9 = 20` ✅
- No stored `(2,2)` on either piece
- Same fixture in Python and C++

???
⏱️ 0:27–0:28 — The corrected decomposition has three convex pieces. The square keeps (2,2) implicit; the remainder never sees it. This 12-point case is the regression test for the 2-node split.

---

### 🐍 Python follows C++

```python
vstop = vcurr
vi = vcurr.next
...
if (prev.y < pcurr.y <= curr.y) or (
    curr.y <= pcurr.y < prev.y
):
    ...
```

- Original half-open C++ scan
- Neighbor-inclusive
- No `is_valid_cut` guard

]

.font-sm[
```python
if vertical and v_min.prev is vcurr.next:
    first, rest = vcurr.next, v_min.next
    ...
```
]

- 12-point fixture: 3 pieces, `1 + 10 + 9`
- 7-point fixture: `3 + 0 + 8` (raw)
- Cut tests: 8 passed
- Full suite: 606 passed, 1 unrelated Vector2 failure

]

???
⏱️ 0:27–0:28 — Python now mirrors the C++ version: the same scan and the same 2-node split. The 12-point fixture returns 1 + 10 + 9 in both languages; the 7-point fixture now exposes its raw zero-area piece.

---

### 🧪 Shared fixture: 7-point raw output

```cpp
{0,0}, {0,2}, {1,2},
{1,1}, {2,1}, {2,0}
```

- 6 points
- First edge shares `x`
- Not canonical even-index
- Not a cut input

]

```cpp
{0,-2}, {1,-3}, {3,-2},
{2,-1}, {4,1}, {3,0}, {2,1}
```

- 7 stored points
- Derived from the full boundary by `step_by(2)`
- Result: 3 raw pieces, `3 + 0 + 8`
- Same fixture in Python and C++

]

$$ \text{full boundary} \;\longrightarrow\; \text{step\_by(2)} \;\longrightarrow\; 3 + 0 + 8 $$

> The raw zero-area piece is no longer filtered; the output keeps `3 + 0 + 8`. 🎯

???
⏱️ 0:29 — This is the fixture shared by the Python and C++ tests. It is canonical even-index, and its raw output is 3 + 0 + 8. The zero-area piece is no longer filtered; the 2-node split is the fix for the 12-point case.

---

## Part 4 — Verification & Lessons 🧪

???
⏱️ 0:29–0:30 — Two minutes on results, status, and takeaways.

---

### 📊 Verification

.font-sm[
```bash
xmake f -m debug -y && xmake build test_recti && xmake run test_recti
xmake f -m release -y && xmake build test_recti && xmake run test_recti
```
]

.font-sm[
| Check | Result |
|---|---|
| Debug + release | **137 / 137 each** ✅ |
| Assertions | **778 / 778 passed** ✅ |
| 100-point stress | passes ✅ |
| 12-point fixture | 3 pieces, `1 + 10 + 9` ✅ |
| 7-point fixture | 3 raw pieces, `3 + 0 + 8` ✅ |
| Python | cut 8 passed; full 606 passed, 1 unrelated Vector2 ⚠️ |
]

- Original scan retained
- Raw pieces kept, no filter
- 2-node split, no new point
- Stress test passes
- Python matches C++

]

- No general cut-path validity oracle
- Vector2 failure is unrelated
- Rust cut is still a stub

]
]

???
⏱️ 0:29–0:30 — Debug and release are green. The 100-point stress passes, the 12-point fixture is 1 + 10 + 9, the 7-point fixture is the raw 3 + 0 + 8, and Python matches C++. The only red test is an unrelated Vector2 property failure.

---

### 📌 Status & next steps

.mermaid[
<pre>
graph LR
    A["Issue 7\nrepresentation"] --> B["Canonical even-index\ndocumented"]
    B --> C["Issue 8\nzero-area piece"]
    C --> D["Remove filter\nraw pieces visible"]
    D --> E["Standalone C++\noriginal scan"]
    E --> F["Degenerate 2-node split\nno new point"]
    F --> G["Python parity"]
    G --> H["Next: Rust cut\nimplementation"]
    classDef good fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px,color:#2e3440;
    classDef step fill:#88c0d0,stroke:#5e81ac,stroke-width:3px,color:#2e3440;
    classDef next fill:#ffe0b2,stroke:#d08770,stroke-width:3px,color:#2e3440;
    class A,B,C,D,E,F,G step;
    class H next;
</pre>
]

- Issue #7: representation / input contract
- Issue #8: filter removed; zero-area piece visible
- 12-point non-convex leftover
- 100-point stress passes
- Python now matches C++

]

- Implement Rust convex cut and fixture
- Keep the 2-node split; no zero-area filter
- Add more structured stress fixtures
- Investigate the unrelated Vector2 test

> The cut is fixed at the source; the zero-area piece is visible, not filtered. 🚀

]

???
⏱️ 0:30 — The zero-area filter is removed. The 2-node split fixes the 12-point cut, while the 7-point zero-area piece remains visible in the raw output. The next engineering step is the Rust implementation and more stress coverage.

---

### 🧠 Lessons learned

- Full list → even-index
- x-first is not y-first
- Start on a horizontal edge
- 2 points = rectangle, not a line

#### Fix the cut, not the output

- Keep the original algorithm
- Split the existing 2-node piece on a duplicate cut
- No new point for a collinear duplicate
- Keep raw pieces visible; do not hide them
- No assertions in the recursion

]

- A fixture is an input
- Invalid fixtures hide invalid paths
- Share the same fixture across languages
- Stress tests protect the fix

#### Review checklist

- Is the input canonical even-index?
- Does the cut duplicate `v_min`?
- Is the 2-node piece non-degenerate?
- Do Python and C++ agree?

> “It works on my polygon” is not a contract. 📝

]

???
⏱️ 0:30 — Close with the lessons: representation first, split the existing 2-node piece instead of synthesizing a duplicate, keep the raw output visible, and make the tests speak the same contract across languages.

---

# 🙋 Q&A

### Questions? Discussion? 🤔

---

# 🎉 Thank You

Slides built with Remark.js · KaTeX · Mermaid · Nord Theme

### Keep your polygons canonical. 🧩