Skip to content

Sketch face extraction misses enclosed regions when squares overlap at a corner #173

Description

@trailcode

Summary

When two squares overlap at a corner (e.g. a 2×2 square plus a 1×1 square placed with its center on the top-right corner of the first), Sketch_topo::update_faces() should produce three bounded faces: two L-shaped regions plus the small overlap square. Currently it produces only two faces—the overlap region is missing.

Problem

  • The face walker marked both directions of each boundary edge as visited after finding a face (seen_edges.insert(a,b) and seen_edges.insert(b,a)).
  • In planar graphs, each directed half-edge (a→b vs b→a) borders exactly one face. Marking both endpoint directions prevents seeding walks for faces that are fully enclosed by already-discovered neighbors.
  • Reproducible via the GUI square tool: add a 2×2 square (half-side 1), then a 1×1 square centered on the top-right corner, midpoints off.

Expected fix

  • Walk the graph one half-edge at a time; key the visited set on (edge pointer, direction) rather than (node_a, node_b) pairs.
  • Use standard leftmost-turn rule with CCW (positive area) cycles as real regions; discard the outer CW cycle.
  • Add a regression test exercising the GUI finalize_square_ path.

Acceptance criteria

  • Overlapping corner squares produce three faces.
  • Existing face tests pass (holes, bridges, mid-splitter rectangles, arcs, dangling edges).
  • src/doc/sketch.md documents the half-edge extraction approach.

Related

Metadata

Metadata

Assignees

Labels

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions