我正在为游戏创建一个基于图块的 2D 地形系统。然而,我还使用游戏中的坐标,需要能够将边界框映射到“图块坐标”中,并点击边界框接触的每个图块(不用担心,有一个 kd 树和所有工作)美好的)。使用定点“真实世界”坐标,我可以将每个图块计为 2^n 个,然后简单地右移这些位以截断为图块坐标。我使用最小的 x,y 对和最大的 x,y 对形成一个边界框。我会打电话给他们R0
and R1
分别。
这是一个带有坐标的边界框R0: 0.8, 0.7
to R1: 2.2, 1.7
被映射到图块上。
现在,这很简单。然而,我想将我的图块分成 4 个三角形象限,这让我可以制作更有趣的东西。由于每个图块变成 4 个三角形,我假设它们可以以某种方式由 2 位引用(不一定是我展示的那种)。我想使用尽可能少的位来“标记”这些三角形。我将把一个点的三角形标签放在其图块坐标旁边,以 [XX] 的形式,其中 XX 是指示它是哪个三角形的位。
但是,我在使用它时遇到了几个问题。我需要能够将现实世界的边界框坐标转换为“三角形坐标”,但似乎有损性太大,无法完全描述边界框。三角形区域中的相同坐标可以描述与不同三角形碰撞的边界框。
我在左侧有与之前相同的第一个边界框:R0: 0.8, 0.7
to R1: 2.2, 1.7
右边,我有一个新的边界框R0: 0.8, 0.3
to R1: 2.2, 1.7
,因此左上角的 y 分量向上移动。它们都转换为相同的三角形坐标,但如果在现实世界坐标中完成,则会与不同的三角形发生碰撞。然而,三角形坐标中没有区别,因此数据会丢失并生成一组不正确的碰撞。
此外,同样的问题也发生在以同一三角形开始和结束的边界框上。相同的三角形坐标描述的边界框有时完全在该三角形内,有时则不在该三角形内。
必须有一种方法来映射这些,也许使用更多的位,以便在 kd 树范围查询中执行的所有三角形坐标比较都可以匹配现实世界边界框与现实世界坐标中的相同三角形的碰撞方式。但我不知所措。
我深入兔子洞创建“子图块”,将每个图块分成 4 个轴对齐的正方形,这也将每个象限图块沿其交叉的轴分成 2 个,因为我注意到很多情况是由于不知道其哪一侧而引起的我的坐标映射到的每个三角形。
但当我遵循一个又一个的例外来遵循更详细的规则时,我最终将我的子图块变成了相同的 4 个三角形象限设计,并最终回到了我开始的地方,除了较小的图块。
我只知道has能够实现这种“压缩”并进行适当的比较,但每当我尝试时,我都会继续原地踏步。如何做呢??
edit:
Alexey提出了一个解决方案 https://stackoverflow.com/questions/13731240/bounding-boxes-in-coordinate-system-based-on-right-triangle-quadrants-of-square/13733010#13733010这将允许我描述一个边界框,但它与使用 kd 树查找边界框重叠不兼容。使用我的 kd 树(存储左上角和右下角坐标)范围查询和搜索区域[x0, y0], [x1, y1]
我进行范围查询:
[0, 0, x1, y1]
to [x1, y1, xmax, ymax]
但即使我尝试补偿 8 维坐标,Alexey 的解决方案也不起作用。
我并不介意坐标系是否与我最初考虑的有所不同,只要它仍然可以与三角形象限表现出相同的结果。