The happy Ender problem

Question

The happy ending problem (actually a theorem) states that

Any set of five points in the plane in general position has a subset of four points that form the vertices of a convex quadrilateral.

The problem was so named by Paul Erdős when two mathematicians who first worked on the problem, Ester Klein and George Szekeres, became engaged and subsequently married.

Clarifications:

• General position here means that no three points are collinear.

• The quadrilateral formed by the four vertices will always be considered to be non-intersecting, irrespective of the order of the points. For example, given the four points [1 1], [1 2], [2 1], [2 2] the intended quadrilateral is the square, not the bow-tie:

  

• A non-intersecting quadrilateral is convex if no interior angle exceeds 180 degrees; or equivalently if both diagonals lie inside the quadrilateral.

The challenge

Given 5 points with positive integer coordinates, output 4 of those points that form a convex quadrilateral.

Rules

If there are several solutions (that is, several sets of 4 points), you can consistently choose to output one of them or all.

Input and output formats are flexible as usual (arrays, lists, list of lists, strings with reasonable separators, etc).

Code golf, fewest bytes wins.

Test cases

1. Input:

   [6 8] [1 10] [6 6] [5 9] [8 10]
   

   There is only one possible output:

   [6 8] [1 10] [6 6] [5 9]
   

2. Input:

   [3 8] [7 5] [6 9] [7 8] [5 1]
   

   There are five solutions:

   [3 8] [7 5] [6 9] [7 8]
   [3 8] [7 5] [6 9] [5 1]
   [3 8] [7 5] [7 8] [5 1]
   [3 8] [6 9] [7 8] [5 1]
   [7 5] [6 9] [7 8] [5 1]
   

3. Input:

   [4 8] [1 9] [9 9] [10 2] [1 6]
   

   There are three solutions:

   [4 8] [1 9] [10 2] [1 6]
   [4 8] [9 9] [10 2] [1 6]
   [1 9] [9 9] [10 2] [1 6]
   

   To illustrate, here are the three solutions to this case:

Answer 1

CJam, 37 34 32 bytes

{e!Wf<{2*3ew{)f.-~W%.*:-V>},!}=}

Not sure if :-V is happy enough, but as K Zhang points out, there's the =} at the end. :)

This only prints one solution because removing duplicates would be more expensive.

Test it here.

Explanation

The idea is fairly simple. We generate all possible quadrilaterals (including all orderings of the points) and then just select the convex ones. We test convexity by looking at every pair of edges and checking that they're all turning in the same direction.

The turning sense can be obtained quite easily from a dot product. If you take the three consecutive points on a quadrilateral, and draw lines from the first to the second, and the first to the third, and then project the latter onto the perpendicular of the former... you get a number whose sign tells you whether these three points turn left or right. (I should probably add a diagram for this.) This "projecting onto the perpendicular" is sounds quite involved, but really just means that we reverse one of the two vectors and subtract the components after multiplication instead of adding them. So here's the code...

e!       e# Generate all permutations of the five input points.
Wf<      e# Discard the fifth point in each permutations, giving all
         e# possible quadrilaterals.
{        e# Select the first for which this block gives a truthy result...
  2*     e#   Double the list of points, so that it includes each cyclically
         e#   adjacent set of three points.
  3ew    e#   Get all sublists of length 3, i.e. all sets of three consecutive
         e#   points (with two duplicates).
  {      e#   Filter these sets of three points...
    )    e#     Pull off the last point.
    f.-  e#     Subtract it from the other two, giving vectors from it to
         e#     to those.
    ~    e#     Unwrap the array dumping both vectors on the stack.
    W%   e#     Reverse one of them.
    .*   e#     Element-wise multiplication.
    :-   e#     Subtract the second element from the first. This completes
         e#     the projection.
    V>   e#     Check whether it's greater than 0. This is *false* for right-
         e#     turning sets of three points.
  },     e#   If all corners are right-turning, this will result
         e#   in an empty array.
  !      e#   Logical NOT - hence, only quadrilaterals where all corners
         e#   are right-turning give something truthy.
}=

Answer 2

MATLAB, 67 bytes

I=input('');for k=~eye(5);if nnz(convhull(I(k,:)))>4;I(k,:),end;end

Input is in the form of a 2D matrix where the columns are X and Y respectively:

[6 8; 1 10; 6 6; 5 9; 8 10]
[3 8; 7 5; 6 9; 7 8; 5 1]
[4 8; 1 9; 9 9; 10 2; 1 6]

All sets of 4 points that create convex quadrilaterals are displayed in the same format.

Here is a demo that is slightly modified to work with Octave

Explanation

This solution takes all subsets of 4 points of the input (order doesn't matter). To do this, we create the identity matrix and negate it: ~eye(5). We loop through the columns of this matrix and k (the loop index) is a logical array which specifies which of the 4 points to consider. We then use this to grab these 4 XY points from the input (I(k,:)).

We then compute the convex hull of these 4 points (convhull). The output of convhull is the indices of the input that correspond with the points that make up the convex hull (with the first index duplicated to close the hull).

For a convex quadrilateral, all four points will be part of the convex hull of the same points (nnz(convhull(points)) > 4). If we detect that this is the case, we display the points that were used for this particular iteration.

Answer 3

Javascript (ES6), 306 293 283 bytes

c=(v,w,x)=>(w[0]-v[0])*(w[1]-x[1])-(w[1]-v[1])*(w[0]-x[0])>0?1:0
i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])
j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}
f=(v)=>(r=[],k(...v),r)

Explanation:

The function c computes the cross product of the vector between 3 adjacent points of the polygon and returns 1 if it is positive and 0 otherwise (note: the cross product cannot be zero as the points cannot be co-linear).

j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}

The function k and j generate all cyclic permutations (ignoring reversing the order) of the input array.

i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])

The function 'i' is then called for each cyclic permutation to calculate the sum of the function c for each of the 4 triplets of adjacent co-ordinates. If the cross products all have the same sign then they will all either be 0 or 1 and total to 0 (modulo 4) and the polygon is concave and is pushed into the output array. If any triplet has a different sign then the total will be non-zero (modulo 4) and the polygon is convex.

f=(v)=>(r=[],k(...v),r)

The function f is used to initialise the output array and then call the above functions before returning the output.

Tests:

c=(v,w,x)=>(w[0]-v[0])*(w[1]-x[1])-(w[1]-v[1])*(w[0]-x[0])>0?1:0
i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])
j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}
f=(v)=>(r=[],k(...v),r)

tests = [
  [[6,8],[1,10],[6,6],[5,9],[8,10]],
  [[3,8],[7,5],[6,9],[7,8],[5,1]],
  [[4,8],[1,9],[9,9],[10,2],[1,6]]
];

tests.forEach(
  (test,i)=>{
    console.log( "Test " + (i+1) );
    f(test).forEach(
      (x)=>console.log( "  " + x.map((e)=>"("+e[0]+","+e[1]+")").join(','))
    );
  }
);

Edit:

Can also handle co-linear points using the original version and changing the first two lines to:

t=(a,b,c)=>Math.sign((b[0]-a[0])*(b[1]-c[1])-(b[1]-a[1])*(b[0]-c[0]))
p=(a,b,c,d)=>[t(a,b,c),t(b,c,d),t(c,d,a),t(d,a,b)].filter(x=>x).reduce((p,c,i,a)=>p&c==a[0],1)
q=(a,m,n,o)=>[a[0],a[m],a[n],a[o]]
f=(a)=>{r=[];for(i=0;i<5;i++){b=a.slice();b.splice(i,1);r.push(q(b,1,2,3));r.push(q(b,1,3,2));r.push(q(b,2,1,3))}return r.filter((a)=>p(...a))}

However, since that case is specifically excluded in the question then the extra characters aren't necessary.

Answer 4

Mathematica 105 96 bytes

Select[#~Subsets~{4},f@#&]& selects, from a list of (5) points, those subsets of 4 points that satisfy f.

f is satisfied when each point, of the 4 points in a set, lies on the RegionBoundary of the ConvexHull of the 4 points.

f@p_:=Apply[And,RegionBoundary@ConvexHullMesh@p~RegionMember~#&/@p];
Select[#~Subsets~{4},f@#&]&

---

Test Cases

1. Let's look at at the 5 convex hulls of subsets (each of 4 points) of {{6, 8}, {1, 10}, {6, 6}, {5, 9}, {8, 10}}.

Select[#~Subsets~{4},f@#&[{{6, 8}, {1, 10}, {6, 6}, {5, 9}, {8, 10}}]

{{{6, 8}, {1, 10}, {6, 6}, {5, 9}}}

---

{{6, 8}, {1, 10}, {6, 6}, {5, 9}} is the only solution; each of the four points serves as a vertex of the convex hull (of the same 4 points).

---

{{6, 8}, {1, 10}, {6, 6},{8, 10}} is not a solution; the convex hull has only 3 vertices. {6, 8} lies within the hull.

---

The remaining subsets also are not solutions:

---

2. {{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}} has three solutions.

Select[#~Subsets~{4},f@#&[{{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}}]

{
{{4, 8}, {1, 9}, {10, 2}, {1, 6}},
{{4, 8}, {9, 9}, {10, 2}, {1, 6}},
{{1, 9}, {9, 9}, {10, 2}, {1, 6}}
}

---

3. {{3, 8}, {7, 5}, {6, 9}, {7, 8}, {5, 1}} has 5 solutions.

Select[#~Subsets~{4},f@#&[{{3, 8}, {7, 5}, {6, 9}, {7, 8}, {5, 1}}]

{
{{3, 8}, {7, 5}, {6, 9}, {7, 8}},
{{3, 8}, {7, 5}, {6, 9}, {5, 1}},
{{3, 8}, {7, 5}, {7, 8}, {5, 1}},
{{3, 8}, {6, 9}, {7, 8}, {5, 1}},
{{7, 5}, {6, 9}, {7, 8}, {5, 1}}
}

Note that each of the five points lies on the boundary of the convex hull of all points.

If any one of the points is removed, the remaining 4 points will each be vertices of the reduced convex hull.