Skip to content

Latest commit

 

History

History
55 lines (43 loc) · 1.95 KB

README.md

File metadata and controls

55 lines (43 loc) · 1.95 KB
Raw

Convex Hull

This project is trying to implement convex hull by using Graham's Scan Algorithm.

Convex Hull

Given a group of points, the set of convex hull is the smallest convex polygon that contain all the points. The example and the result of the program show as below:

File name: convex_hull_implementation.py
Command line: python convex_hull_implementation.py 


NOTE: 
  - the green dots are random points and the blue line is the "convex hull" of the points
  - the corner with no green dot is the start points, because for image the origin of coordinates 
    is on the top-left. Is the same as to find the bottommost + leftmost in the Coordinate System.

Graham's Scan Algorithm

Time Complexity: O(nlogn)

The process demo of Graham's scann show as below (from Wikipedia)

Part 1: sort the points

(a) Find the start points: This project find the (smallest x, smallest y) as start points.

(b) Sort the points: This project calculate angle(theta) to sort the points, if points have same angle use distance to sort.

NOTE: any sorting algorithm can apply to this part, this project using merge sort. 
      * time complexity O(nlogn)

Part 2: Algorithm to consider the point in convex set or not

(a) Select last two points(P1, P2) in convex hull and a points(P3).

(b) If (P2[0]-P1[0]) * (P3[1]-P1[1]) - (P2[1]P1[1]) * (P3[0]-P1[0]) <= 0, P2 is not in convex hull.

Code

License

This project is licensed under the MIT License - see the LICENSE.md file for details

Acknowledgments