Andrew's monotone chain algorithm

Processing Coding Questions
1

Hello, I have a project for university about creating NURBs curves. One part of the code is Andrew’s monotone chain algorithm. And I have the code that doesn’t work, could anyone help me with that?
Thank you so much!

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

class Point implements Comparable {
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+")";
}

}

public class ConvexHull {

public static 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 static 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 static void main(String[] args) throws IOException {

	BufferedReader f = new BufferedReader(new FileReader("hull.in")); 	// "hull.in"  Input Sample => size x y x y x y x y
	StringTokenizer st = new StringTokenizer(f.readLine());
	Point[] p = new Point[Integer.parseInt(st.nextToken())];
	for (int i = 0; i < p.length; i++) {
		p[i] = new Point();
		p[i].x = Integer.parseInt(st.nextToken()); // Read X coordinate 
		p[i].y = Integer.parseInt(st.nextToken()); // Read y coordinate
	}
	
	Point[] hull = convex_hull(p).clone();
	
	for (int i = 0; i < hull.length; i++) {
		if (hull[i] != null)
			System.out.print(hull[i]);
	}
}

}

2

Please format your code :blush:

It consist on these two steps:

  1. In your code editor (PDE, VS code, Eclipse, etc) ensure you execute the beautifier function. This function automatically indents your code. Auto-indenting makes your code easier to read and helps catching bugs due to mismatch parenthesis, for instance. In the PDE, you use the key combination: ctrl+t
  2. You copy and paste your code in the forum. Then you select the code and you hit the formatting button aka. the button with this symbol: </>

That’s it! Please notice you do not create a new post in case you need to format something you already posted. You can edit your post, copy the code to the PDE, indent the code properly there and then past it back here, format the code and >> save << the edits.

Extra info:

Formatting your code makes everybody’s life easier, your code looks much better plus it ensures your code integrity is not affected by the forum’s formatting (Do you know the forum processes markup code?) Please visit the sticky posts or the FAQ section/post to learn about this, other advantages and super powers you can get in this brand new forum.

Kf

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