# Andrew's monotone chain algorithm

**URL:** <https://discourse.processing.org/t/andrews-monotone-chain-algorithm/5485>\
**Category:** Coding Questions\
**Created:** [November 12, 2018, 7:38pm UTC](https://discourse.processing.org/t/andrews-monotone-chain-algorithm/5485 "2018-11-12T19:38:19Z")\
**Posts on this page:** 1\
**Showing post:** 3

<div class="post-metadata">

**Author:** ![kll](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/kll/32/964_2.png) [@kll](https://discourse.processing.org/u/kll)\
**Post date:** [November 13, 2018, 2:46pm UTC](https://discourse.processing.org/t/andrews-monotone-chain-algorithm/5485/3 "2018-11-13T14:46:09Z")

</div>

you could also just link to the code source!

[https://en.wikibooks.org/wiki/Algorithm\_Implementation/Geometry/Convex\_hull/Monotone\_chain#Java](https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#Java)

i play little bit with it and made some test data in subdir  
/data/hull.in

```auto
0 3
2 3
1 1
2 1
3 0
0 0
3 3

```

and changed to

> loadStrings  
> and the setup is doing all and print to console, not more

```auto
// https://discourse.processing.org/t/andrews-monotone-chain-algorithm/5485

// https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

import java.util.Arrays;

ConvexHull myset;

class Point implements Comparable<Point> {
  int x, y;

  public int compareTo(Point p) {
    if (this.x == p.x) {
      return this.y - p.y;
    } else {
      return this.x - p.x;
    }
  }

  public String toString() {
    return "("+x + "," + y+")";
  }
}

class ConvexHull {

  public long cross(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
  }

  public Point[] convex_hull(Point[] P) {

    if (P.length > 1) {
      int n = P.length, k = 0;
      Point[] H = new Point[2 * n];

      Arrays.sort(P);

      // Build lower hull
      for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) <= 0)
          k--;
        H[k++] = P[i];
      }

      // Build upper hull
      for (int i = n - 2, t = k + 1; i >= 0; i--) {
        while (k >= t && cross(H[k - 2], H[k - 1], P[i]) <= 0)
          k--;
        H[k++] = P[i];
      }
      if (k > 1) {
        H = Arrays.copyOfRange(H, 0, k - 1); // remove non-hull vertices after k; remove k - 1 which is a duplicate
      }
      return H;
    } else if (P.length <= 1) {
      return P;
    } else {
      return null;
    }
  }

  public void make(String[] lines) {
    println(" point array: ");
    Point[] p = new Point[lines.length];
    for (int i = 0; i < p.length; i++) {
      String[] vals = split(lines[i], ' ');
      p[i] = new Point();
      p[i].x = int(vals[0]); // Read X coordinate 
      p[i].y = int(vals[1]); // Read y coordinate
      println(p[i]);
    }
    println(" hull: ");
    Point[] hull = convex_hull(p).clone();
    for (int i = 0; i < hull.length; i++) {
      if (hull[i] != null)
        println(hull[i]);
    }
  }
}

String infile = "hull.in";

void setup() {
  size(500, 500); 
  println("read file: /data/"+infile);
  String[] lines = loadStrings(infile); 
  println("there are " + lines.length + " lines");
  for (int i = 0; i < lines.length; i++) {
    println(lines[i]);
  }

  myset = new ConvexHull();
  myset.make(lines);
}

/*
// input:
/data/hull.in
0 3
2 3
1 1
2 1
3 0
0 0
3 3

// output:
read file: /data/hull.in
there are 7 lines
0 3
2 3
1 1
2 1
3 0
0 0
3 3
 point array: 
(0,3)
(2,3)
(1,1)
(2,1)
(3,0)
(0,0)
(3,3)
 hull: 
(0,0)
(3,0)
(3,3)
(0,3)

*/

```

but i did not try to understand that code, not ask me!

and now i need google for “NURBs curves” ?

---

_[View the full topic](https://discourse.processing.org/t/andrews-monotone-chain-algorithm/5485)._