Data Modelling & AI Data Structure & Algorithm

Perimeter of Convex hull for a given set of points

23 June 2025

2

Given n 2-D points points[], the task is to find the perimeter of the convex hull for the set of points. A convex hull for a set of points is the smallest convex polygon that contains all the points. Examples:

Input: points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}} Output: 12 Input: points[] = {{0, 2}, {2, 1}, {3, 1}, {3, 7}} Output: 15.067

Approach: Monotone chain algorithm constructs the convex hull in O(n * log(n)) time. We have to sort the points first and then calculate the upper and lower hulls in O(n) time. The points will be sorted with respect to x-coordinates (with respect to y-coordinates in case of a tie in x-coordinates), we will then find the left most point and then try to rotate in clockwise direction and find the next point and then repeat the step until we reach the rightmost point and then again rotate in the clockwise direction and find the lower hull. We will then find the perimeter of the convex hull using the points on the convex hull which can be done in O(n) time as the points are already sorted in clockwise order. Below is the implementation of the above approach:

CPP

// C++ implementation of the approach
#include <bits/stdc++.h>
#define llu long long int
using namespace std;
 
struct Point {
 
    llu x, y;
 
    bool operator<(Point p)
    {
        return x < p.x || (x == p.x && y < p.y);
    }
};
 
// Cross product of two vectors OA and OB
// returns positive for counter clockwise
// turn and negative for clockwise turn
llu cross_product(Point O, Point A, Point B)
{
    return (A.x - O.x) * (B.y - O.y)
        - (A.y - O.y) * (B.x - O.x);
}
 
// Returns a list of points on the convex hull
// in counter-clockwise order
vector<Point> convex_hull(vector<Point> A)
{
    int n = A.size(), k = 0;
 
    if (n <= 3)
        return A;
 
    vector<Point> ans(2 * n);
 
    // Sort points lexicographically
    sort(A.begin(), A.end());
 
    // Build lower hull
    for (int i = 0; i < n; ++i) {
 
        // If the point at K-1 position is not a part
        // of hull as vector from ans[k-2] to ans[k-1]
        // and ans[k-2] to A[i] has a clockwise turn
        while (k >= 2
            && cross_product(ans[k - 2], 
                            ans[k - 1], A[i]) <= 0)
            k--;
        ans[k++] = A[i];
    }
 
    // Build upper hull
    for (size_t i = n - 1, t = k + 1; i > 0; --i) {
 
        // If the point at K-1 position is not a part
        // of hull as vector from ans[k-2] to ans[k-1]
        // and ans[k-2] to A[i] has a clockwise turn
        while (k >= t
            && cross_product(ans[k - 2], 
                        ans[k - 1], A[i - 1]) <= 0)
            k--;
        ans[k++] = A[i - 1];
    }
 
    // Resize the array to desired size
    ans.resize(k - 1);
 
    return ans;
}
 
// Function to return the distance between two points
double dist(Point a, Point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x)
                + (a.y - b.y) * (a.y - b.y));
}
 
// Function to return the perimeter of the convex hull
double perimeter(vector<Point> ans)
{
    double perimeter = 0.0;
 
    // Find the distance between adjacent points
    for (int i = 0; i < ans.size() - 1; i++) {
        perimeter += dist(ans[i], ans[i + 1]);
    }
 
    // Add the distance between first and last point
    perimeter += dist(ans[0], ans[ans.size() - 1]);
 
    return perimeter;
}
 
// Driver code
int main()
{
    vector<Point> points;
 
    // Add points
    points.push_back({ 0, 3 });
    points.push_back({ 2, 2 });
    points.push_back({ 1, 1 });
    points.push_back({ 2, 1 });
    points.push_back({ 3, 0 });
    points.push_back({ 0, 0 });
    points.push_back({ 3, 3 });
 
    // Find the convex hull
    vector<Point> ans = convex_hull(points);
 
    // Find the perimeter of convex polygon
    cout << perimeter(ans);
 
    return 0;
}

Java

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Point {
    int x, y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
class Main {
    static int cross_product(Point o, Point a, Point b) {
        return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
    }
 
    static List<Point> convex_hull(List<Point> points) {
        int n = points.size();
        if (n <= 3)
            return points;
 
        Collections.sort(points, new Comparator<Point>() {
            @Override
            public int compare(Point p1, Point p2) {
                if (p1.x == p2.x)
                    return p1.y - p2.y;
                return p1.x - p2.x;
            }
        });
 
        Point[] ans = new Point[2 * n];
        int k = 0;
 
        // Build lower hull
        for (int i = 0; i < n; i++) {
            while (k >= 2 && cross_product(ans[k-2], ans[k-1], points.get(i)) <= 0)
                k--;
            ans[k++] = points.get(i);
        }
 
        // Build upper hull
        int t = k + 1;
        for (int i = n-2; i >= 0; i--) {
            while (k >= t && cross_product(ans[k-2], ans[k-1], points.get(i)) <= 0)
                k--;
            ans[k++] = points.get(i);
        }
 
        List<Point> result = new ArrayList<>();
        for (int i = 0; i < k-1; i++)
            result.add(ans[i]);
        return result;
    }
 
    static double dist(Point a, Point b) {
        return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
    }
 
    static double perimeter(List<Point> points) {
        int n = points.size();
        double perimeter = 0.0;
        for (int i = 0; i < n-1; i++)
            perimeter += dist(points.get(i), points.get(i+1));
        perimeter += dist(points.get(0), points.get(n-1));
        return perimeter;
    }
 
    public static void main(String[] args) throws java.lang.Exception {
        List<Point> points = new ArrayList<>();
        points.add(new Point(0, 3));
        points.add(new Point(2, 2));
        points.add(new Point(1, 1));
        points.add(new Point(2, 1));
        points.add(new Point(3, 0));
        points.add(new Point(0, 0));
        points.add(new Point(3, 3));
 
        List<Point> convex_points = convex_hull(points);
        System.out.println(perimeter(convex_points));
    }
}

Python3

from typing import List
from math import sqrt
 
class Point:
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y
 
def cross_product(o: Point, a: Point, b: Point) -> int:
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
 
def convex_hull(points: List[Point]) -> List[Point]:
    n = len(points)
    if n <= 3:
        return points
 
    points.sort(key=lambda p: (p.x, p.y))
    ans = [None] * (2 * n)
 
    # Build lower hull
    k = 0
    for i in range(n):
        while k >= 2 and cross_product(ans[k-2], ans[k-1], points[i]) <= 0:
            k -= 1
        ans[k] = points[i]
        k += 1
 
    # Build upper hull
    t = k + 1
    for i in range(n-2, -1, -1):
        while k >= t and cross_product(ans[k-2], ans[k-1], points[i]) <= 0:
            k -= 1
        ans[k] = points[i]
        k += 1
 
    ans = ans[:k-1]
    return ans
 
def dist(a: Point, b: Point) -> float:
    return sqrt((a.x - b.x) ** 2 + (a.y - b.y) ** 2)
 
def perimeter(points: List[Point]) -> float:
    n = len(points)
    perimeter = 0.0
    for i in range(n-1):
        perimeter += dist(points[i], points[i+1])
    perimeter += dist(points[0], points[n-1])
    return perimeter
 
# Driver code
points = [Point(0, 3), Point(2, 2), Point(1, 1), Point(2, 1), Point(3, 0), Point(0, 0), Point(3, 3)]
convex_points = convex_hull(points)
print(perimeter(convex_points))

Javascript

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}
 
function crossProduct(o, a, b) {
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
 
function convexHull(points) {
  let n = points.length;
  if (n <= 3) {
    return points;
  }
 
  points.sort((a, b) => a.x - b.x || a.y - b.y);
  let ans = new Array(2 * n).fill(null);
 
  // Build lower hull
  let k = 0;
  for (let i = 0; i < n; i++) {
    while (k >= 2 && crossProduct(ans[k-2], ans[k-1], points[i]) <= 0) {
      k--;
    }
    ans[k] = points[i];
    k++;
  }
 
  // Build upper hull
  let t = k + 1;
  for (let i = n - 2; i >= 0; i--) {
    while (k >= t && crossProduct(ans[k-2], ans[k-1], points[i]) <= 0) {
      k--;
    }
    ans[k] = points[i];
    k++;
  }
 
  ans = ans.slice(0, k-1);
  return ans;
}
 
function dist(a, b) {
  return Math.sqrt((a.x - b.x) ** 2 + (a.y - b.y) ** 2);
}
 
function perimeter(points) {
  let n = points.length;
  let perimeter = 0.0;
  for (let i = 0; i < n - 1; i++) {
    perimeter += dist(points[i], points[i+1]);
  }
  perimeter += dist(points[0], points[n-1]);
  return perimeter;
}
 
// Driver code
let points = [new Point(0, 3), new Point(2, 2), new Point(1, 1), new Point(2, 1), new Point(3, 0), new Point(0, 0), new Point(3, 3)];
let convex_points = convexHull(points);
console.log(perimeter(convex_points));

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class Point {
    public int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
class MainClass {
   
      // Cross product of two vectors OA and OB
    // returns positive for counter clockwise
    // turn and negative for clockwise turn
    static int cross_product(Point o, Point a, Point b) {
        return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
    }
 
      // Returns a list of points on the convex hull
    // in counter-clockwise order
    static List<Point> convex_hull(List<Point> points) {
        int n = points.Count;
        if (n <= 3)
            return points;
 
        points.Sort((p1, p2) => {
            if (p1.x == p2.x)
                return p1.y - p2.y;
            return p1.x - p2.x;
        });
 
        Point[] ans = new Point[2 * n];
        int k = 0;
 
        // Build lower hull
        for (int i = 0; i < n; i++) {
           
              // If the point at K-1 position is not a part
            // of hull as vector from ans[k-2] to ans[k-1]
            // and ans[k-2] to A[i] has a clockwise turn
            while (k >= 2 && cross_product(ans[k-2], ans[k-1], points[i]) <= 0)
                k--;
            ans[k++] = points[i];
        }
 
        // Build upper hull
        int t = k + 1;
        for (int i = n-2; i >= 0; i--) {
           
              // If the point at K-1 position is not a part
            // of hull as vector from ans[k-2] to ans[k-1]
            // and ans[k-2] to A[i] has a clockwise turn
            while (k >= t && cross_product(ans[k-2], ans[k-1], points[i]) <= 0)
                k--;
            ans[k++] = points[i];
        }
 
        List<Point> result = new List<Point>();
        for (int i = 0; i < k-1; i++)
            result.Add(ans[i]);
        return result;
    }
   
    // Function to return the distance between two points
    static double dist(Point a, Point b) {
        return Math.Sqrt(Math.Pow(a.x - b.x, 2) + Math.Pow(a.y - b.y, 2));
    }
   
    // Function to return the perimeter of the convex hull
    static double perimeter(List<Point> points) {
        int n = points.Count;
        double perimeter = 0.0;
        for (int i = 0; i < n-1; i++)
            perimeter += dist(points[i], points[i+1]);
        perimeter += dist(points[0], points[n-1]);
        return perimeter;
    }
   
    // Driver code
    public static void Main(string[] args) {
        List<Point> points = new List<Point>();
       
          // Add points
        points.Add(new Point(0, 3));
        points.Add(new Point(2, 2));
        points.Add(new Point(1, 1));
        points.Add(new Point(2, 1));
        points.Add(new Point(3, 0));
        points.Add(new Point(0, 0));
        points.Add(new Point(3, 3));
        // Find the convex hull
        List<Point> convex_points = convex_hull(points);
       
          // Find the perimeter of convex polygon
        Console.WriteLine(perimeter(convex_points));
    }
}

Output:

Time Complexity : O(nlogn), where n is the number of points in the input vector.

Auxiliary Space Complexity : O(n), where n is the number of points in the input vector.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Perimeter of Convex hull for a given set of points

CPP

Java

Python3

Javascript

C#

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US