How to sort points cyclically?

Questions
1

csort

I have a bunch of distinct points which are on a plane in an array.
I want to sort them such that they are in order around their center calculated by average (cyclic/acyclic).


// attempt at getting the angle with execssive care to avoid 
// unexpected change
function getAngle(v1, v2) {
	let aV1 = v1.clone();
	let aV2 = v2.clone();
	aV1.normalize();
	aV2.normalize();
	let theta = Math.acos( aV1.dot(aV2) );
	let cr = aV1.clone();
	cr.cross(aV2);
	let bV1 = v1.clone();
	let bV2 = v2.clone();
	bV1.normalize();
	bV2.normalize();
	let n = bV1.clone();
	n.cross(bV2);
	let d = cr.dot(n);
	if (d < 0) theta = -theta;
	return theta;
}

function getVector(p1, p2) {
	let dir = new THREE.Vector3();
	dir.subVectors( p2, p1 );
	return dir.normalize();
}

function toDeg(rad) {
	let deg = rad * 57.2958;
	deg = (deg >= 0) ? deg : (180 + (180 + deg));
	return deg;
}



function sortPoints(pts, c, n = new THREE.Vector3(0, 1, 0)) {

	let ret = [];
	let vs = [];
        // get vectors fron the center to each point
	for (let i = 0; i < pts.length; i++) {
		vs.push(getVector(pts[i], c));
	}

	// calculate angle of each vector from the first one
	let angs = [ 0 ];
	for (let i = 1; i < vs.length; i++) {
		angs.push(toDeg(getAngle(vs[0], vs[i])));
	}

	// build angle to point mapping
	let list = [];
	for (let j = 0; j < pts.length; j++) 
	    list.push({'pt': pts[j], 'ang': angs[j]});

	// sort points based on angles
	list.sort(function(a, b) {
	    return ((a.ang < b.ang) ? -1 : ((a.ang == b.ang) ? 0 : 1));
	});

	// build return list
	for (let k = 0; k < list.length; k++) {
	    pts[k] = list[k].pt;
	    angs[k] = list[k].ang;
	}

	ret = pts;
	return ret;
}

This example has all the points on the XY-plane but it could be any arbitrary plane.

Sample

2

Your question is a bit unclear to me. Without a reference vector in the plane, it’s not possible to sort the points in a deterministic way. It’s not related to your problem but you might want to study how the Graham Scan works, an algorithm for finding the convex hull for a set of points. It also performs sorting based on angles.

Probably the easiest way is to represent your plane as a coordinate system where you consider the normal of the plane as the forward vector. The up vector would be the reference vector. If you transform the points in the coordinate space of the plane, you should be able to use the dot product in order to compute a value for sorting. The actual angle value in radians or degree is not necessary. You would perform the dot product with each of your points and the reference vector.

1 Like
3

Right. Sorry I forgot to mention that part in the write up.
The method I am using to derive the reference vector is:

  • Average all the points to get point C
  • Create a vector from C to any of the points and use that as a vector.

My issue I think is this function. I would like it to return angles by measuring consistently on one side of the reference vector (image below).

image
image555×502 63.4 KB

  • Green is the reference vector you mentioned
  • angle a between point 1 and 6 is what I don’t want
  • angle b is what I want

Thanks for the link on Graham Scan. I would eventually like to use the vertices of the hull to get C. But that’s for later.
The method above would work fine for me now since the points are somewhat evenly distributed around an imaginary center.