检查矩形列表和单个矩形之间的交集的最快方法

本文关键字：方法 之间 列表 单个矩 检查 | 更新日期: 2023-09-27 18:22:50

我想检查矩形（播放器）是否与列表（列表）中的一个矩形相交。

我目前使用的是for循环，这使它速度慢，性能差。

for (int i = 0; i < gameObjects.objectList.Count; i++)
{
   if (gameObjects.objectList[i].IntersectsWith(gameObjects.player))
   {
        gameObjects.objectList.RemoveAt(i); // if the player collided with an object, remove that object
    }
}

我怎样才能使它更有效率/有其他方法可以更快地完成吗？

检查矩形列表和单个矩形之间的交集的最快方法

您可以尝试在名为k-d-tree的结构中组织矩形。

在一个大型矩形阵列（>100）中，它的复杂度高达O（logN）。

例如，制作固定长度的二叉树，比如2。将你的空间分为左右两半，然后每一半分为上下四分之一（依此类推）。

在叶节点内部创建一个矩形列表。如果矩形分为左半部分和上四分之一部分，请在该四分之一的列表中找到它。

一个矩形可以同时位于几个列表中（例如，如果它分为左右两半）。

若要检查交集，您应该在响应的两半和四分之一中测试矩形。

或者，如果删除了太多的矩形，那么将剩余的矩形复制到自己代码中的新列表中会更快。

小例子。

public enum CheckBy
{
    Horizontal,
    Vertical
}
public class Node
{
    public Node First { get; set; }
    public Node Second { get; set; }
    public int Coordinate { get; set; }
    public CheckBy CheckBy { get; set; }
    public List<Rectangle> Rectangles { get; set; }
}
public bool IsRectangleInFist(Node node, Rectangle rectangle)
{
    if (node.CheckBy == CheckBy.Horizontal)
        return rectangle.Left <= node.Coordinate;
    return rectangle.Top <= node.Coordinate;
}
public bool IsRectangelInSecond(Node node, Rectangle rectangle)
{
    if (node.CheckBy == CheckBy.Horizontal)
        return rectangle.Right >= node.Coordinate;
    return rectangle.Bottom >= node.Coordinate;
}
public void AddRectangleInSuitableNode(Node node, Rectangle rectangle)
{
    if (InRectangleInFirst(node, rectangle))
        AddRectangleInSuitableNode(node.First, rectangle);
    if (InRectangleInSecond(node, rectangle))
        AddRectangleInSuitableNode(node.Second, rectangle);
}
public void SearchIntersectedRectangles(Node node, Rectangle rectangle, List<Rectangles> result)
{
    // If not-leaf node
    if (node.Rectangles == null && node.First != null && node.Second != null)
    {
        if (IsRectangleInFirst(node, rectangle))
            SearchIntersecatedRectangles(node.First, rectangle, result);
        if (IsRectangleInSecond(node, rectangle))
            SearchIntersecatedRectangles(node.Second, rectangle, result);
        return;
    }
    result.AddRangle(Rectangles.Where(r => r.IsIntersect(rectangle)));
}

这些线条构成了简单的2D树。首先，制作树：

// Say, all rectangles would be inside this "space"
const int leftest = -1000;
const int rightest = 1000;
const int bottomest = -1000;
const int toppest = 1000;
// Tree with depth == 2
var tree = new Node
{
    CheckBy = CheckBy.Hozirontal,
    Coordinate = (leftest + rightest)/2,
    First = new Node
    {
        CheckBy = CheckBy.Vertical,
        Coordintate = (toppest + bottomest)/2,
        Rectangles = new List<Rectangle>(),
    },
    Second = new Node
    {
        CheckBy = CheckBy.Vertical,
        Coordintate = (toppest + bottomest)/2,
        Rectangles = new List<Rectangle>(),
    },
}

然后，对该树中的所有矩形进行排序：

foreach (var rectangle in rectangles)
    AddRectangleInSuitableNode(tree, rectangle);

现在你可以快速得到相交的矩形：

var intersecting = new List<Rectangles>();
SearchIntersecatedRectangles(tree, targetRectangle, intersecting);
// Here you can remove intersecting rectangles...

基本上，每次都需要停止检查所有矩形。你需要弄清楚哪些矩形位于玩家附近。

你可以使用某种空间网格来存储你的矩形，这样你就可以快速找到要检查碰撞的相邻矩形。请参见本教程，例如：N教程B-宽相位碰撞。

我怀疑它会更快，但你总是可以在一行中使用Ling：

gameObjects.objectList = gameObjects.objectList
                         .Select(go => go)
                         .Where(go => !go.IntersectsWith(gameObjects.player))
                         .ToList();

这基本上将列表设置为移除与player冲突的任何gameObject的列表。

还要注意，首先处理排序列表通常会更快，所以这样做：

gameObjects.objectList = gameObjects.objectList
                         .OrderBy(go => go.X)
                         .ThenBy(go => go.Y)
                         .ToList();

可能有助于加快速度。不过，对每一帧进行排序会很慢，因此在将对象添加到列表中时对其进行排序是值得的。

相关文章：