如何检测坐标是否在指定区域内？现有实现存适配及性能疑问

嘿，我来帮你梳理这个问题——先从你遇到的bug根源说起，再聊聊性能优化和四叉树的实际应用，Java方案也会给到你~

你最初的inside函数有个隐藏假设：cornerOne的X/Z坐标一定小于等于cornerTwo。前3个区域刚好是按“左上→右下”的顺序选点，符合这个假设，所以检测正常；但第4个区域选点顺序反过来了（比如右下→左上），导致location.x >= cornerOne.x && location.x <= cornerTwo.x这个条件永远不成立，自然就失效了。

你后来修改的inBetween函数允许两种区间顺序的判断，完美修复了这个bug——不过我们还能进一步优化性能。

高频调用时，每次判断都做两次区间检查（(a in b..c) || (a in c..b)）会有额外开销。既然你已经有isValidRegion()方法，不如在Region初始化阶段就把X/Z的最小、最大值计算好并存储，避免每次判断都重复计算。

Kotlin优化版Region #

class Region(originBlock: Location, finalBlock: Location) {
    // 提前计算好标准化的区间边界
    val minX = min(originBlock.x, finalBlock.x)
    val maxX = max(originBlock.x, finalBlock.x)
    val minZ = min(originBlock.z, finalBlock.z)
    val maxZ = max(originBlock.z, finalBlock.z)

    fun isValidRegion(): Boolean {
        // 直接用标准化后的边界计算范围，逻辑更清晰
        return (maxX - minX + 1) >= 5 && (maxZ - minZ + 1) >= 5
    }
}

简化的判断函数 #

fun isInRegion(location: Location): Boolean {
    // 这里注意：你原来用了none，意思是"不在任何区域"；如果要判断"在任意一个区域"，换成any
    return regions.none { region ->
        location.x in region.minX..region.maxX && location.z in region.minZ..region.maxZ
    }
}

这样每次判断只需要两次简单的区间比对，性能比原来的inBetween更好，尤其适合高频调用场景。

如果你的区域数量非常多（比如上百个），遍历整个集合的开销会越来越大，这时候四叉树就能派上用场——它是一种二维空间索引结构，能快速定位目标点可能所属的区域，减少需要检查的区域数量。

核心实现思路 #

1. 节点结构：每个四叉树节点代表一块矩形区域，包含四个子节点（东北、西北、东南、西南象限），以及当前节点存储的Region列表。当节点内的Region数量超过阈值时，就拆分子节点。
2. 插入Region：把Region插入到对应象限的子节点中，递归直到达到最大深度或节点内Region数量未超阈值。
3. 查询点：从根节点开始，先检查当前节点的Region，再递归检查包含目标点的子节点，直到找到匹配的Region或遍历完所有可能节点。

Kotlin简化版四叉树示例 #

// 辅助矩形类，代表四叉树节点的边界
data class Rect(val x: Int, val z: Int, val width: Int, val height: Int) {
    fun contains(point: Point): Boolean {
        return point.x in x..x+width && point.z in z..z+height
    }

    fun intersects(other: Rect): Boolean {
        return x <= other.x + other.width && x + width >= other.x &&
               z <= other.z + other.height && z + height >= other.z
    }
}

data class Point(val x: Int, val z: Int)

class QuadTreeNode(
    private val bounds: Rect,
    private val maxDepth: Int,
    private val maxRegionsPerNode: Int,
    private val depth: Int = 0
) {
    private val regions = mutableListOf<Region>()
    private var children: Array<QuadTreeNode>? = null

    fun insert(region: Region) {
        // 达到最大深度，直接存入当前节点
        if (depth >= maxDepth) {
            regions.add(region)
            return
        }

        // 节点内区域数量超标，拆分出子节点
        if (regions.size >= maxRegionsPerNode && children == null) {
            split()
        }

        // 优先插入到子节点（如果存在）
        children?.forEach { child ->
            if (child.bounds.intersects(region.toRect())) {
                child.insert(region)
            }
        } ?: regions.add(region)
    }

    fun isPointInAnyRegion(point: Point): Boolean {
        // 先检查当前节点的区域
        if (regions.any { it.contains(point) }) {
            return true
        }

        // 递归检查子节点
        children?.forEach { child ->
            if (child.bounds.contains(point) && child.isPointInAnyRegion(point)) {
                return true
            }
        }

        return false
    }

    private fun split() {
        val halfWidth = bounds.width / 2
        val halfHeight = bounds.height / 2
        val x = bounds.x
        val z = bounds.z

        children = arrayOf(
            // 东北象限
            QuadTreeNode(Rect(x + halfWidth, z, halfWidth, halfHeight), maxDepth, maxRegionsPerNode, depth + 1),
            // 西北象限
            QuadTreeNode(Rect(x, z, halfWidth, halfHeight), maxDepth, maxRegionsPerNode, depth + 1),
            // 西南象限
            QuadTreeNode(Rect(x, z + halfHeight, halfWidth, halfHeight), maxDepth, maxRegionsPerNode, depth + 1),
            // 东南象限
            QuadTreeNode(Rect(x + halfWidth, z + halfHeight, halfWidth, halfHeight), maxDepth, maxRegionsPerNode, depth + 1)
        )
    }
}

// Region扩展函数
fun Region.toRect() = Rect(minX, minZ, maxX - minX, maxZ - minZ)
fun Region.contains(point: Point) = point.x in minX..maxX && point.z in minZ..maxZ

使用方式 #

// 初始化四叉树（假设你的世界X/Z范围是0到1000）
val quadTree = QuadTreeNode(Rect(0, 0, 1000, 1000), maxDepth = 4, maxRegionsPerNode = 5)
// 插入所有区域
regions.forEach { quadTree.insert(it) }
// 查询点是否在区域内
val isInRegion = quadTree.isPointInAnyRegion(Point(location.x, location.z))

如果你需要Java实现，核心逻辑和Kotlin一致，这里给出标准化Region和判断函数的版本：

Java版Region #

public class Region {
    private final int minX;
    private final int maxX;
    private final int minZ;
    private final int maxZ;

    public Region(Location originBlock, Location finalBlock) {
        this.minX = Math.min(originBlock.getX(), finalBlock.getX());
        this.maxX = Math.max(originBlock.getX(), finalBlock.getX());
        this.minZ = Math.min(originBlock.getZ(), finalBlock.getZ());
        this.maxZ = Math.max(originBlock.getZ(), finalBlock.getZ());
    }

    public boolean isValidRegion() {
        return (maxX - minX + 1) >= 5 && (maxZ - minZ + 1) >= 5;
    }

    public boolean contains(Location location) {
        int x = location.getX();
        int z = location.getZ();
        return x >= minX && x <= maxX && z >= minZ && z <= maxZ;
    }
}

Java版判断函数 #

public boolean isInRegion(Location location, java.util.Set<Region> regions) {
    // 对应Kotlin的none()，即"不在任何区域内"返回true
    for (Region region : regions) {
        if (region.contains(location)) {
            return false;
        }
    }
    return true;
}

四叉树的Java实现可以参考Kotlin版本的逻辑，语法上做对应转换即可。

内容的提问来源于stack exchange，提问作者User12322341232142