Convex hull

As explained in Advanced Algorithms and Data Structures

A convex hull is the smallest convex set containing a given set or geometric shape.

A convex hull is the smallest convex set containing a shape. For a Bézier curve, the hull forms a polygon whose vertices are the endpoints and control points. section 15.4.4

In Bézier intersection testing, compare the curves’ convex hulls first. Non-overlapping hulls prove that the curves do not intersect; overlapping hulls require further subdivision. section 15.4.4

A subdivision-based intersection procedure proceeds as follows:

• Construct a convex hull around each Bézier curve from its endpoints and control points. section 15.4.4
• Discard curve pairs whose hulls do not overlap. section 15.4.4
• Split overlapping curves repeatedly until their sections are small enough to approximate with line segments, then test segment intersections. section 15.4.4

Figure 15.24 The Bézier subdivision method in action (first iteration). The points shown are the actual control points of cubic curves. This method can obviously also be applied to quadratic, quartic, or generic curves.

Shows Bézier subdivision and the control points used to form the curves’ convex hulls. section 15.4.4

How Advanced Algorithms and Data Structures covers it

How deep it goes

Defines the hull and outlines recursive subdivision, but defers detailed Bézier clipping and formal derivations.

Examples

Uses quadratic and cubic Bézier curves whose control points define polygons for overlap comparison.

What it assumes

Assumes familiarity with Bézier curves, endpoints, control points, and segment-intersection testing.

What you can do after

Apply Bézier subdivision to reject nonintersecting curves and reduce remaining cases to segment tests.

How it connects

Connects convex hulls with Bézier curves, control points, Bézier subdivision, and line-segment intersection testing.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Optimization Algorithms: AI techniques for design, planning, and control problemsThe convex hull problem is the computational problem of finding the smallest convex boundary containing a given set of points.
• 

  liveBookmanning.com
  Sutskever's ListA convex hull is the smallest convex set containing a given set of points.
• 

  liveBookmanning.com
  Outlier Detection in PythonAn iterative outlier-detection method that assigns scores according to the successive layers of a convex hull around the data points.

Compare how 4 books explain convex hull →

Related concepts

• Bézier subdivisionused by · Bézier subdivision is a technique that recursively splits Bézier curves into smaller curve sections for geometric analysis.
• anomaly scoreproduces · An anomaly score is a numerical measure of how anomalous an observation or event is relative to a reference or expected pattern.
• high-dimensional datacontrasts with · High-dimensional data consists of observations represented by a large number of features, variables, coordinates, or other dimensions.
• SciPyuses · SciPy is an open-source Python library providing algorithms and numerical utilities for scientific and technical computing.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.