3 dimensional array sort Javascript

Question

I have already read several posts here and on other sites about using a custom sort function on multidimensional arrays but can't work out how to implement them for this case...

I am trying to use the painters algorithm...

face_list[num_face][num_vertex] = [2d_x, 2d_y, z, light_intensity]

How do I write the sort function such that the face_list is sorted by z?

I have tried

a=a[2][2]

b=b[2][2]

For third value of third array but the browser doesn't like it.

The sequence of [num_face] is what I want changed.

I've been puzzling over this for two days now and would appreciate help!

Thank you, Andrew

What is the error you are getting. What does a and b look like? — scrappedcola
– scrappedcola, Commented Mar 6, 2013 at 20:41

Amy · Accepted Answer · 2013-03-06 20:42:28Z

1

You can try this method of sorting, yes it's a custom sort function, but they're great. You get the values, in your case the z value, and keeps a list of the indices of each point, then sorts it by z.

Taken from: https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Array/sort#Example.3A_Sorting_maps

// the array to be sorted
var list = ["Delta", "alpha", "CHARLIE", "bravo"];
// temporary holder of position and sort-value
var map = [];
// container for the resulting order
var result = [];

// walk original array to map values and positions
for (var i=0, length = list.length; i < length; i++) {
  map.push({    
    // remember the index within the original array
    index: i, 
    // evaluate the value to sort
    value: list[i].toLowerCase() 
  });
}

// sorting the map containing the reduced values
map.sort(function(a, b) {
  return a.value > b.value ? 1 : -1;
});

// copy values in right order
for (var i=0, length = map.length; i < length; i++) {
  result.push(list[map[i].index]);
}

// print sorted list
print(result);

answered Mar 6, 2013 at 20:42

Amy

7,5262 gold badges22 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user1977132 Over a year ago

This looked promising but I then realised that it will not keep the vertices together. From the face_list[n][v] I need the vertices to stay ordered for each face. Its the faces I want to sort not the vertices.

user1977132 Over a year ago

Eureka! Thank you, despite my doubts an hour ago this answer did provide the direction which finally worked. I'd like to post the code but can't seem to work out how to post code in the comments box (yes I have read the help page "Indent four spaces to create an escaped <pre><code> block:" but can't work out how to do that.

Amy Over a year ago

@user1977132 Glad it could help. Btw you can update your original question and add the edits for your new code so others can benefit too

GameAlchemist · Accepted Answer · 2013-03-06 22:27:39Z

This should get you started.

(corresponding jsBin is here : http://jsbin.com/olegoj/1/edit )

// 3D points array.
var points=[];

var Vector=function(x,y,z) {
  this.x=x;
  this.y=y;
  this.z=z;
};

Vector.prototype.toString= function() {
  return (' x: ' + this.x + ' y: ' + this.y  + ' z : ' + this.z);
};

// returns a new vector translatedfrom ampVec * random 
Vector.prototype.createRandomShift= function(ampVec) {
    var thisRandom = Math.random()*0.9+0.1;
  return  new Vector(
      thisRandom*ampVec.x+this.x,
       thisRandom*ampVec.y+this.y,
        thisRandom*ampVec.z+this.z    );
};

var pointCount=20;

var pt = new Vector(Math.random()*100|0, Math.random()*100|0, Math.random()*100|0 );
var ampVec = new Vector(Math.random()*4-2, Math.random()*4-2, Math.random()*4 - 2);
var ampVecAmp = new Vector(Math.random()*2-1, Math.random()*2-1, Math.random()*2-1) ;

// fill the point array.
// based on the current point shifted randomly by ampVec
// ampVec itself is shifted randomly by ampVecAmp 
for(var i=0; i<pointCount; i++) {
   points.push(pt );
   pt=pt.createRandomShift(ampVec);
   ampVec=ampVec.createRandomShift(ampVecAmp);
}

// array of face. a face is an array of 3 point indexes.
var facelist=[];

var faceCount=10, i=faceCount;

// fill the face array
while(i--) {
    var thisFacePoints=[];
    var ip1 = 0;
    // 3 point indexes
    thisFacePoints.push(ip1=Math.random()*pointCount|0);
    thisFacePoints.push(Math.random()*pointCount|0);
    thisFacePoints.push(Math.random()*pointCount|0);
    facelist.push(thisFacePoints);
}

// returns the min z for a face
var minZ=function(f) {
    return Math.min(f[0].z, Math.min(f[1].z, f[2].z));
};

// returns the max z for a face                  
var maxZ=function(f) {
   return Math.max(f[0].z, Math.max(f[1].z, f[2].z));
};

// !!! sort the faces on Z !!!
facelist.sort(function(a,b) {
   if (maxZ(a) < minZ (b)) return 1;  // a fully below b
   if (minZ(b) < minZ(a) ) return -1;  // b fully below a
   // !!!!!!!!!!!!!!!!!!!!!!!!
   // in fact here is the tricky part :
   // here a and b overlap in Z.
  return trickyFaceZSort(a,b); 
 });

 // !!!!!! returns wether face a is < to face b when looking at Z (0,0,1).
//Required : a and b overlaps by Z.
var trickyFaceZSort= function(a,b) {
 // do some checks on projected(xi), projected(yi)  -> return 0 if no overlap
 // then you have the hardest part ahead : x,y and z overlap.
 return 0;
};

// Print sorted faces
for(var i=0; i<facelist.length; i++) {
    var fp=facelist[i];
console.log(' *** face ' + i + ' *** ');
console.log(' ** point 0 ' + points[fp[0]] + ' *** ');
console.log(' ** point 1 ' + points[fp[1]] + ' *** ');
console.log(' ** point 2 ' + points[fp[2]] + ' *** ');  
}

Collectives™ on Stack Overflow

3 dimensional array sort Javascript

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related