Loop Detection: Finding Holes in Polygon Soup

You have 20 segments. They connect at vertices forming closed loops.

Which segments form loop 1? Which form loop 2? Where are the holes?

This is the loop detection problem.

The Problem

Vector networks store segments as unordered edge soup:

Segments: [(0→1), (5→3), (1→2), (3→0), (2→5)]

To render filled shapes, we need ordered loops:

Loop 1: [0→1, 1→2, 2→5, 5→3, 3→0]  ← Traces a closed path

The segments exist, but their ordering isn't explicit. We have to detect it.

First Attempt: Greedy Traversal

Start at any segment, follow connections:

std::vector detectLoop(uint32_t startSegment) {
  std::vector loop = {startSegment};
  uint32_t current = startSegment;

  while (true) {
    uint32_t nextSegment = findConnectedSegment(current);
    if (nextSegment == startSegment) break;  // Loop closed

    loop.push_back(nextSegment);
    current = nextSegment;
  }

  return loop;
}

This worked for simple shapes (rectangles, triangles). Then we tried it on a star shape with five points.

It found one loop connecting all five outer points. Missed the inner pentagon hole entirely.

The problem: greedy search doesn't backtrack. If there are multiple ways to connect segments, it picks one arbitrarily and gets stuck.

Second Attempt: Topological Ordering

Build a connectivity graph, then traverse it systematically:

// Build adjacency map: vertex → segments
std::map> vertexToSegments;

for (uint32_t segId = 0; segId < segments.size(); segId++) {
  auto& seg = segments[segId];
  vertexToSegments[seg.fromVertex].push_back(segId);
  vertexToSegments[seg.toVertex].push_back(segId);
}

// For each vertex, order segments by angle
for (auto& [vertexId, segs] : vertexToSegments) {
  std::sort(segs.begin(), segs.end(), compareByAngle);
}

Now when traversing, at each vertex, pick the next segment in angular order (clockwise or counter-clockwise).

This found all loops, including holes. But it created duplicate loops for the same path—traversing clockwise vs counter-clockwise gave two separate loops for one polygon.

The Solution: Sequential Ordering with Virtual Vertices

The key insight: loops are continuous sequences of segments where each segment's end connects to the next segment's start.

For segments that don't naturally connect this way, insert virtual vertices:

// Segment ordering for a loop
Loop segments must satisfy: segment[i].toVertex == segment[i+1].fromVertex

If they don't, insert a virtual "zero-length" segment connecting them

Algorithm (src/cf/model/CfVectorNetworkLoop.cpp):

void orderSegmentsSequentially(std::vector& segments) {
  std::vector ordered;
  Segment current = segments[0];
  ordered.push_back(current);

  while (ordered.size() < segments.size()) {
    // Find segment whose fromVertex == current.toVertex
    auto next = findSegmentStartingAt(current.toVertex);

    if (next == nullptr) {
      // No natural connection - need virtual vertex
      uint32_t virtualVertex = createVirtualVertex(current.toVertex);
      // Insert virtual segment
    }

    ordered.push_back(*next);
    current = *next;
  }

  segments = ordered;
}

This ensures segments form a continuous path without gaps.

Handling Holes

Loops have winding direction: clockwise or counter-clockwise.

Outer boundary: counter-clockwise (by convention) Holes: clockwise (opposite winding)

Detect by calculating signed area:

float calculateSignedArea(const Loop& loop) {
  float area = 0;
  for (auto& seg : loop.segments) {
    SkPoint p1 = vertices[seg.fromVertex];
    SkPoint p2 = vertices[seg.toVertex];
    area += (p2.x - p1.x) * (p2.y + p1.y);  // Shoelace formula
  }
  return area / 2;
}

bool isHole(const Loop& loop) {
  return calculateSignedArea(loop) > 0;  // Positive = clockwise = hole
}

Render outer loops with fill, holes with reverse fill or subtraction.

Results

Loop detection now correctly identifies:

• All closed loops in the segment graph
• Loop ordering (sequential traversal)
• Holes vs outer boundaries (winding direction)
• Complex topology (nested holes, multiple loops)

The algorithm is ~150 lines handling:

• Connectivity graph construction
• Angular ordering at vertices
• Sequential path traversal
• Virtual vertex insertion for gaps
• Winding direction calculation

Vector networks can now be converted to filled paths for rendering, with proper hole handling.

---

Read next: Effect Caching: When to Recalculate vs. Reuse - Cache invalidation for static effects.