四叉树写着玩-JZTXT

在看碰撞检测的时候看到了四叉树。闲着没事，写一个玩玩呗。

除了都含有一个矩形区域外，叶子节点能存几个粒子，而分支结点包含四个子节点，分别代表四个小矩形。结构还是很清晰的： struct QUAD{RECT boundary; BOOL isLeaf; union{POINT points[4]; LPQUAD children[4];}; } 。程序的任务就是：新建一个窗口，在客户区内画个边界，然后往这个矩形里插入新点，每个区域在适当的时候递归划分为4个小矩形，最终使每个矩形里最多只包含4个点。

插入新点P到矩形R内时这样做：

PROC AddNewPoint(P,R)：//将点P放到矩形R里
    if R.isLeaf==FALSE {
        if P位于左上：AddNewPoint(P,R.children[0]),结束
        if P位于右上：AddNewPoint(P,R.children[1]),结束
        if P位于左下：AddNewPoint(P,R.children[2]),结束
        if P位于右下：AddNewPoint(P,R.children[3])
        结束 }
    找[K]：R.points[K]=NOPOINT //NOPOINT是空标志
    if K∈[0..3] then R.points[K]←P, 结束
    TEMP ← R.points[0..3] // 暂存
    (左上，右上，左下，右下) ← 根据R划分出四个子矩形
    R.children[0..3] ← (左上，右上，左下，右下)
    R.isLeaf ← FALSE
    for E in TEMP:
        AddNewPoint(E,R) //安排这些点到子矩形中
    AddNewPoint(P,R) //加入新点
END

验证了一下，效果还行吧。

可恶！死去的计算机图形学知识又开始袭击我！

幸好本人数学不太行，我全部防出去了啊~~