Práctica 3: Hash

int grid = 0;

ArrayList<Particula> particulas;

float dt = 1/60.0;

float radio = 5.0;

int num_part = 0;

Bordes bordes;

Tabla_Hash hash;

int tam_celda = 0;

int tam_tabla = 0;

boolean comprobar = false;

int Tdraw1, Tdraw2;

int Tcomp1, Tcomp2;

​

void setup(){

  size (600+1,600+1);

  particulas = new ArrayList<Particula>();

  bordes = new Bordes();

  tam_celda = width/6;

  tam_tabla = width;

  grid = tam_celda;

}

void draw(){

  Tdraw1 = millis();

  background(0);

  //Tabla

  for (int i = 0; i <= 600; i+=grid) {

    stroke(255);

    line (i, 0, i, 600);

  }

  for (int i = 0; i <= 600; i+=grid) {

    line (0, i, 600, i);

  }

  hash = new Tabla_Hash(tam_celda, tam_tabla);

  Tcomp1 = millis();

  for (int i=0;i<particulas.size();i++){

    Particula p = particulas.get(i);

    hash.insertar(p.loc, p);

    p.update();

  //Vecinos

  ArrayList<Particula> part_vecinas = new ArrayList<Particula>();

    PVector locV = p.loc.get();

    //Celda de arriba-izquierda

    locV = p.loc.get();

    locV.x -= tam_celda;

    locV.y += tam_celda;

    part_vecinas.addAll(hash.comprobar(locV));

    //Celda de arriba

    locV = p.loc.get();

    locV.y -= tam_celda;

    part_vecinas.addAll(hash.comprobar(locV));

    //Celda de arriba-derecha

    locV = p.loc.get();

    locV.x += tam_celda;

    locV.y += tam_celda;

    part_vecinas.addAll(hash.comprobar(locV));

    //Celda de la izquierda

    locV = p.loc.get();

    locV.x -= tam_celda;

    part_vecinas.addAll(hash.comprobar(locV));

    //Celda actual

    locV = p.loc.get();

    part_vecinas.addAll(hash.comprobar(locV));

    //Celda de la derecha

    locV = p.loc.get();

    locV.x += tam_celda;

    part_vecinas.addAll(hash.comprobar(locV));

    //Celda de abajo-izquierda

    locV = p.loc.get();

    locV.x -= tam_celda;

    locV.y -= tam_celda;

    part_vecinas.addAll(hash.comprobar(locV));

    //Celda de abajo

    locV = p.loc.get();

    locV.y += tam_celda;

    part_vecinas.addAll(hash.comprobar(locV));

    //Celda de abajo-derecha

    locV = p.loc.get();

    locV.x += tam_celda;

    locV.y -= tam_celda;

    part_vecinas.addAll(hash.comprobar(locV));  

    for (int j=0; j<part_vecinas.size(); j++){

      Particula q = part_vecinas.get(j);

      if (p != q){

        p.collision(q);

      }

    }

  p.run(hash.hash(locV));

  }

  bordes.run();

  Tcomp2 = millis();

  Tdraw2 = millis();

  fill(255);

  text("frame rate: "+frameRate,15,15);

  text("N: "+num_part,15,50);

  text("Tdraw: "+(Tdraw2-Tdraw1),15,70);

  text("Tcomp: "+(Tcomp2-Tcomp1),15,90);

}

void mousePressed(){

    /*PVector pos;

    pos = new PVector(mouseX,mouseY);

    Particula p = new Particula(pos);

    particulas.add(p);

    comprobar = true;*/

    PVector pos;

    pos = new PVector(300,300);

    for(int i=0; i<1000; i++)

    {

      pos.x++;

      if(pos.x>=600){

        pos.y++;

        pos.x = 300;

      }

      Particula p = new Particula(pos);

      particulas.add(p);

      num_part++;

    }

}

class Bordes {

  ArrayList<Plano> planos;

  Bordes()

  {

    planos = new ArrayList<Plano>();

    Plano arriba = new Plano(width/3, 2, width-width/3, 2);

    Plano abajo = new Plano(width/3, height-1-2, width-width/3, height-1-2);

    Plano izq = new Plano(2, height/3, 2, height-width/3);

    Plano der = new Plano(width-2, height/3, width-2, height-width/3);

    Plano esquina1 = new Plano(2, height/3, width/3, 2);

    Plano esquina2 = new Plano(width-width/3, 2, width-2, height/3);

    Plano esquina3 = new Plano(2, height-width/3, width/3, height-1-2);

    Plano esquina4 = new Plano(width-width/3, height-1-2, width-2, height-width/3);

    planos.add(arriba);

    planos.add(abajo);

    planos.add(izq);

    planos.add(der);

    planos.add(esquina1);

    planos.add(esquina2);

    planos.add(esquina3);

    planos.add(esquina4);

  }

  void run()

 {

   update();

   display();

 } 

  void update()

  {

    for (int i = 0; i<planos.size(); i++) {

       Plano p = planos.get(i);

       for (int j=0;j<particulas.size();j++){

          Particula b = particulas.get(j);

          p.checkCollisions(b); 

       }

    }

  }

  void display()

  {

      stroke(255,0,0);

      //fill(100);

      strokeWeight(4);

      for (int i=0;i<planos.size();i++){

        Plano p = planos.get(i);

        line(p.ini.x, p.ini.y, p.fin.x, p.fin.y);

      }

  }

}

class Particula

{

  float m = 2.0;

  PVector loc;

  PVector vel;

  PVector a; //aceleracion

  float r;

  PVector g;

  float Kr = 0.5;

  Particula(PVector posicion)

  {

    loc = posicion.get();

    vel = new PVector( random(-100,100), random(-100,100) );

    a = new PVector();

    g = new PVector(0,0);

    r = radio;

  }

  void applyForce(PVector fuerza)

  {

    PVector f = PVector.div(fuerza.get(),m);

    a.add(f);

  }

  void run(int tipo_color)

  {

    update();

    display(tipo_color);

  }

  void update() //Metodo Euler(semi)

  {

    applyForce(g);

    vel.add(PVector.mult(a,dt));

    loc.add(PVector.mult(vel,dt));

    a.set(0,0);

  }

  void display(int tipo_color)

  {

    fill(0,175,0);

    if(tipo_color>200)

    fill(175,0,0);

   // if(tipo_color%2 == 1 & tipo_color<12 & tipo_color>5)

   // fill(0,0,175);

    noStroke();

    ellipse(loc.x, loc.y, 2*r, 2*r);

  }  

  //Colisiones

  void collision(Particula b){

    PVector dist = PVector.sub(loc, b.loc);

    // Detección   

    if (dist.mag() < (r + b.r) ) {

      //La velocidad normal

      //normal vel1

      float proyeccion;

      if(vel.mag() == 0 || dist.mag() == 0)

        proyeccion = 0;

      else

        proyeccion = vel.dot(dist)/dist.mag();

      PVector v_unit = dist.get();

      v_unit.normalize();

      v_unit.mult(proyeccion);

      PVector normal_vel1 = v_unit;

      //normal vel2

      if(b.vel.mag() == 0 || dist.mag() == 0)

        proyeccion = 0;

      else

        proyeccion = b.vel.dot(dist)/dist.mag();

      v_unit = dist.get();

      v_unit.normalize();

      v_unit.mult(proyeccion);

      PVector normal_vel2 = v_unit;

      //Velocidad tangencial

      PVector tang_vel1 = PVector.sub(vel, normal_vel1);

      PVector tang_vel2 = PVector.sub(b.vel, normal_vel2);

      // Restitución

      float L = r + b.r - dist.mag(); //

      float vrel = PVector.sub(normal_vel1, normal_vel2).mag();

      loc.add(PVector.mult(normal_vel1, -L/vrel));

      b.loc.add(PVector.mult(normal_vel2, -L/vrel));

      // Velocidades de salida

      float m1 = m;

      float m2 = b.m;

      //Escalar u

      float u1, u2;

      //u1

      if (normal_vel1.mag() == 0 || dist.mag() == 0)

        u1 = 0;

      else

        u1 = normal_vel1.dot(dist)/dist.mag(); //Normaliza

      //u2

      if (normal_vel2.mag() == 0 || dist.mag() == 0)

        u2 = 0;

      else

        u2 = normal_vel2.dot(dist)/dist.mag(); //Normaliza

      //Módulo v

      float v1 = ((m1-m2*Kr)*u1+(m2+m2*Kr)*u2)/(m1+m2);

      float v2 = ((m2-m1*Kr)*u2+(m1+m1*Kr)*u1)/(m1+m2);

      //Vector normal1

      v_unit = dist.get();

      v_unit.normalize();

      v_unit.mult(v1);

      normal_vel1 = v_unit;

      //Vector normal2

      v_unit = dist.get();

      v_unit.normalize();

      v_unit.mult(v2);

      normal_vel2 = v_unit;

      //Vector vel

      vel = PVector.add(normal_vel1, tang_vel1);

      b.vel = PVector.add(normal_vel2, tang_vel2); 

    } 

  }

}

class Plano {

  PVector ini;

  PVector fin;

  PVector plano; 

  PVector normal;

  float Kr = 0.9;

​

  PVector dist1, dist2, P1Project, VecP2Project, dist_col, uni;

  float escalar_p1Norm, escalar_p1Plano, escalar_p2Plano, modulo_plano, p1, p2;

​

  float nv, delta_s, ang;

  PVector norm_plano, Norm, tang, restitucion; 

​

  Plano(float iniX, float iniY, float finX, float finY)

  {

    ini = new PVector(iniX, iniY);

    fin = new PVector(finX, finY);

    plano = PVector.sub(fin, ini);

    normal =  new PVector(-plano.y, plano.x);

    normal.normalize();

  }

  // Colisiones con el plano (pto1, pto2)

​

  void checkCollisions(Particula b)

  {

    //dif = loc - pto   //  

    dist1 = PVector.sub(ini, b.loc);

    dist2 = PVector.sub(fin, b.loc);

​

    uni = new PVector(0, 0); //Vector untario

    modulo_plano = plano.mag(); //hipotenusa

​

    escalar_p1Plano = dist1.dot(plano); //Producto escalar

    p1 = escalar_p1Plano/modulo_plano; //Normalizacion

​

    escalar_p2Plano = dist2.dot(plano);

    p2 = escalar_p2Plano/modulo_plano;

​

    uni.set(plano);

    uni.normalize();

    //plano.normalize(uni);

​

    dist_col = PVector.add(dist1, PVector.mult(uni, p1*(-1)));

​

​

    if (abs(p1) < modulo_plano && abs(p2) < modulo_plano)

    {

      if (dist_col.mag() < radio) {

​

        norm_plano = normal.get(); 

        if (norm_plano.dot(b.vel)>0) //Producto escalar de la velocidad

          norm_plano.mult(-1);

​

        ang = PVector.angleBetween(b.vel, plano); //Calcula el angulo entre 

​

        delta_s = ( radio+dist_col.dot(norm_plano) ) / sin(ang);

​

        restitucion = PVector.mult(norm_plano, delta_s);

        b.loc.add(restitucion);

​

​

        nv = normal.dot(b.vel); //Producto vectorial de la normal y la velocidad

        Norm = PVector.mult(normal, nv); //Luego se multiplica

        tang = PVector.sub(b.vel, Norm);

        b.vel = PVector.sub(tang, PVector.mult(Norm, Kr));

      }

    }

  }

}

class Tabla_Hash {

  ArrayList<ArrayList<Particula>> tabla;

  int cell_size;

  int t_size;

  Tabla_Hash(int tam_celda, int tam_tabla){

    cell_size = tam_celda;

    t_size = tam_tabla;

    tabla = new ArrayList<ArrayList<Particula>>(); 

    for(int i = 0; i < t_size; i++){

      tabla.add(new ArrayList<Particula>());

    } 

  }

  int hash(PVector p){

    int xd = (int)floor(p.x/cell_size);

    int yd = (int)floor(p.y/cell_size);

    int zd = (int)floor(p.z/cell_size);

    int h = (73856093 * xd + 19349663 * yd + 83492791 * zd) % t_size;

    if (h < 0)

      h += t_size;

    return h;

  }

  int insertar(PVector v, Particula p){

    int num = hash(v);

    tabla.get(num).add(p);

    return num;

  }

  ArrayList comprobar(PVector v){

    int num = hash(v); 

    return tabla.get(num);

  }

}

​

​

​