I would like an algorithm to calculate the convex hull of 4 2D points. I have looked at the algorithms for the generalized problem, but I wonder if there is a simple solution for 4 points.

# R – Convex hull of 4 points

algorithmcomputational-geometryconvex-hullgraphics

#### Related Solutions

I'll do my best to explain it here on simple terms, but be warned that this topic takes my students a couple of months to finally grasp. You can find more information on the Chapter 2 of the Data Structures and Algorithms in Java book.

There is no mechanical procedure that can be used to get the BigOh.

As a "cookbook", to obtain the BigOh from a piece of code you first need to realize that you are creating a math formula to count how many steps of computations get executed given an input of some size.

The purpose is simple: to compare algorithms from a theoretical point of view, without the need to execute the code. The lesser the number of steps, the faster the algorithm.

For example, let's say you have this piece of code:

```
int sum(int* data, int N) {
int result = 0; // 1
for (int i = 0; i < N; i++) { // 2
result += data[i]; // 3
}
return result; // 4
}
```

This function returns the sum of all the elements of the array, and we want to create a formula to count the computational complexity of that function:

```
Number_Of_Steps = f(N)
```

So we have `f(N)`

, a function to count the number of computational steps. The input of the function is the size of the structure to process. It means that this function is called such as:

```
Number_Of_Steps = f(data.length)
```

The parameter `N`

takes the `data.length`

value. Now we need the actual definition of the function `f()`

. This is done from the source code, in which each interesting line is numbered from 1 to 4.

There are many ways to calculate the BigOh. From this point forward we are going to assume that every sentence that doesn't depend on the size of the input data takes a constant `C`

number computational steps.

We are going to add the individual number of steps of the function, and neither the local variable declaration nor the return statement depends on the size of the `data`

array.

That means that lines 1 and 4 takes C amount of steps each, and the function is somewhat like this:

```
f(N) = C + ??? + C
```

The next part is to define the value of the `for`

statement. Remember that we are counting the number of computational steps, meaning that the body of the `for`

statement gets executed `N`

times. That's the same as adding `C`

, `N`

times:

```
f(N) = C + (C + C + ... + C) + C = C + N * C + C
```

There is no mechanical rule to count how many times the body of the `for`

gets executed, you need to count it by looking at what does the code do. To simplify the calculations, we are ignoring the variable initialization, condition and increment parts of the `for`

statement.

To get the actual BigOh we need the Asymptotic analysis of the function. This is roughly done like this:

- Take away all the constants
`C`

. - From
`f()`

get the polynomium in its`standard form`

. - Divide the terms of the polynomium and sort them by the rate of growth.
- Keep the one that grows bigger when
`N`

approaches`infinity`

.

Our `f()`

has two terms:

```
f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1
```

Taking away all the `C`

constants and redundant parts:

```
f(N) = 1 + N ^ 1
```

Since the last term is the one which grows bigger when `f()`

approaches infinity (think on limits) this is the BigOh argument, and the `sum()`

function has a BigOh of:

```
O(N)
```

There are a few tricks to solve some tricky ones: use summations whenever you can.

As an example, this code can be easily solved using summations:

```
for (i = 0; i < 2*n; i += 2) { // 1
for (j=n; j > i; j--) { // 2
foo(); // 3
}
}
```

The first thing you needed to be asked is the order of execution of `foo()`

. While the usual is to be `O(1)`

, you need to ask your professors about it. `O(1)`

means (almost, mostly) constant `C`

, independent of the size `N`

.

The `for`

statement on the sentence number one is tricky. While the index ends at `2 * N`

, the increment is done by two. That means that the first `for`

gets executed only `N`

steps, and we need to divide the count by two.

```
f(N) = Summation(i from 1 to 2 * N / 2)( ... ) =
= Summation(i from 1 to N)( ... )
```

The sentence number *two* is even trickier since it depends on the value of `i`

. Take a look: the index i takes the values: 0, 2, 4, 6, 8, ..., 2 * N, and the second `for`

get executed: N times the first one, N - 2 the second, N - 4 the third... up to the N / 2 stage, on which the second `for`

never gets executed.

On formula, that means:

```
f(N) = Summation(i from 1 to N)( Summation(j = ???)( ) )
```

Again, we are counting **the number of steps**. And by definition, every summation should always start at one, and end at a number bigger-or-equal than one.

```
f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )
```

(We are assuming that `foo()`

is `O(1)`

and takes `C`

steps.)

We have a problem here: when `i`

takes the value `N / 2 + 1`

upwards, the inner Summation ends at a negative number! That's impossible and wrong. We need to split the summation in two, being the pivotal point the moment `i`

takes `N / 2 + 1`

.

```
f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )
```

Since the pivotal moment `i > N / 2`

, the inner `for`

won't get executed, and we are assuming a constant C execution complexity on its body.

Now the summations can be simplified using some identity rules:

- Summation(w from 1 to N)( C ) = N * C
- Summation(w from 1 to N)( A (+/-) B ) = Summation(w from 1 to N)( A ) (+/-) Summation(w from 1 to N)( B )
- Summation(w from 1 to N)( w * C ) = C * Summation(w from 1 to N)( w ) (C is a constant, independent of
`w`

) - Summation(w from 1 to N)( w ) = (N * (N + 1)) / 2

Applying some algebra:

```
f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )
f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )
=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )
=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 =
(N / 2 - 1) * (N / 2) / 2 =
((N ^ 2 / 4) - (N / 2)) / 2 =
(N ^ 2 / 8) - (N / 4)
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )
f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + C * N
f(N) = C * 1/4 * N ^ 2 + C * N
```

And the BigOh is:

```
O(N²)
```

This link might be helpful to you, as it details the use of the Haversine formula to calculate the distance.

Excerpt:

This script [in Javascript] calculates great-circle distances between the two points – that is, the shortest distance over the earth’s surface – using the ‘Haversine’ formula.

```
function getDistanceFromLatLonInKm(lat1,lon1,lat2,lon2) {
var R = 6371; // Radius of the earth in km
var dLat = deg2rad(lat2-lat1); // deg2rad below
var dLon = deg2rad(lon2-lon1);
var a =
Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) *
Math.sin(dLon/2) * Math.sin(dLon/2)
;
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
var d = R * c; // Distance in km
return d;
}
function deg2rad(deg) {
return deg * (Math.PI/180)
}
```

###### Related Question

- How to create a URL shortener?
- What does O(log n) mean exactly
- Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
- Ukkonen’s suffix tree algorithm in plain English
- C++ – Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
- How to find time complexity of an algorithm
- How to pair socks from a pile efficiently
- The optimal algorithm for the game 2048

## Best Solution

Take three of the points, and determine whether their triangle is clockwise or counterclockwise::

For a right-handed coordinate system, this value will be positive if ABC is counterclockwise, negative for clockwise, and zero if they are collinear. But, the following will work just as well for a left-handed coordinate system, as the orientation is relative.

Compute comparable values for three triangles containing the fourth point:

If all three of {ABD,BCD,CAD} have the same sign as ABC, then D is inside ABC, and the hull is triangle ABC.

If two of {ABD,BCD,CAD} have the same sign as ABC, and one has the opposite sign, then all four points are extremal, and the hull is quadrilateral ABCD.

If one of {ABD,BCD,CAD} has the same sign as ABC, and two have the opposite sign, then the convex hull is the triangle with the same sign; the remaining point is inside it.

If any of the triangle values are zero, the three points are collinear and the middle point is not extremal. If all four points are collinear, all four values should be zero, and the hull will be either a line or a point. Beware of numerical robustness problems in these cases!

For those cases where ABC is positive: