7

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. enter image description here

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];
    }
  • "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. – Dennis Meng Oct 31 '13 at 22:36
  • 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. –  Oct 31 '13 at 22:59
  • Sounds reasonable. Do you mind editing the question to make that point a little more clear? – Dennis Meng Oct 31 '13 at 23:33
  • I think you meant to use `hull1 + hull2 < big hull`? – sdasdadas Nov 01 '13 at 00:03
  • 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. – sdasdadas Nov 01 '13 at 00:07
  • 1
    @sdasdadas - what about `<===>` which can be split into `<` and `>`? that suggests that breaking the two largest non-contiguous edges might work. – andrew cooke Nov 01 '13 at 00:20
  • I edited the question and added a simple image. Thanks guys. –  Nov 01 '13 at 10:46
  • @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? – AnT stands with Russia Nov 10 '13 at 16:21
  • 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. –  Nov 10 '13 at 16:30
  • @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? – AnT stands with Russia Nov 10 '13 at 16:34
  • 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. –  Nov 10 '13 at 16:37
  • You can create two convex hulls if it is beneficial, no more. –  Nov 10 '13 at 16:38

2 Answers2

4

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

enter image description here

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)

MBo
  • 77,366
  • 5
  • 53
  • 86
  • 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. –  Nov 01 '13 at 10:41
  • @user2943215 No, you start to create one hull for points left to dividing line, and another hull for points right to that line – MBo Nov 01 '13 at 11:13
  • 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++) ? –  Nov 06 '13 at 21:26
  • 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. –  Nov 09 '13 at 18:50
  • No, it is not multiplied. Just reference. – MBo Nov 10 '13 at 15:58
  • 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. –  Nov 10 '13 at 17:00
  • 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 – MBo Nov 11 '13 at 02:31
  • 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. –  Nov 14 '13 at 17:32
  • M description added. Two last lines are about the method to divide points to two parts – MBo Nov 14 '13 at 17:55
  • 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. –  Nov 14 '13 at 17:59
  • One last question, I promise! Why it has to be AB vector, not just a point as M? Why is it important ? –  Nov 14 '13 at 19:08
  • Also, if I'm using only the last equation, why is middle point important for me if it's not there ? –  Nov 14 '13 at 22:42
  • I uploaded my implementation of the points division. Seems like it doesn't work for me. Could you please take a look ? –  Nov 14 '13 at 23:05
1

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.

Sneftel
  • 40,271
  • 12
  • 71
  • 104