# Discrete Algoritmen

Table of Content
---
- Introduction
- Implementation
- Comparison

1.Introduction
---

Computing the convex hull means that a non-ambiguous and efficient representation of the required
convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in
terms of n, the number of input points, and sometimes also in terms of h, the number of points on the
convex hull

2.Implementation
---
### Graham scan

This algorithm has a time complexicity of O(n.log n).

1. Select the bottom most point.
2. Sort the points according polar angle.
3. Place the frist 3 points on stack
4. For each point:
- Using the last 2 points of stack caclulate the angle. If the angle is bigger than 180 degrees, place the second last point on the stack. repeat until angle is smaller than 180 or stack is empty
- Add point to stack
– Voeg het beschouwde punt toe aan de stack.
• De stack bevat nu alle punten die tot de convex omhullende behoren.

### Jarvis Walk
This algorithm only takes maximally 0.17s on our datasets, thus can also be seen as a fast algorithm. It works by, from the point of view of the point, continuously taking the leftmost point. To determine this point, the cross-product formula from line-segment properties is used.
Some visualizations in OpenGL were performed, to check the resulting convex hull.

Quick check on a simple test that I wrote:

This was an easy way to check if it works, but evidently it also needs to work on a bigger set of points.


Here we can see that it also correctly works on a $40\%$ mixed dataset of 20,000 points. We can clearly see that the convex hull is now shaped as a circle. This behaviour depends on which distribution we sample our points from. If we were to take 20,000 points from a uniform real distribution, we can clearly see a rectangular shape.


### QuickHull

QuickHull is a fast and efficient algorithm for computing the convex hull of a set of points. The algorithm is based on a divide-and-conquer.

In brief, the QuickHull algorithm follows these steps:

1. Identify the points with minimum and maximum x coordinates, which are always part of the convex hull. If multiple points have the same minimum/maximum x, use the ones with minimum/maximum y, respectively.
2. Use the line formed by these two points to divide the set into two subsets of points, which will be processed recursively.
3. Determine the part of the hull above and below the line
4. Find the point above the line with the maximum distance from the line, forming a triangle with the two points on the line.Exclude points inside the triangle, as they cannot be part of the convex hull.
5. Recursively repeat previous steps on the two lines formed by the two new sides of the triangle.
6. Continue this process until no more points are left, and the recursion ends. The selected points form the convex hull.

### QuickHullDisk

Quickhulldisk is an algorithm to determine the convex hull of a set of disks. It is based of the quickhull algorithm and uses the same concept but has some edge cases due to the added complexity of disks. We used the formula to compute the tangent of two disks as stated [here](https://en.wikipedia.org/wiki/Tangent_lines_to_circles#Outer_tangent), used the formula to compute the intersection of a line and a circle as stated [here](//https://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle). We also used the formula for the point on a circle given a distance and a slope, to compute the apex point, as stated [here](https://math.stackexchange.com/a/2812330)


3.Comparison
---

The mixed dataset have a percentage of random points. So a higher percentage, increases the randomness
in thedata set.