Algorithms time! In this post Melkman's algorithm of finding convex hull will be described. Checkout all the code at Github repo.

melkman algorithm

Introduction

So Melkman's algorithm is handy when we need to find convex hull of a simple polygonal chain (or simple polygon). It works in linear time but its obvious restriction – we must be sure that our chain has no intersections.

A simple polygonal chain is one in which only consecutive (or the first and the last) segments intersect and only at their endpoints. Wikipedia

The idea behind Melkman's algorithm is quite simple – we define initial hull (with first three points) and then step by step we examine points and check whether they lie inside our outside of the current hull. We skip inside points and for external points we rebuild current hull by popping last points and checking if current point locks hull to contain all previous points.

Implementation

You may noticed that we pop and push values of current hull so Deque data sctructure is used to store current hull points. As you know Ruby's implementation of Array is already a Deque, since we have these handy Array's methods:

As was mentioned before at each step we decide if next point lies inside or outside of the hull. To determine that we need to look if the next point lies from the left of the line formed by first and last points of the current hull (in the next picture 4th point lies from the left of 3-1 line so we should include it to convex hull):

convex hull check

Github repo

Check out all the code at https://github.com/makaroni4/melkman.

You will find algorithm #ruby implementation, code for generation random simple polygonal chain and #GIF animation.

#algo #algorithm