四叉樹在碰撞檢測中的應用

2021-02-10 ACM算法日常
緣起

《你被追尾了》中預告了加速碰撞檢測的算法——四叉樹（for 2D），所以本文就來學習一下.

分析

首先是為什麼要使用四叉樹進行優化，其實《你被追尾了》中已經說了，這裡簡單複習一下，碰撞檢測是一種比較昂貴的操作. 假設有100個對象需要進行碰撞檢測，那麼兩兩進行碰撞檢測需要進行 100 x 100 = 10000 次碰撞檢測，檢測的次數實在太多，消耗大量CPU資源而引起遊戲卡幀。一種優化途徑是減少非必要的碰撞檢測的次數。比如兩個物體位於屏幕的左上角和右下角，顯然是不可能發生碰撞的，因此不需要檢測它們之間是否會發生碰撞。這正是四叉樹發揮作用的地方。

什麼是四叉樹（Quadtree）

四叉樹是一種將一塊2D矩形區域（理解為遊戲沙盒）分割為更易於管理的子區域的數據結構.

四叉樹是二叉樹的擴展——將2個子節點變為4個子節點.  四叉樹的根節點是初始的尚未被劃分的一整塊2D區域.

在下面所有的圖中， 紅色的小方塊代表物體（例如賽車）.

然後，我們將一個物體放入初始的2D區域（即四叉樹的根節點）

當越來越多的物體被放入該區域（記做 R，region）的時候，就會導致該區域（節點）的分裂（split）.  具體多到什麼程度開始分裂，你可以在程序中進行自定義. 例如我設定為1，則表示只要有物體放入，我就對R 進行分裂. 顯然，這個數字的大小代表四叉樹算法的惰性.

該節點將最終分裂為4（因為是四叉樹嘛~）個子節點（子節點記做SR，sub region）. 然後每個物體都將根據它們所處的坐標被劃分進某個SR. 如果一個物體不能完全放入任何一個SR的話，將被歸入 R

例如上圖中，物體 A 將歸入 R， 而除了 A 之外的所有物體都被歸入了相應的 SR

然後，隨著越來越多的物體加入，SR 可能也會分裂. 就像下圖這樣, 左上角的 SR 繼續分裂為了4個子節點.

正如你所見，A、B、C、D 四個物體處在不同的象限，所以絕逼不可能發生碰撞. 這就不需要對這四個物體之間進行昂貴的碰撞檢測，從而優化了遊戲的性能.

知道了四叉樹的思想之後，我們不難給出如下實現.  首先，我先說一下我想做出什麼效果? 就是如下圖所示

就是能實時（其實是每一幀）展示出 四叉樹的樣子，以及填充發生碰撞的小球對（ball pair）. 框中的小球和邊界都是彈性碰撞，小球碰撞時彼此互相穿過.

網上有使用 js 實現的版本，我這裡使用 Win 32 API 實現 UI 界面.

以下代碼在 vs2010  下調試通過

Object.h

#include "Rectangle.h"
#include <graphics.h>

#define OBJECT_WIDTH 20 
#define OBJECT_HEIGHT 20 

class Object : public Bound 
{
    double vx, vy; 
    int color; 
    int id;
public:
    Object(double x = 0, double y = 0)
    {
        this->x = x;
        this->y = y;
        this->w = rand() % OBJECT_WIDTH + 1;
        this->h = this->w;
        this->vx = (rand() % 10 + 1) * (rand() & 1 ? 1 : -1); 
        this->vy = (rand() % 10 + 1) * (rand() & 1 ? 1 : -1);
        color = YELLOW; 
    }

    ~Object() {}

    friend bool collisionWithBound(Object object);

    friend void reflect(Object &object); 

    void setId(int id) 
    {
        this->id = id;
    }

    void setColor(int color) 
    {
        this->color = color;
    }

    void paint()
    {
        setfillcolor(color);
        solidrectangle(x, y, x + w, y + h);
    }

    bool collision(Object &o) 
    {
        bool ans = x < o.x + o.w && o.x < x + w && y < o.y + o.h && o.y < y + h;
        if (ans) 
        {
            o.color = color = RED;
        }
        return ans;
    }

    void move()
    {
        x += vx;
        y += vy;
    }

    bool operator == (const Object &o)
    {
        return id == o.id;
    }

};
QuadTree.h
#include <list>
using namespace std;
#include "Object.h"
typedef list<Object>::iterator LIT;

class QuadTreeNode
{
public:
    void clear();
    void insert(Object); 
    list<Object> retrieve(Object &); 
    void setLevel(int level) { this->level = level; }
    void setBound(Bound bound) { this->bound = bound; }
    QuadTreeNode();
    QuadTreeNode(int, Bound);
    ~QuadTreeNode();
private:
    int level; 
    list<Object> objects; 
    Bound bound; 
    QuadTreeNode *nodes[4];

    const static int MAX_OBJECTS = 5; 
    const static int MAX_LEVELS = 5; 

    void split(); 
    int getIndex(Object &); 
};

struct Line 
{
    double sx, sy, ex, ey; 
    Line(double sx = 0, double sy = 0, double ex = 0, double ey = 0):sx(sx), sy(sy), ex(ex), ey(ey){}
    void paint(); 
};
Rectangle.h
class Bound
{
protected:
    double x, y, w, h; 
public:
    Bound(double x = 0, double y = 0, double w = 0, double h = 0):x(x), y(y), w(w), h(h){}
    
    double getx()
    {
        return x;
    }

    double gety()
    {
        return y;
    }

    double getw()
    {
        return w;
    }

    double geth()
    {
        return h;
    }

};
QuadTree.cpp
#include "QuadTree.h"
#include <string.h>

Line lines[10005];
int top; 

QuadTreeNode::QuadTreeNode()
{
    memset(nodes, 0, sizeof(nodes));
}

QuadTreeNode::QuadTreeNode(int level, Bound bound)
{
    this->level = level;
    this->bound = bound;
    memset(nodes, 0, sizeof(nodes));
}

QuadTreeNode::~QuadTreeNode()
{
    clear();
}

void QuadTreeNode::clear()
{
    objects.clear();
    if (nodes[0])
    {
        for (int i = 0; i < 4; i++)
        {
            nodes[i]->clear();
            nodes[i] = 0;
        }
    }
}

void QuadTreeNode::split()
{
    double w = bound.getw() / 2.0;
    double h = bound.geth() / 2.0;
    double x = bound.getx();
    double y = bound.gety();
    nodes[0] = new QuadTreeNode(level + 1, Bound(x + w, y, w, h)); 
    nodes[1] = new QuadTreeNode(level + 1, Bound(x, y, w, h)); 
    nodes[2] = new QuadTreeNode(level + 1, Bound(x, y + h, w, h)); 
    nodes[3] = new QuadTreeNode(level + 1, Bound(x + w, y + h, w, h)); 
    lines[top].sx = bound.getx() + bound.getw() / 2.0; lines[top].sy = bound.gety(); lines[top].ex = bound.getx() + bound.getw() / 2.0; lines[top].ey = bound.gety() + bound.geth();
    lines[top + 1].sx = bound.getx(); lines[top + 1].sy = bound.gety() + bound.geth() / 2.0; lines[top + 1].ex = bound.getx() + bound.getw(); lines[top + 1].ey = bound.gety() + bound.geth() / 2.0;
    lines[top + 2].sx = bound.getx(); lines[top + 2].sy = bound.gety(); lines[top + 2].ex = bound.getx() + bound.getw(); lines[top + 2].ey = bound.gety();
    lines[top + 3].sx = bound.getx(); lines[top + 3].sy = bound.gety() + bound.geth(); lines[top + 3].ex = bound.getx() + bound.getw(); lines[top + 3].ey = bound.gety() + bound.geth();
    lines[top + 4].sx = bound.getx(); lines[top + 4].sy = bound.gety(); lines[top + 4].ex = bound.getx(); lines[top + 4].ey = bound.gety() + bound.geth();
    lines[top + 5].sx = bound.getx() + bound.getw(); lines[top + 5].sy = bound.gety(); lines[top + 5].ex = bound.getx() + bound.getw(); lines[top + 5].ey = bound.gety() + bound.geth();
    top += 6;
}

int QuadTreeNode::getIndex(Object &object)
{
    int ans = -1; 
    double hmid = bound.getx() + bound.getw() / 2.0, vmid = bound.gety() + bound.geth() / 2.0; 
    if (object.getx() + object.getw() < hmid) 
    {
        if (object.gety() + object.geth() / 2.0 < vmid)
        {
            return 1;
        }
        else if (object.gety() > vmid)
        {
            return 2;
        }
    }
    else if (object.getx() > hmid) 
    {
        if (object.gety() + object.geth() / 2.0 < vmid)
        {
            return 0;
        }
        else if (object.gety() > vmid)
        {
            return 3;
        }
    }
    return ans; 
}

void QuadTreeNode::insert(Object object)
{
    if (nodes[0])
    {
        int index = getIndex(object);
        if (~index) 
        {
            nodes[index]->insert(object);
            return;
        }
    }
    objects.push_back(object); 
    if (objects.size() > QuadTreeNode::MAX_OBJECTS && level < QuadTreeNode::MAX_LEVELS) 
    {
        if (!nodes[0]) 
        {
            split();
        }
        for (LIT lit = objects.begin(); lit != objects.end();)
        {
            int index = getIndex(*lit);
            if (~index)
            {
                nodes[index]->insert(*lit);
                lit = objects.erase(lit);
            }
            else
            {
                ++lit;
            }
        }
    }
}

list<Object> QuadTreeNode::retrieve(Object &object)
{
    list<Object> ans;
    int index;
    if (nodes[0] && ~(index = getIndex(object)))
    {
        ans = nodes[index]->retrieve(object);
    }
    for (LIT lit = objects.begin(); lit != objects.end(); lit++)
    {
        ans.push_back(*lit);
    }
    return ans;
}
四叉樹Demo.cpp
#include <stdio.h>
#include <graphics.h>
#include <time.h>
#include <MMSystem.h>
#pragma comment(lib, "winmm.lib")
#include "QuadTree.h"

#define WIDTH 600 
#define HEIGHT 800 
#define OBJECT_NUM 20 
Object objects[OBJECT_NUM];
QuadTreeNode quad;
extern int top;
extern Line lines[];

HWND hWnd;

void initGame(); 

void _move();

void drawGame();

int main()
{
    // 秋華の戀
    mciSendString("open 1.mp3 alias start", NULL, NULL, NULL); 
    mciSendString("play start repeat", NULL, NULL, NULL);
    initGame();
    SetTimer(hWnd, 666, 50, (TIMERPROC)_move);
    while (1)
    {
        drawGame();
    }
    return 0;
}

void initGame()
{
    srand(time(0));
    hWnd = initgraph(WIDTH, HEIGHT);
    setbkcolor(RGB(0, 255, 255));
    cleardevice();
    for (int i = 0; i < OBJECT_NUM; i++)
    {
        objects[i] = Object(rand() % (WIDTH - OBJECT_WIDTH), rand() % (HEIGHT - OBJECT_HEIGHT));
        objects[i].setId(i);
    }
    quad.setLevel(0);
    quad.setBound(Bound(0, 0, WIDTH, HEIGHT));
}

bool collisionWithBound(Object object)
{
    return object.x <= 0 || object.x + object.w >= WIDTH || object.y <= 0 || object.y + object.h >= HEIGHT;
}

void reflect(Object &object)
{
    if (object.x < 0)
    {
        object.x = 0;
        object.vx = -object.vx;
    }
    else if (object.x + object.w > WIDTH)
    {
        object.x = WIDTH - object.w;
        object.vx = -object.vx;
    }
    if (object.y < 0)
    {
        object.y = 0;
        object.vy = -object.vy;
    }
    else if (object.y + object.h > HEIGHT)
    {
        object.y = HEIGHT - object.h;
        object.vy = -object.vy;
    }
}

void _move()
{
    for (int i = 0; i < OBJECT_NUM; i++)
    {
        objects[i].move();
        if (collisionWithBound(objects[i])) 
        {
            reflect(objects[i]); 
        }
    }
}

void Line::paint()
{
    setlinecolor(BLUE);
    setlinestyle(PS_DASH);
    line((int) sx, (int) sy, (int) ex, (int) ey);
}

void drawGame()
{
    BeginBatchDraw();
    cleardevice();
    quad.clear();
    top = 0;
    for (int i = 0; i < OBJECT_NUM; i++) 
    {
        quad.insert(objects[i]);
    }
    for (int i = 0; i < OBJECT_NUM; i++)
    {
        objects[i].setColor(YELLOW); 
        list<Object> candidate = quad.retrieve(objects[i]); 
        for (LIT lit = candidate.begin(); lit != candidate.end(); lit++)
        {
            if (objects[i] == *lit) 
            {
                continue;
            }
            objects[i].collision(*lit); 
        }
    }
    for (int i = 0; i < OBJECT_NUM; i++) 
    {
        objects[i].paint();
    }
    for (int i = 0; i < top; i++) 
    {
        lines[i].paint();
    }
    EndBatchDraw();
}
運行效果
綺麗ですね~！！！

相關焦點

  • 結構與算法:二叉樹與多叉樹
    經典數據結構中的各種樹狀圖是一種典型的樹形結構：一顆樹可以簡單的表示為根，左子樹，右子樹。 左子樹和右子樹又有自己的子樹。= 2^n -1 , n 為層數，則稱為滿二叉樹。平衡二叉樹平衡二叉樹指的是，任意節點的子樹的高度差的絕對值都小於等於1，並且左右兩個子樹都是一棵平衡二叉樹，常見的符合平衡樹的有，B樹（多路平衡搜索樹）、AVL樹（二叉平衡搜索樹）等。
  • Nature:防止複製叉的碰撞
    沿一個DNA鏈向相反方向運動的兩個複製叉之間的碰撞，預計會經常發生在具有多個複製起源的真核細胞中。Christian Rudolph等人利用一個細菌系統來觀察這種碰撞對細胞的影響。他們發現，碰撞點可被用來獨立於一個活性來源重新啟動複製，這可能具有潛在的致病效應。RecG轉位酶和幾種核酸外切酶能防止這種事件的發生，從而維持基因組的穩定性。
  • 工業機器人技術解密之動力學應用:碰撞檢測
    隨著機器人應用範圍增大，人們對機器人的要求也越來越高，尤其在機器人安全性能方面。最初研製的機器人只能完成一些簡單的重複任務，不具備人機互動能力；隨著技術的高速發展，機器人趨於智能化，能夠完成更加複雜的任務，例如噴塗、裝配、鑽孔等。
  • 木疙瘩中碰撞檢測大致原理及邏輯表達式
    邏輯表達式是木疙瘩使用過程中的一個難點，在某些場景下，邏輯表達式能很好地幫我們完成條件的判斷，比如驗證輸入框不為空，檢測文本的值為預期的值，取得某個文本的值填到另一個文本中等。做小遊戲時，邏輯表達式更是必備的，合理利用邏輯表達式可以讓我們在物體不同狀態下執行不同的行為，今天要講的碰撞檢測就是特別常用的一個邏輯表達式。學會它，可以很輕鬆地完成小車碰撞，接水果，垃圾分類等等小遊戲。碰撞檢測就是檢測兩個物體邊緣是不是有重疊，此例以兩個矩形為例。
  • 四叉樹上如何求希爾伯特曲線的鄰居 ?
    如上圖，綠色的區域是一顆四叉樹表示的範圍，四叉樹上面有一個點，圖中黃色區域標明的點。現在想求四叉樹上黃色的點的希爾伯特曲線鄰居。圖中黑色的線就是一顆穿過四叉樹的希爾伯特曲線。希爾伯特曲線的起點0在左上角的方格中，終點63在右上角的方格中。紅色的四個格子是黃色格子邊相鄰鄰居，藍色的四個格子是黃色格子的頂點相鄰的鄰居，所以黃色格子的鄰居為8個格子，分別表示的點是8，9，54，11，53，30，31，32 。可以看出來這些鄰居在表示的點上面並不是相鄰的。那麼怎麼求四叉樹上任意一點的希爾伯特曲線鄰居呢？
  • 工業機器人技術解密之碰撞檢測
    隨著機器人應用範圍增大，人們對機器人的要求也越來越高，尤其在機器人安全性能方面。最初研製的機器人只能完成一些簡單的重複任務，不具備人機互動能力；隨著技術的高速發展，機器人趨於智能化，能夠完成更加複雜的任務，例如噴塗、裝配、鑽孔等。
  • 在word中實現方框打鉤打叉的幾種方法
    今天就來教大家幾種方法來實現在word裡打勾跟打叉，具體的過程請看下面。一：輸入法實現如果我們需要用的僅僅只是打勾跟打叉的話，這個很簡單，打勾可以靠輸入法來解決，至於打叉，我們可以用字母X來代替。二：少為人知的快捷鍵Word中的方框打勾跟打叉其實是有快捷鍵可以快速實現的，但是這種快捷鍵一般很少有人知道，這裡有兩種快捷鍵。第一種是我們只需要按住鍵盤上的ALT鍵不放，然後在小鍵盤區輸入「9745」這幾個數字，最後鬆開 ALT 鍵，自動變成框框中帶勾符號。同理，按住ALT鍵，輸入「9746」，就會變成方框打叉。
  • 美研究員利用蝗蟲迴避能力研發碰撞檢測器 可預防汽車碰撞
    【汽車材料網】蝗災時會有數百萬種昆蟲，它們飛過天空攻擊農作物，但在這些龐大的昆蟲群中，單個昆蟲不會相互碰撞。如今，賓夕法尼亞州立大學的一個工程師團隊正在研發一種低功率碰撞檢測器，該檢測器通過模擬蝗蟲迴避反應，可以幫助機器人、無人機甚至自動駕駛汽車避免碰撞。
  • 倒立叉 PK 正立叉
    倒立叉相對正叉的好處主要有兩個，一個是對路面狀況反應靈敏，大家都知道質量越大的物體其慣性也越大，對外力作用的反應就越遲鈍，
  • 華為應用市場四重檢測機制,構建安全的終端應用生態環境
    隨著智能終端設備的不斷發展，手機在生活中扮演著越來越重要的角色，而手機上眾多種類的應用也豐富著我們的工作和娛樂生活。如何確保應用安全，保障用戶個人數據和隱私安全，對應用市場乃至整個終端生態都極為重要。四重監測機制保護消費者隱私和安全華為應用市場是華為終端官方的應用分發平臺，是全球首家實施"開發者實名認證"的應用市場，所有入駐的開發者需要經過嚴格的實名認證審核，以此過濾掉"來源不明"的第三方應用。
  • 紅外熱像儀在建築檢測——防治白蟻中的實地應用
    本文分享一家專注建築檢測的新加坡公司，其使用高德智感紅外熱像儀為新加坡國家藝術理事會（NationalArtsCouncil）防治白蟻的真實案例，通過實際應用詳細了解紅外技術在整治白蟻中的實際用途。因此，還可著重對辦公樓木質結構進行檢測，例如木門、木櫃等，查看是否遭受白蟻啃食。　　如圖五，檢測工程師對首次發現白蟻活動的室外樹木進行紅外檢測，因被蛀空處不再有水分供給，因此會比周圍有水分供給的樹體溫度高，在紅外熱像圖中可直觀查看到溫度差異。
  • 線性代數4——向量3(叉積)
    從上面的描述中可以看出，叉積得到的是一個向量，而不是一個數字，也因此，A×B和B×A並不等同，實際上，叉積的幾何意義　　向量的兩個要素是模長和方向，讓我們從這兩個角度考慮叉積的幾何意義。　　在模長上，叉積的幾何意義是以兩個向量為邊的平行四邊形的面積：
  • 基於平面投影的起重機吊裝碰撞檢測方法
    在各種工程建設中，起重機吊裝過程是否與障礙物碰撞決定著施工工程的安全性、可靠性、高效性。因此，研究一種判斷起重機吊裝作業規劃及仿真系統中實時碰撞檢測的可行且高效的計算方法，對吊裝行業的施工具有重要意義。
  • 中叉網:無託盤化搬運神器——滾輪貨叉
    目前的貨叉大都是與託盤配合使用的，貨物放在託盤上，貨叉從託盤的底部插入，再將貨物轉運到指定的位置，然後抽出貨叉，如此反覆運行，存在工作效率低、增加轉運成本的不足。如何實現無託盤化搬運貨物？這便需要叉車屬具來決定了，叉車配什麼樣的叉屬具主要根據不同性質和不同形狀的貨物決定，而通常使用普通貨叉最為常見。
  • 圖像檢測技術在靜態風電葉片檢測中的應用綜述
    摘要: 在簡述靜態風電葉片損傷的基礎上，本文主要針對圖像檢測技術在靜態風電葉片無損檢測中應用的研究方法及應用現狀進行綜述研究，重點闡述並橫向對比了目視法、紅外熱成像法、數字圖像相關技術、超聲檢測技術、機器視覺檢測技術及其他圖像檢測技術。
  • 叉尾太陽鳥,中國最小的鳥,性格很活潑
    叉尾太陽鳥（學名：Aethopyga christinae），別稱燕尾太陽鳥。常見分布於中國南方，範圍包括海南島，也及越南。它們的嘴細長下彎，舌呈管狀，專門用來吮吸花蜜，因此又被稱為「亞洲蜂鳥」 。在開花的矮樹木叢生活，且能懸飛在枝頭食蜜，它的性情活潑，行動敏捷。在1982年曾被認為是中國最小的鳥；2000年被列入中國《國家保護的有益的或者有重要經濟、科學研究價值的陸生野生動物名錄》。叉尾太陽鳥在東南亞屬常見鳥類，儘管由於棲息地逐漸破壞，可能呈現一定的減少趨勢，相對整體基數而言數量仍較穩定 。
  • 拜託,別再問我什麼是 B+ 樹了
    可以很明顯地觀察到查詢次數和樹高有關，那樹高和什麼有關，很明顯和每個節點的子節點個數有關，即 N 叉樹中的 N，假設現在有 16 個數，我們分別用二叉樹和五叉樹來構建，看下樹高分別是多少可以看到如果用二叉樹 ，要遍歷 5 個節點，如果用五叉樹 ，只要遍歷 3 次，一下少了兩次磁碟 IO，回過頭來看 上文的一億個節點，如果我們用 100 叉樹來構建，需要幾次 IO 呢
  • 達安中心正式形成70MPa氫燃料電池汽車碰撞檢測能力
    這是達安中心進行的首次氫燃料電池汽車碰撞試驗，也是國內首次採用外部數據採集器獨立檢測氫系統完整性。另外，通過此次碰撞試驗所驗證的檢測方法和能力，積累的檢測經驗可有效推動相關企標和國標的制修訂，而且有助於進口燃料電池汽車的檢測。
  • 金奎大中心正式形成70MPa氫燃料電池汽車的碰撞檢測能力
    近日，國家汽車質量監督檢驗中心(襄陽)和襄陽金奎大汽車檢測中心有限公司(以下簡稱「金奎大中心」)在汽車碰撞實驗室成功完成了70Mpa氫燃料電池汽車的碰撞試驗，標誌著金奎大中心正式建立了70MPa氫燃料電池汽車的碰撞檢測能力。這是金奎大中心進行的首次氫燃料電池汽車碰撞試驗，也是國內首次用外部數據採集器獨立測試氫系統的完整性。
  • . | 有趣的複製叉減速器cGAS
    責編 | 酶美cGAS-STING信號通路作為天然免疫系統的一個重要組成部分被發現，其功能是檢測胞漿DNA的存在，並在反應中觸發炎症基因的表達【1，2】。所以，胞漿中的cGAS就像一個防盜報警器。細胞核裡的cGAS雖然仍然和DNA結合，但是並不有效激活STING介導的免疫反應 【5，6】。cGAS為什麼存在在核內？在核內有什麼功能？為什麼STING在很多腫瘤中被抑制，cGAS不受影響？種種現象說明cGAS可能有STING通路之外的功能，但現在的研究成果還難以解釋這些現象。