2

Preciso repartir o espaço em células. Cada célula deve ter aproximadamente o tamanho do raio das partículas para que uma partícula não ocupe mais que 4 células como na ilustração abaixo:

A partícula de raio r pode ocupar até 4 células. A sua própria célula (onde o centro (x,y) da partícula está localizado) e mais outras 3 células vizinhas.

Motivo da otimização: Com o atual código, quando aumento a quantidade de partículas, o programa fica muito lento e as colisões entre elas não ocorrem de forma fluída.

canvas.cpp

#include "canvas.h"
#include <QPainter>

canvas::canvas(QWidget *parent) :
QWidget(parent)
{
m_particulas.resize(50);

int n = m_particulas.size();
for(int i = 0 ; i<n ; ++i)
{
    m_particulas[i].init();
}

startTimer(5);
}

void canvas::paintEvent(QPaintEvent * event)
{
(void) event;

QPainter painter(this);
painter.setWindow(0,0,1000,1000);
painter.setRenderHint(QPainter::Antialiasing, true);
painter.setPen(QPen(Qt::black, 2, Qt::SolidLine, Qt::RoundCap));
painter.setBrush(QBrush(Qt::darkCyan, Qt::SolidPattern));

int n = m_particulas.size();
for(int i = 0 ; i<n ; ++i)
{
    double x = m_particulas[i].x();
    double y = m_particulas[i].y();
    double L = m_particulas[i].r();
    painter.drawEllipse(QPointF(x, y), L, L);
}
}

void canvas::timerEvent(QTimerEvent *event)
{
(void) event;

int n = m_particulas.size();

for(int i = 0 ; i<n ; ++i)
    m_particulas[i].andar();

for(int i = 0 ; i<n ; ++i)
{
    Particula &pi = m_particulas[i];

    for(int j = 0 ; j < n ; ++j)
    {
        if (i == j) continue; //(MODO 2)

        Particula &pj = m_particulas[j];

        if (pi.testa_colisao(pj))
        {
            pi.calcula_colisao(pj);
        }
    }
}
update();
}

particula.cpp

#include "particula.h"
#include <stdlib.h>     /* srand, rand */
#include <cmath>

Particula::Particula()
{

}

void Particula::init()
{
m_r = 20;

m_x = 900.0*rand()/RAND_MAX + 50;
m_y = 900.0*rand()/RAND_MAX + 50;

m_vx = 2.0 * rand()/RAND_MAX - 1;
m_vy = 2.0 * rand()/RAND_MAX - 1;

double norma = sqrt(m_vx*m_vx + m_vy*m_vy);
m_vx /= norma;
m_vy /= norma;
}

void Particula::normaliza(double &vx, double &vy)
{
double norma = sqrt(vx*vx + vy*vy);

if (norma > 0)
{
    vx /= norma;
    vy /= norma;
}
}

bool Particula::testa_colisao (Particula &p)
{
    double dx = x() - p.x();
    double dy = y() - p.y();

    double dist2 = dx*dx + dy*dy;
    double somaRaios = r() + p.r();
    return dist2 <= somaRaios * somaRaios;
}

void Particula::calcula_colisao(Particula &p)
{
    double vx = p.x() - x();
    double vy = p.y() - y();
    normaliza(vx,vy);

    p.m_vx += vx;
    p.m_vy += vy;
    normaliza(p.m_vx,p.m_vy);

    m_vx -= vx;
    m_vy -= vy;
    normaliza(m_vx, m_vy);

   do
    {
        andar();
        p.andar();
    } while (testa_colisao(p));
}

double Particula::x() const
{
return m_x;
}

double Particula::y() const
{
return m_y;
}

double Particula::r() const
{
return m_r;
}

void Particula::andar()
{
m_x += m_vx;
m_y += m_vy;

if(m_x > 1000-m_r) m_vx *= -1; //inferior - multiplicado por -1 para inverter a     direção...
if(m_y > 1000-m_r) m_vy *= -1; //direita
if(m_x < 0+m_r) m_vx *= -1; //esquerda
if(m_y < 0+m_r) m_vy *= -1; //superior
}
5
  • Eu não sei se entendi direito a pergunta: você não sabe como verificar a colisão usando esse conceito de partições, é isso? Ah, talvez você não precise repartir o espaço nesse nível. Já tentou repartí-lo em 4 ou 16 grandes áreas quadradas? Commented 20/06/2014 às 1:35
  • Não consegui ver como funciona seu código, está um pouco complexo. Eu faria usando conceitos de geometria analítica com equação da circunferência, já que você tem o raio, o X do centro e o Y do centro. Então veria retas que são secantes à circunferência, ignorando as retas tangentes e as que estão fora. Talvez usando distância entre ponto e reta e comparando o raio com algumas coisas da equação da circunferência, fique um código bastante pequeno, legível e rápido.
    – Metalus
    Commented 20/06/2014 às 2:34
  • Quero fazer de uma forma que não seja mais necessário calcular a distância de uma partícula para todas as outras partículas, mas somente para aquelas que estiverem próximas. Evitando assim a lentidão nas colisões. Segue imagem como exemplo: goo.gl/D1B5lV Commented 20/06/2014 às 2:47
  • 1
    Qual a ordem de magnitude que estamos falando? Quantas partículas pretende usar e qual o tamanho da sua malha? Commented 20/06/2014 às 2:49
  • Algo em torno de 5 mil partículas com o raio entre 5 e 10. Commented 20/06/2014 às 4:09

1 Resposta 1

2

Para efeito de ilustração, considere uma divisão simples em que o seu Canvas é partido em 4x4 quadrados menores, como na figura abaixo:

inserir a descrição da imagem aqui

O seu código testa a colisão dentro do método canvas::timerEvent, hoje verificando-a entre cada possível combinação das n particulas: p1 x p2. Por isso, ele tem uma complexidade quadrática (O(n2)) e pode demorar bastante pra um grande número de partículas.

Usando uma divisão simples como a ilustrada, você pode fazer um único laço para localizar as partículas nos diferentes quadrados e assim "filtrar" apenas aquelas no mesmo quadrado (ou nos quadrados vizinhos, como preferir) de uma partícula de interesse.

A filtragem é simples de ser realizada usando um único laço para percorrer todas as partículas existentes (a complexidade é O(n), e você pode utilizar o mesmo laço que já usa para fazer as partículas andarem):

  • Divida as dimensões do canvas em comprimento (width) e altura (height) respectivamente pelo número de quadrados em uma linha e em uma coluna (no exemplo ilustrado, esse número é 4 para ambox). Isso resultará nas dimensões em pixels de um quadrado (isto é, comprimento e altura de um quadrado em pixels).
  • No laço de localização, para a partícula atual pi, divida os valores de suas coordenadas em x e em y respectivamente pelas dimensões comprimento e largura de um quadrado anteriormente calculadas, e tome apenas a parte inteira (trunque o resultado). Isso resultará no índice (iniciado em 0) do quadrado em que a partícula está localizada nos eixos X e Y, que pode ser usado para armazenar e referenciar as partículas em um array bidimensional que represente os quadrados.

Exemplo:

Considere que o canvas tenha 100 x 100 pixels e que uma partícula A se encontra na coordenada (x:80, y:25) e outra partícula B se encontra na coordenada (x:48, y:77).

Como são 4 quadrados em uma linha do canvas, o comprimento de um quadrado é 100/4=25 pixels. Como são 4 quadrados em uma coluna do canvas, a altura de um quadrado é 100/4=25 pixels. Assim, um quadrado tem 25 x 25 pixels; no eixo X do canvas, o primeiro quadrado vai do pixel 0 ao pixel 24, o segundo do pixel 25 ao pixel 49, o terceiro do pixel 50 ao pixel 74, e o último do pixel 75 ao pixel 99; como a altura é igual ao comprimento, os mesmos valores valem para as coordenadas dos quadrados no eixo Y do canvas.

Para a partícula A. Ao dividir seu valor de x = 80 pelo comprimento do quadrado resulta em: 80/25 = 3,2. Extraindo-se a parte inteira, tem-se o valor 3. Esse valor indica o índice do quadrado em que a particula se encontra no eixo X, isto é, no quarto e último quadrado da esquerda para a direita (lembrando que a indexação é a partir de 0). Ao dividir seu valor de y = 25 pela altura do quadrado resulta em: 25/25 = 1. Extraindo-se a parte inteira, tem-se o valor 1 o que indica que a partícula está no segundo quadrado de cima para baixo. Ou seja, usando um array bidimensional para representar os quadrados, a particula está no quadrado CANVAS[3,1].

Para a partícula B. Ao dividir seu valor de x = 48 pelo comprimento do quadrado tem-se: 48/25 = 1,92 com parte inteira igual a 1. Ao dividir seu valor de y = 77 pela altura do quadrado tem-se: 77/25 = 3,08 com parte inteira igual a 3. Ou seja, a particula está no quadrado CANVAS[1,3].

Uma vez que você tenha as particulas localizadas em seus diferentes quadrados, a verificação da colizão pode ser feita apenas para as partículas dentro de cada quadrado. Você pode fazer isso simplesmente percorrendo os quadrados em um array bidimensional e fazendo o teste de colisão apenas para as partículas armazenadas dentro do quadrado atual (ou seja, dentro de CANVAS[i,j]).

Ainda que dentro de cada quadrado a comparação tenha complexidade quadrática, no resultado geral o custo computacional vai ser bem menor, proporcional à sua divisão (imagine que você tenha 100 partículas; para comparar todas entre si são necessárias 100x100 = 10000 comparações; com apenas 4 células, se tiverem 25 partículas em cada célula serão necessárias apenas quatro comparações locais de 25x25 partículas, ou seja, 4x25x25 = 2500 comparações - apenas 25% do que seria necessário sem a divisão).

Você pode não precisar de uma divisão muito grande. Talvez usar 16 células (divisão 4x4 como a ilustrada) seja suficiente para o seu propósito. Além disso, talvez você não precise recalcular a localização das partículas no mesmo intervalo de tempo em que as move, mas isso vai depender da velocidade delas e do ajuste fino que você possa vir a precisar. Aconselho a começar com as soluções mais simples (menos quadrados, relocalização a cada movimento), e aplicar as mudanças conforme sentir necessidade.

P.S.: Note também que na minha sugestão eu não estou considerando as dimensões das partículas (que foi uma preocupação sua na pergunta, mas que eu julguei desnecessária). Se tiver algum motivo pra isso (talvez vindo da referência de onde você mesmo tirou uma imagem postada nos comentários), acho importante você especificar na pergunta. :)

1
  • 1
    A dimensão das partículas é apenas para um visão nítida das colisões entre elas. Isso se trata de um trabalho para a faculdade, onde o professor pede para ir aumentando a quantidade de partículas e diminuindo o seu raio proporcionalmente, para critério de avaliação da eficiência do código. Foi de grande ajuda, tentarei fazer o que sugeriu. Obrigado. Commented 20/06/2014 às 15:37

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .