At around the same time of the Jarvis March, R. L. Graham was also developing an algorithm to find the convex hull of a random set of points {{ "gs1972" | cite }}.
Unlike the Jarvis March, which is an
Rather than starting at the leftmost point like the Jarvis March, the Graham scan starts at the bottom. We then sort the distribution of points based on the angle between the bottom-most point, the origin, and each other point. After sorting, we go through point-by-point, searching for points that are on the convex hull and throwing out any other points. We do this by looking for counter-clockwise rotations. If an angle between three points turns inward, the shape is obviously not convex, so we can throw that result out. We can find whether a rotation is counter-clockwise with trigonometric functions or by using a cross-product, like so:
{% method %} {% sample lang="jl" %} import:6-8, lang:"julia" {% sample lang="hs" %} import:6-7, lang:"haskell" {% sample lang="c" %} import:24-26, lang:"c" {% sample lang="js" %} import:36-38, lang:"javascript" {% sample lang="py" %} import:4-6, lang:"python" {% sample lang="go" %} import:13-15, lang:"go" {% sample lang="java" %} import:27-29, lang:"java" {% sample lang="lisp" %} import:5-13, lang:"lisp" {% sample lang="cpp" %} import:18-20, lang="cpp" {% sample lang="coco" %} import:4-8, lang="coconut" {% sample lang="rs" %} import:33-35, lang: "rust" {% endmethod %}
If the output of this function is 0, the points are collinear. If the output is positive, then the points form a counter-clockwise "left" turn. If the output is negative, then the points form a clockwise "right" turn. We basically do not want clockwise rotations, because this means we are at an interior angle.
To save memory and expensive append() operations, we ultimately look for points that should be on the hull and swap them with the first elements in the array.
If there are
{% method %} {% sample lang="jl" %} import:10-45, lang:"julia" {% sample lang="hs" %} import:9-18, lang:"haskell" {% sample lang="c" %} import:65-95, lang:"c" {% sample lang="js" %} import:1-30, lang:"javascript" {% sample lang="py" %} import:14-28, lang:"python" {% sample lang="go" %} import:21-42, lang:"go" {% sample lang="java" %} import:35-70, lang:"java" {% sample lang="lisp" %} import:15-58, lang:"lisp" {% sample lang="cpp" %} import:26-62, lang="cpp" {% sample lang="coco" %} import:17-30, lang="coconut" {% sample lang="rs" %} import:42-61, lang: "rust" {% endmethod %}
{% references %} {% endreferences %}
{% method %} {% sample lang="jl" %} import, lang:"julia" {% sample lang="hs" %} import, lang:"haskell" {% sample lang="c" %} import, lang:"c" {% sample lang="js" %} import, lang:"javascript" {% sample lang="py" %} import, lang:"python" {% sample lang="go" %} import, lang:"go" {% sample lang="java" %} import, lang:"java" {% sample lang="lisp" %} import, lang:"lisp" {% sample lang="cpp" %} import, lang="cpp" {%sample lang="coco" %} import, lang="coconut" {% sample lang="rs" %} import, lang: "rust" {% endmethod %}
<script> MathJax.Hub.Queue(["Typeset",MathJax.Hub]); </script>The code examples are licensed under the MIT license (found in LICENSE.md).
The text of this chapter was written by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.
After initial licensing (#560), the following pull requests have modified the text or graphics of this chapter:
- none