Andrew's monotone chain algorithm

Processing Coding Questions
3

you could also just link to the code source!

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

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

// 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” ?