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];
    }

Excision

"has to output a minimum circumference of a convex hull of the polygon" For what it's worth, the convex hull is unique (i.e. there's only one), so I'm not sure what "minimum" you want to take. – Supercilious

Yeah, I'm sorry for not being clear. The program has to output a circumference of the convex hull, that's it. But if it is possible to create two convex hulls and the circumference of both is shorter than the circumference of one, it outputs a sum of those hulls. – Excision

Sounds reasonable. Do you mind editing the question to make that point a little more clear? – Supercilious

I think you meant to use hull1 + hull2 < big hull? – Binns

Also, I don't think it's possible to find a division such that the perimeter of the two hulls is less than the large one. This is probably mathematically provable in a few lines. – Binns

@Binns - what about <===> which can be split into < and >? that suggests that breaking the two largest non-contiguous edges might work. – Salinasalinas

I edited the question and added a simple image. Thanks guys. – Excision

@Clu: So, what is the input for the problem? Are you working with points or with polygons? What are you building the convex hull of? It is not clear from what you wrote above. In one part it seems to say that you are building a convex hull for polygon(s), in another - for points. Initially you say that you are given a polygon. Does that mean that you are allowed to cut that polygon into pieces to build the new convex hull? – Nutty

The input is a set of points so you have to construct a convex hull first. I'll post my source code to make it more clear, because I really don't know how to proceed. – Excision

@Clu: Firstly, your question begins with "It's given a polygon (point []) with Xi and Yi coordinates as an input. The program has to output circumference of a convex hull of the polygon...". What "polygon" are you talking about here? What is the importance of that polygon? Secondly, if you are simply given a set of scattered points, then the important question is how many convex nulls are you allowed to generate? Two? Three? As many as you want? – Nutty

There's written "there can't be more than two hulls". I mean that you have to construct a convex hull from the given set of points. But if it would be more efficient/ beneficial to build two hulls, you have to do so. And all this is because of the circumference, which has to be the shortest possible. I think the answer down there is correct, but I don't really know C++ so well to proceed. I ended at finding the diameter of a convex hull with rotating calipers. – Excision

You can create two convex hulls if it is beneficial, no more. – Excision

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)

Redistrict

Wow, that's like something I was looking for. I edited the question to make it more clear. There can be maximum of two hulls. But well, I'm not sure if I got it right. I need to find the farthers pair of points A and B, allright. Then I start to create hulls around those points ? I'm not sure what are rotating calipers and how to divide the points. – Excision

@Excision No, you start to create one hull for points left to dividing line, and another hull for points right to that line – Redistrict

Hi, I just returned to this problem, because I didn't have much time last days. Now I've constructed convex hull and calculated a circumference. I'm actually on my way to calculate the diameter, but could you give me some idea how to divide the points with middle perpendicular (I don't know whether it matters or not, but I'm programming in C++) ? – Excision

I have one more question. In calculation of "Middle point M = (A + B)/2 AB vector (B.X-A.X, B.Y-A.Y)" the (A + B)/2 is multiplied by vector (B.X-A.X, B.Y-A.Y) ? Sorry, I don't know much about vectors, I have been programming only in C recently. – Excision

No, it is not multiplied. Just reference. – Redistrict

Man, I understand your suggestion and I think your answer is correct. But I am not so skilled in C++, therefore I don't know how to implement rotating calipers and how to use vectors correctly. If you could just do that and post it here, I would be so happy. I uploaded what I coded so far. – Excision

Sorry, I don't know C++ well enough and I haven't implemented rotated calipers. But I suggest that there are implementations somewhere in the Internet – Redistrict

I succesfully implemented rotating calipers. Now I think this is the last thing I need to know. When calculating a middle point M, how can I get a sum of two points, if those points have X and Y values ? You didn't mention that in your post. Should it be M = (A.x - B.x)+ (A.y - B.y)/2 ? Sorry, if I'm misunderstanding something. Also, what are those two lines about the last equation about ? Thank you. – Excision

M description added. Two last lines are about the method to divide points to two parts – Redistrict

I'm dumb as f**k :D I wrote that on my whiteboard and I understood it immediately, but it was not so clear on the screen. Sorry again for bothering you. – Excision

One last question, I promise! Why it has to be AB vector, not just a point as M? Why is it important ? – Excision

Also, if I'm using only the last equation, why is middle point important for me if it's not there ? – Excision

I uploaded my implementation of the points division. Seems like it doesn't work for me. Could you please take a look ? – Excision

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.

Sabbatarian