Convex Hull

Table of Contents

• Goal
• Theory
  • The algorithm
• Project configuration (CMake)
• Code
• Explanation
• Result

Compatibility	OpenCV >= 5.0

Goal

In this tutorial you will learn how to:

• Use the OpenCV function cv::convexHull (part of the geometry module in OpenCV 5.0) to find the convex hull of a 2D point set or contour.
• Link the new opencv_geometry module in your CMake project.

Theory

The convex hull of a set of points is the smallest convex polygon that contains all the points. To visualize this, imagine a rubber band stretched open to encompass all the given points; when released, it snaps around the outermost points, taking the shape of the convex hull.

The algorithm

OpenCV computes the hull using Sklansky's algorithm, which is highly efficient for 2D points:

• If the points are unsorted, the time complexity is \(O(N \log N)\).
• If the points are already sorted (for example, ordered contour points from cv::findContours), the complexity drops to \(O(N)\).

Note

In OpenCV 5.0 the computational-geometry algorithms were reorganized: functions such as cv::convexHull moved from imgproc to the new geometry module. C++ code must now include <opencv2/geometry.hpp>.

Project configuration (CMake)

Because OpenCV 5.0 moved these functions into a dedicated module, link opencv_geometry in your CMakeLists.txt alongside the standard modules:

cmake_minimum_required(VERSION 3.1)
project(ConvexHullDemo)
 
find_package(OpenCV REQUIRED)
 
add_executable(ConvexHullDemo convex_hull_demo.cpp)
target_link_libraries(ConvexHullDemo ${OpenCV_LIBS} opencv_geometry)

Code

C++

This tutorial code's is shown lines below. You can also download it from here

 
#include "opencv2/imgcodecs.hpp"
#include "opencv2/highgui.hpp"
#include "opencv2/geometry.hpp"
#include "opencv2/imgproc.hpp"
#include <iostream>
 
using namespace cv;
using namespace std;
 
Mat src_gray;
int thresh = 100;
RNG rng(12345);
 
void thresh_callback(int, void* );
 
int main( int argc, char** argv )
{
    CommandLineParser parser( argc, argv, "{@input | stuff.jpg | input image}" );
    Mat src = imread( samples::findFile( parser.get<String>( "@input" ) ) );
    if( src.empty() )
    {
        cout << "Could not open or find the image!\n" << endl;
        cout << "Usage: " << argv[0] << " <Input image>" << endl;
        return -1;
    }
 
    cvtColor( src, src_gray, COLOR_BGR2GRAY );
    blur( src_gray, src_gray, Size(3,3) );
 
    const char* source_window = "Source";
    namedWindow( source_window );
    imshow( source_window, src );
 
    const int max_thresh = 255;
    createTrackbar( "Canny thresh:", source_window, &thresh, max_thresh, thresh_callback );
    thresh_callback( 0, 0 );
 
    waitKey();
    return 0;
}
 
void thresh_callback(int, void* )
{
    Mat canny_output;
    Canny( src_gray, canny_output, thresh, thresh*2 );
 
    vector<vector<Point> > contours;
    findContours( canny_output, contours, RETR_TREE, CHAIN_APPROX_SIMPLE );
 
    vector<vector<Point> >hull( contours.size() );
    for( size_t i = 0; i < contours.size(); i++ )
    {
        convexHull( contours[i], hull[i] );
    }
 
    Mat drawing = Mat::zeros( canny_output.size(), CV_8UC3 );
    for( size_t i = 0; i< contours.size(); i++ )
    {
        Scalar color = Scalar( rng.uniform(0, 256), rng.uniform(0,256), rng.uniform(0,256) );
        drawContours( drawing, contours, (int)i, color );
        drawContours( drawing, hull, (int)i, color );
    }
 
    imshow( "Hull demo", drawing );
}

Java

This tutorial code's is shown lines below. You can also download it from here

import java.awt.BorderLayout;
import java.awt.Container;
import java.awt.Image;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
 
import javax.swing.BoxLayout;
import javax.swing.ImageIcon;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JSlider;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;
 
import org.opencv.core.Core;
import org.opencv.core.CvType;
import org.opencv.core.Mat;
import org.opencv.core.MatOfInt;
import org.opencv.core.MatOfPoint;
import org.opencv.core.Point;
import org.opencv.core.Scalar;
import org.opencv.core.Size;
import org.opencv.highgui.HighGui;
import org.opencv.imgcodecs.Imgcodecs;
import org.opencv.imgproc.Imgproc;
 
class Hull {
    private Mat srcGray = new Mat();
    private JFrame frame;
    private JLabel imgSrcLabel;
    private JLabel imgContoursLabel;
    private static final int MAX_THRESHOLD = 255;
    private int threshold = 100;
    private Random rng = new Random(12345);
 
    public Hull(String[] args) {
        String filename = args.length > 0 ? args[0] : "../data/stuff.jpg";
        Mat src = Imgcodecs.imread(filename);
        if (src.empty()) {
            System.err.println("Cannot read image: " + filename);
            System.exit(0);
        }
 
        Imgproc.cvtColor(src, srcGray, Imgproc.COLOR_BGR2GRAY);
        Imgproc.blur(srcGray, srcGray, new Size(3, 3));
 
        // Create and set up the window.
        frame = new JFrame("Convex Hull demo");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        // Set up the content pane.
        Image img = HighGui.toBufferedImage(src);
        addComponentsToPane(frame.getContentPane(), img);
        // Use the content pane's default BorderLayout. No need for
        // setLayout(new BorderLayout());
        // Display the window.
        frame.pack();
        frame.setVisible(true);
        update();
    }
 
    private void addComponentsToPane(Container pane, Image img) {
        if (!(pane.getLayout() instanceof BorderLayout)) {
            pane.add(new JLabel("Container doesn't use BorderLayout!"));
            return;
        }
 
        JPanel sliderPanel = new JPanel();
        sliderPanel.setLayout(new BoxLayout(sliderPanel, BoxLayout.PAGE_AXIS));
 
        sliderPanel.add(new JLabel("Canny threshold: "));
        JSlider slider = new JSlider(0, MAX_THRESHOLD, threshold);
        slider.setMajorTickSpacing(20);
        slider.setMinorTickSpacing(10);
        slider.setPaintTicks(true);
        slider.setPaintLabels(true);
        slider.addChangeListener(new ChangeListener() {
            @Override
            public void stateChanged(ChangeEvent e) {
                JSlider source = (JSlider) e.getSource();
                threshold = source.getValue();
                update();
            }
        });
        sliderPanel.add(slider);
        pane.add(sliderPanel, BorderLayout.PAGE_START);
 
        JPanel imgPanel = new JPanel();
        imgSrcLabel = new JLabel(new ImageIcon(img));
        imgPanel.add(imgSrcLabel);
 
        Mat blackImg = Mat.zeros(srcGray.size(), CvType.CV_8U);
        imgContoursLabel = new JLabel(new ImageIcon(HighGui.toBufferedImage(blackImg)));
        imgPanel.add(imgContoursLabel);
 
        pane.add(imgPanel, BorderLayout.CENTER);
    }
 
    private void update() {
        Mat cannyOutput = new Mat();
        Imgproc.Canny(srcGray, cannyOutput, threshold, threshold * 2);
 
        List<MatOfPoint> contours = new ArrayList<>();
        Mat hierarchy = new Mat();
        Imgproc.findContours(cannyOutput, contours, hierarchy, Imgproc.RETR_TREE, Imgproc.CHAIN_APPROX_SIMPLE);
 
        List<MatOfPoint> hullList = new ArrayList<>();
        for (MatOfPoint contour : contours) {
            MatOfInt hull = new MatOfInt();
            Imgproc.convexHull(contour, hull);
 
            Point[] contourArray = contour.toArray();
            Point[] hullPoints = new Point[hull.rows()];
            List<Integer> hullContourIdxList = hull.toList();
            for (int i = 0; i < hullContourIdxList.size(); i++) {
                hullPoints[i] = contourArray[hullContourIdxList.get(i)];
            }
            hullList.add(new MatOfPoint(hullPoints));
        }
 
        Mat drawing = Mat.zeros(cannyOutput.size(), CvType.CV_8UC3);
        for (int i = 0; i < contours.size(); i++) {
            Scalar color = new Scalar(rng.nextInt(256), rng.nextInt(256), rng.nextInt(256));
            Imgproc.drawContours(drawing, contours, i, color);
            Imgproc.drawContours(drawing, hullList, i, color );
        }
 
        imgContoursLabel.setIcon(new ImageIcon(HighGui.toBufferedImage(drawing)));
        frame.repaint();
    }
}
 
public class HullDemo {
    public static void main(String[] args) {
        // Load the native OpenCV library
        System.loadLibrary(Core.NATIVE_LIBRARY_NAME);
 
        // Schedule a job for the event dispatch thread:
        // creating and showing this application's GUI.
        javax.swing.SwingUtilities.invokeLater(new Runnable() {
            @Override
            public void run() {
                new Hull(args);
            }
        });
    }
}

Python

This tutorial code's is shown lines below. You can also download it from here

from __future__ import print_function
import cv2 as cv
import numpy as np
import argparse
import random as rng
 
rng.seed(12345)
 
def thresh_callback(val):
    threshold = val
 
    # Detect edges using Canny
    canny_output = cv.Canny(src_gray, threshold, threshold * 2)
 
    # Find contours
    contours, _ = cv.findContours(canny_output, cv.RETR_TREE, cv.CHAIN_APPROX_SIMPLE)
 
    # Find the convex hull object for each contour
    hull_list = []
    for i in range(len(contours)):
        hull = cv.convexHull(contours[i])
        hull_list.append(hull)
 
    # Draw contours + hull results
    drawing = np.zeros((canny_output.shape[0], canny_output.shape[1], 3), dtype=np.uint8)
    for i in range(len(contours)):
        color = (rng.randint(0,256), rng.randint(0,256), rng.randint(0,256))
        cv.drawContours(drawing, contours, i, color)
        cv.drawContours(drawing, hull_list, i, color)
 
    # Show in a window
    cv.imshow('Contours', drawing)
 
# Load source image
parser = argparse.ArgumentParser(description='Code for Convex Hull tutorial.')
parser.add_argument('--input', help='Path to input image.', default='stuff.jpg')
args = parser.parse_args()
 
src = cv.imread(cv.samples.findFile(args.input))
if src is None:
    print('Could not open or find the image:', args.input)
    exit(0)
 
# Convert image to gray and blur it
src_gray = cv.cvtColor(src, cv.COLOR_BGR2GRAY)
src_gray = cv.blur(src_gray, (3,3))
 
# Create Window
source_window = 'Source'
cv.namedWindow(source_window)
cv.imshow(source_window, src)
max_thresh = 255
thresh = 100 # initial threshold
cv.createTrackbar('Canny thresh:', source_window, thresh, max_thresh, thresh_callback)
thresh_callback(thresh)
 
cv.waitKey()

Explanation

• Include the headers. The demo includes imgproc.hpp for edge and contour detection and the new geometry.hpp for the convex-hull algorithm.
• Edge detection and contour extraction. Inside the trackbar callback the Canny edge detector finds the raw edges, and cv::findContours retrieves the boundary shapes.
• Compute the convex hull. For each contour, cv::convexHull computes its convex polygon. By default it takes the input point set and outputs the hull coordinates.
• Draw the results. Both the original contours and their bounding hulls are drawn with cv::drawContours on a blank image, each contour/hull pair sharing a random color.

Note

cv::convexHull(points, hull, clockwise, returnPoints) accepts two useful flags. clockwise orders the output points clockwise when true (default false). returnPoints returns hull coordinates when true (default); set it to false to get the indices of the original points instead — required if you later call cv::convexityDefects.

Result

After compiling and running with an input image, a window with a trackbar appears. As you adjust the Canny threshold, the contours are recomputed dynamically and drawn alongside their convex hulls, each matching pair sharing the same randomized color.