Separation of the convex hull into two separate parts

Question

I am trying to solve a rather difficult problem for me. I am not new to programming, but I really don't know how to understand this problem. He gave a set of points (point []) with the coordinates Xi and Yi as input. The program should draw the circle of the convex hull of the polygon, but if necessary, it can divide the body into two parts, two separate convex hulls, each of which will contain several points. The purpose of this separation is to have a shorter circle (if the sum of the circumferences of these two buildings is shorter than the circumference of one body, for example: two clusters of points far apart). The problem is also that there can be no more than two buildings. I would be grateful for any ideas.

There is a simple illustration of this problem (there may be much more points). Here you can see that the circumference of the two separated enclosures is shorter than the circumference of one.

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

Here is the key part of my code:

mx = (ax + bx)/2; my = (ay + by)/2; ab.first = bx - ax; ab.second = by - ay; 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 enclosures will be useful when there are two (or more) separated by long clusters. Therefore, I would suggest trying a simple method (probably an approximate one):

 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: find the farthest pair of points with rotating calipers

Added 2: How to split a point cloud with a middle perpendicular:

Midpoint: M = (A + B) / 2
(MX = (AX + BX) / 2, MY = (AY + BY) / 2)

AB vector: (BX-AX, BY-AY)

The middle perpendicular line has the general equation:

 (yM.Y) / AB.X = - (xM.X) / AB.Y (yM.Y) * AB.Y + (xM.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 - (BY^2 - AY^2 + BX^2 - AX^2)/2 = 0 

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

Answer 2

I agree with MBo that the trick is to find a wide span in which two cases can be cut. But I do not agree that rotating calipers are the right approach. What you care about is not external dimensions, but internal dimensions. If you have a very wide range of points that are organized in two parallel horizontal lines, you want to cut between two lines, not halfway through each.

Essentially, I think you want to find a “thick” dividing line that cuts the point into two parts and which is as far from the points on both sides as possible. This is known as the “farthest hyperplane problem” and is commonly used for an uncontrolled version of the vector machine support algorithm.

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