Search code examples
javaalgorithmconvex-hull

Merging two convex hulls

I'm currently writing a divide and conquer version of the Convex Hull algorithm and it's very close to working but am having trouble merging two convex hulls (to form the overall convex hull).

I'm merging by:

  • Computing Upper & Lower Hulls for each Input Hull, A and B
  • Finding the combined upper hull by ensuring right turns
  • Finding the combined lower hull by ensuring left turns
  • Computing the union of the 2 combined hulls

I'm not 100% sure if this is the right way to do it - any guidance or pseudocode for finding combined upper/lower hulls?

Solution

  • check this out; it'll give you very clever approaches to convex hull manipulation

    https://web.archive.org/web/20120617005317/http://moais.imag.fr/membres/denis.trystram/SupportsDeCours/convexHull.pdf