Convex Hull Jarvis march and Graham scan

[nowy20180820]

https://ideone.com/mK1Xj7

//I tried to place code in tags but it was too long

Can I get the same efect without allocating memory for another linked list ?


In CLRS Introduction to algorithms I found pseudocode for Graham scan

   1.  Let p_{0} be the point in Q with the minimum y-coordinate
         or the leftmost such point in case of tie
   2.  Let <p_{1},p_{2},...,p_{m}> be the remaining points in Q,
           sorted by polar angle in counterclockwise order around p_{0}
           ( if more then one point has the same angle, remove all but
             the one that is farthest from p_{0})
   3.  Let S be an empty stack
   4.  PUSH(p_{0},S)
   5.  PUSH(p_{1},S)
   6.  PUSH(p_{2},S)
   7.  for i = 3 to m 
   8.        while the angle formed by points NEXT-TO-TOP(S),TOP(S)
                       and p_{i} makes a nonleft turn 
   9.           POP(S)
   10.       PUSH(p_{i},S)
   11. return S

and linked list that I have has too few functions for Graham scan

Step 1. can be realized by loop and comparing y coordinates and x coordinates
in case of a tie
When we find such node we delete it from linked list and insert
at the head of the linked list
Step 2. Here linked list I have is missing two functions
Sorting function
Remove duplicates function
For sorting function i thought about
Natural merge sort with comparator function passed as parameter
For remove duplicates it will be enough to move duplicates
to the end of the linked list and return pointer
to the tail of sublist with unique keys

To realize conditiion from Step 8. we have to know when angle
makes a nonleft turn

Notes for Natural merge sort

Key values of nodes of linked list create sequence
Before sorting we have subsequences which are already sorted
We distribute sorted sequences alternately into two linked lists
How we can detect end of sorted subsequence ?
a) We reached tail node
b) current->key > current->next->key (or current->prev->key > current->key)
Stop condition is checked after division step
(if second list is empty after division step we can stop)
We merge sorted subsequences
After merge procedure sorted subsequences are longer so
division and merge steps have to be repeated

[ne555]

- you should encapsulate the functions for insert and remove a node
- Solve() is a terrible name
- comment your code
- don't call destructors, they are called automatically when the object goes out of scope


> Can I get the same efect without allocating memory for another linked list ?
not going to bother to analyse your code to figure out if you are duplicating points
you may do graham's scan inplace by erasing the points that are not in the convex hull
you may also splice your list of points into two list: convex-hull points and no-convex-hull points
or you may duplicate the points or store a reference to them to have a list with all the points and a list with points in the convex hull
not sure what you have now or what you want.

[nowy20180820]

What I want ?

Linked List which I have does not have functions for STEP 2
in Graham scan pseudocode from CLRS Introduction to algorithms
and I would like to know how to write them

Natural merge sort function and
function which move duplicates to the end allow me to
realize step 2 of Graham scan

Step 2 is the most time consuming part of algorithm

And additional question

Why we cannot generalize Graham scan to higher dimensions