1

I want to extract only bounded faces from an undirected connected planar graph where edges are represented as straight lines or quadratic/cubic Bézier curves, and they don't intersect each other. I did it successfuly for graphs with only straight line edges following this paper. My algorithm goes like this.

  1. Find the 2-core of the graph. Use the 2-core instead of the entire graph.
  2. Pick a vertex V and a directed edge V->U. Mark V->U as visited.
  3. Find edge U->W such that the counterclockwise angle from U->V to U->W is the minimum. Mark U->W as visited.
  4. If W is the initial vertex, a face is found. Else put U in place of V and U->W in place of V->U and repeat 3.
  5. Let V1V2...Vn be the face found. Find k such that the directed edge Vk->Vk-1 is unvisited. Restart 2 with initial vertex Vk and edge Vk->Vk-1. If there is no such k, pick any unvisited edge and restart.
  6. Remove the only face with different orientation. This face represents the unbounded exterior region.

I calculated the orientation of faces with this answer.

But if there are curved edges, the situation is different. First, I modified step 2 so that we compare the angle between tangent vectors instead. Now, I have trouble at step 6. The convex hull of a face could contain no vertices, so that answer doesn't work. In this case we can instead grab a point on a curve with minimal y coordinate and calculate the sign of the curvature, but it seems too inefficient. Is there a way to calculate orientation more efficiently, or is there another way to distinguish unbounded region from bounded regions?

Ris
  • 165
  • 10
  • Replace the curves with their control points and you again have straight-edged polygons upon which you can do your initial calculations (including neighbor edge search and orientation calculation). – Nico Schertler May 31 '22 at 18:04

0 Answers0