# Why this Graham Scan algorithm of convex hull works wrong when number of points more than 10k

**URL:** <https://discourse.processing.org/t/why-this-graham-scan-algorithm-of-convex-hull-works-wrong-when-number-of-points-more-than-10k/37749>\
**Category:** Coding Questions\
**Created:** [June 28, 2022, 6:10pm UTC](https://discourse.processing.org/t/why-this-graham-scan-algorithm-of-convex-hull-works-wrong-when-number-of-points-more-than-10k/37749 "2022-06-28T18:10:12Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![obry](https://avatars.discourse-cdn.com/v4/letter/o/87869e/32.png) [@obry](https://discourse.processing.org/u/obry)\
**Post date:** [June 28, 2022, 6:10pm UTC](https://discourse.processing.org/t/why-this-graham-scan-algorithm-of-convex-hull-works-wrong-when-number-of-points-more-than-10k/37749/1 "2022-06-28T18:10:12Z")

</div>

Here is the code. It works fine with 10k and less.  
NUM variable it is number of points

```auto
import java.util.Arrays;
import java.util.Comparator;

ArrayList<PVector> init, sorted;
int NUM = 10000;
int border = 100;
void setup() {
	size(600, 600);
	background(205);
	
	//noLoop();
	// exit();
}
void newConvex(){
	init = new ArrayList<PVector>();
	// strokeWeight(2);
	int index = -1;
	float maxY = -1;
	float prevMax = maxY;
	for (int i = 0; i < NUM; i++) {
		PVector p = new PVector(border+random(width-2*border),border+random(height-2*border));
		init.add(p);
		// point(p.x, p.y);
		maxY=max(maxY, init.get(i).y);
		if (maxY!=prevMax) {
			index = i;
			prevMax = maxY;
		}
	}
	sorted = new ArrayList<PVector>();
	sorted.add(init.get(index));
	float[][] angles = new float[init.size()-1][2];
  PVector p0 = sorted.get(0);
	int j=0;
	for (int i = 0; i < init.size(); ++i) {
		PVector p = init.get(i);
		if (i!=index) {
			PVector a = PVector.sub(p,p0);
			angles[j][0] = a.heading();
			angles[j][1] = i;
			j++;
		}
	}
	Arrays.sort(angles, new Comparator<float[]>(){
		int compare(float[] a, float[] b) {
			return Float.compare(a[0],b[0]);
		}
	});
	sorted.add(init.get(int(angles[0][1])));
	for (int i = 0; i < init.size()-1; ++i) {
  if(i!=int(angles[0][1])) {
		PVector pp = sorted.get(sorted.size()-2);
		PVector p = sorted.get(sorted.size()-1);
		PVector p1 = init.get(int(angles[i][1]));
		PVector a = PVector.sub(p1,p);
		PVector b = PVector.sub(p,pp);
		PVector c = b.cross(a);
			while (c.z<0) {
        sorted.remove(sorted.size()-1);
				pp = sorted.get(sorted.size()-2);
				p = sorted.get(sorted.size()-1);
				a = PVector.sub(p1,p);
				b = PVector.sub(p,pp);
				c = b.cross(a);
			}
      sorted.add(init.get(int(angles[i][1])));
		}
    
		// text(i,init.get(int(angles[i][1])).x, init.get(int(angles[i][1])).y);
	}

	strokeWeight(1);
  stroke(0);
	noFill();
	beginShape();
	for (PVector p : sorted) {
		vertex(p.x, p.y);
	}
	endShape(CLOSE);
}

void drawPoints(){
  strokeWeight(1);
  stroke(0);
  noFill();
  for (PVector p : init) {
    point(p.x, p.y);
  }
}

void draw() {
  background(205);
	newConvex();
  drawPoints();
	
}

```

---

<div class="post-metadata">

**Author:** ![josephh](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/josephh/32/210_2.png) [@josephh](https://discourse.processing.org/u/josephh)\
**Post date:** [June 28, 2022, 6:21pm UTC](https://discourse.processing.org/t/why-this-graham-scan-algorithm-of-convex-hull-works-wrong-when-number-of-points-more-than-10k/37749/2 "2022-06-28T18:21:03Z")

</div>

Hi @obry,

Welcome to the forum! 😉

When I run the code it does that:

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/3X/c/8/c8d6c9866bec1d42f6f7b9829d614506734da060.png)

It looks like it’s working (convex hull of a dense point cloud approximate a square), could you describe precisely the behavior you are seeing?

---

<div class="post-metadata">

**Author:** ![obry](https://avatars.discourse-cdn.com/v4/letter/o/87869e/32.png) [@obry](https://discourse.processing.org/u/obry)\
**Post date:** [June 29, 2022, 8:54am UTC](https://discourse.processing.org/t/why-this-graham-scan-algorithm-of-convex-hull-works-wrong-when-number-of-points-more-than-10k/37749/3 "2022-06-29T08:54:21Z")

</div>

Yep. Everything works fine almost always. But as the number of points grows more than 10000 the more bugs like this come up

 ![convex](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/3X/e/5/e564a592270bba8f5ee469ebda284244ebdd49cb.jpeg)  
In this example I don’t draw points, only convex hull. The thing is that it is not convex as you see.  
I wander if it is bug in algorithm. Maybe the reason is that some points are so close that this happens, which I doubt. Probably, the real reason is wrong algorithm

---

<div class="post-metadata">

**Author:** ![josephh](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/josephh/32/210_2.png) [@josephh](https://discourse.processing.org/u/josephh)\
**Post date:** [June 29, 2022, 10:42am UTC](https://discourse.processing.org/t/why-this-graham-scan-algorithm-of-convex-hull-works-wrong-when-number-of-points-more-than-10k/37749/4 "2022-06-29T10:42:46Z")

</div>

I tried with different values ranging from `10_000` to `100_000` and it seems to appear randomly. Maybe it’s a rounding error caused by the proximity of the points as you said so when you compare the angles, it breaks…

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [June 29, 2022, 10:48am UTC](https://discourse.processing.org/t/why-this-graham-scan-algorithm-of-convex-hull-works-wrong-when-number-of-points-more-than-10k/37749/5 "2022-06-29T10:48:23Z")

</div>

Like @josephh I tried your code and as you increase the number of points the more frequent the artifacts. I even tried with 100,000 points and although the artifact appeared more often it didn’t happen all the time.

This tells me that the problem almost certainly not the algorithm, it is something to do with the data set.

I suspect that some of the intermediate calculations are producing NaN(s) I had this problem using `float`s and had to uses `double`s instead.

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [June 29, 2022, 12:21pm UTC](https://discourse.processing.org/t/why-this-graham-scan-algorithm-of-convex-hull-works-wrong-when-number-of-points-more-than-10k/37749/6 "2022-06-29T12:21:36Z")

</div>

In your method `newConvex` you have this conditional statement

> [@obry](#):
>
> `if (maxY!=prevMax) {`

You should test 2 floating point number for equality (`==`) or inequality (`!=`) because it can lead to logical errors. What would you expect from this sketch?

```auto
float a, b, c;
a = 3.1415927;
b = 3.1415928;
c = 3.1415926;
println(a == b);
println(a == c);

```

You get

```auto
true
false

```

which is obviously wrong.

You can improve the first part of the `newConvex` method to avoid this issue and also improve efficiency by avoiding reading from the list like this -

```auto
void newConvex(){
  init = new ArrayList<PVector>();
  // strokeWeight(2);
  int index = -1;
  float maxY = -1;
  for (int i = 0; i < NUM; i++) {
    PVector p = new PVector(border+random(width-2*border),border+random(height-2*border));
    init.add(p);
    if (p.y > maxY) {
      index = i;
      maxY = p.y;
    }
  }

```

BTW this does not get rid of the visual artifact unfortunately

---

<div class="post-metadata">

**Author:** ![obry](https://avatars.discourse-cdn.com/v4/letter/o/87869e/32.png) [@obry](https://discourse.processing.org/u/obry)\
**Post date:** [June 30, 2022, 9:38am UTC](https://discourse.processing.org/t/why-this-graham-scan-algorithm-of-convex-hull-works-wrong-when-number-of-points-more-than-10k/37749/7 "2022-06-30T09:38:33Z")

</div>

Thank you, guys!  
Seems like this is the case.  
I appreciate your help.