Division of a convex hull into two separate parts

Question

I am trying to solve quite a difficult problem for me. I'm not new to programming, but I don't really know how to figure out this problem. It's given a set of points (point []) with Xi and Yi coordinates as an input. The program has to output circumference of a convex hull of the polygon, but if it is necessary, it can divide the hull into two parts, two separate convex hulls, for each will contain a number of points. The goal of this division is to have a shorter circumference (if a sum of circumference of those two hulls is shorter than circumference of one hull; for example: two clusters of points far away from each other). The problem also is that there can't be more than two hulls. I would appreciate any ideas.

There's a simple illustration of that problem (there could be a lot more points). Here you can see that circumference of two separated hulls is shorter than circumference of one.

ADD: Actually, by "circumference" I mean perimeter.

Here's the key part of my code:

m.x = (a.x + b.x)/2;
    m.y = (a.y + b.y)/2;

    ab.first = b.x - a.x;
    ab.second = b.y - a.y;

    for (i=0; i<n; ++i)
    {
        if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 > 0)
            left[l++]=p[i];
        else if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 < 0)
            right[r++]=p[i];
        if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 == 0)
            mid[md++]=p[i];
    }

Answer 1

It seems that two hulls will be beneficial when two (or more) long-separated clusters exist. So I would suggest to try a simple method (probably approximate):

construct convex hull
find the farthest pair of points (A, B) in hull with rotating calipers
divide all the points with middle perpendicular to AB segment
find hulls of resulted clouds and calculate profit or loss 

Added: finding the farthest pair of points with rotating calipers link

Added 2: How to divide point cloud with middle perpendicular:

Middle point: M = (A + B)/2
(M.X = (A.X + B.X)/2, M.Y = (A.Y + B.Y)/2 )

AB vector: (B.X-A.X, B.Y-A.Y)

Middle perpendicular line has general equation:

(y-M.Y) / AB.X = - (x-M.X) / AB.Y
(y-M.Y) * AB.Y + (x-M.X) * AB.X = 0
//incorrect  x * AB.X + y * AB.Y - (AB.Y^2 + AB.X^2)/2 = 0
x * AB.X + y * AB.Y - (B.Y^2 - A.Y^2 + B.X^2 - A.X^2)/2 = 0

When you use P[i].X and P[i].Y for every point instead of x and y in in the last equation, you'll get positive value for points to left, and negative value for points to right of line (and zero value for points on the line)

Answer 2

I agree with MBo that the trick is to find a wide spacing within which to cut the two hulls. But I don't agree that rotating calipers is the right approach. What you care about is not the outer dimensions, but the inner dimensions. If you have a very wide set of points which are organized into two parallel horizontal lines, you want to cut between the two lines, not halfway through each.

Essentially, I think you want to find a "thick" separating line, which cuts the point set into two pieces and which is as far separated from the points on both sides as possible. This is known as the "furthest hyperplane problem", and is normally used for an unsupervised variant of the Support Vector Machine algorithm.

This is a hard (NP-hard) problem, but there are approximation algorithms out there. The basic idea is to take many potential angles for the line, and figure out where to put a line of that angle to maximize its separation.