Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Extract Shapes

Once we apply boolean filter to Overlay Graph, we can begin extract contours.

Build Contour

Outer Contour

Extracting an outer contour Green segments and nodes form the overlay graph. Gold arrows show how to select the next segment and trace an outer contour. Numbered steps show the traversal sequence.

Inner Contour

Extracting an inner contour Green segments and nodes form the overlay graph. Gold arrows show how to select the next segment and trace an inner contour. Numbered steps show the traversal sequence.

The algorithm starts by selecting the leftmost node and proceeds by choosing the topmost segment connected to that node. The process continues by traversing to the next node along the selected segment.

At each node, the algorithm selects the next segment by rotating around the current node in a clockwise/counterclockwise direction for outer/inner contours and taking the first nearest segment.

To prevent segments from being visited twice, each segment is marked as visited upon traversal.

This process continues until the contour is complete, forming either an outer or inner contour.

By following this approach, outer contours are extracted in a counter-clockwise direction, while inner contours are extracted in a clockwise direction.

Define Contour

Classifying a contour Red and blue filled or hollow markers show outer and inner membership on each side of the selected green segments. outer inner

To define a contour, the algorithm begins by identifying the leftmost and topmost segment in the contour. The classification of the contour is determined as follows:

  • If the left-top side of the segment is classified as the outer side, then the contour is an outer contour.
  • If the left-top side of the segment is classified as the inner side, then the contour is an inner contour.

This method ensures each contour is correctly classified based on its orientation in 2D space.

Define Shape

Defining a shape from contours Each green filled shape consists of an outer contour and its inner contours. Numbers identify separate shapes.

A shape is defined as a group of contours, where the first contour is always an outer contour, and the subsequent contours (if any) are inner contours.

Matching Contours

Matching inner contours to outer contours Gold arrows and dashed guide lines show how to find the containing contour for a point on an inner contour.

To match inner contours to their corresponding outer contours:

  1. Draw a line downward from any point on the inner (target) contour.
  2. Identify the first segment encountered along the line that does not belong to the target contour.
  • If the segment belongs to an outer contour, that contour is the container for the target contour.
  • If the segment belongs to another inner contour, the container of that inner contour is also the container for the target contour.

Define Segment under Point

Segment under Point

Testing whether a segment is below a point Green segment AB lies below point P. Dashed guides mark the projected intersection M; arrows show triangle traversal. P A B M a b

To determine whether a segment AB is below a point P, one may be tempted to compute the value of ym at the point of intersection M, where a vertical line is dropped from P onto AB (i.e., xp = xm):

$$ y_{m} = \frac{y_{a} - y_{b}}{x_{a} - x_{b}}\cdot(x_{m} - x_{a}) + y_{a} $$

However, this approach can introduce precision issues due to the division involved.

A more reliable method involves using the order of traversal around the vertices of the triangle APB. If segment AB is below point P, the vertices A, P, and B will appear in a clockwise order.

This method uses the cross product of vectors PA and PB:

$$ a \times b = a_x b_y - a_y b_x $$

Since this method avoids division, it eliminates precision issues, making it stable for determining whether a segment is below a point.

Selecting the Closest Segment under Point

When multiple segments are positioned below point P, we need to determine which segment is the closest to P. This scenario can be divided into three distinct cases based on the configuration of the segments relative to P.

Left Case

Selecting the closest segment: shared left endpoint Two green segments share left endpoint A. Right endpoints B zero and B one determine which segment is closest below point P. P A B1 B0

When both segments share a common left vertex A, we check the positions of their right endpoints. If the vertices B0, B1, and A form a clockwise pattern, then AB0 is closer to P than AB1.

Right Case

Selecting the closest segment: shared right endpoint Two green segments share right endpoint B. Left endpoints A zero and A one determine which segment is closest below point P. P A0 B A1

When both segments share a common right vertex B, we check the positions of their left endpoints. If the vertices A0, A1, and B form a clockwise pattern, then A1B is closer to P than A0B.

Middle Case

Selecting the closest segment: overlapping horizontal ranges Green segments have overlapping horizontal ranges. Projected gold points and dashed guides compare their positions below point P. A1 P A0 B1 B0

In this case, one of the vertices (e.g., A1 or B0) lies inside the opposite segment. We use the point-segment comparison method to determine which of the segments is closer to P.