我要创建地形的二维，瓦为基础的系统的游戏。不过，我也使用在游戏中的坐标是需要能够以一个边框映射到瓦坐标，打每瓦边框触摸（别担心，有一个kd树和所有工作精细）。使用固定点真实世界的坐标，我可以让每片数为2 ^ N人，只是右移位关闭以截断下来的瓷砖坐标。余形成用最小x，y对和最大x，y对一个边界框。我会打电话给他们 R0 和 R1 分别。

I'm creating a 2D, tile-based system of terrain for a game. However, I'm also using in-game coordinates that need to be able to map a bounding box into the "tile coordinates" and hit each tile the bounding box touches (don't worry, have a kd-tree and all that working fine). Using fixed point "real world" coordinates, I can make each tile count as 2^n of them and simply right shift the bits off to truncate down to tile coordinates. I form a bounding box using the smallest x,y pair and the largest x,y pair. I'll call them R0 and R1 respectively.

下面的坐标 R0边界框：0.8，0.7 到 R1：2.2，1.7 被映射到瓷砖。

Here's a bounding box with coordinates R0: 0.8, 0.7 to R1: 2.2, 1.7 being mapped to the tiles.

现在，这是很简单的。不过，我想拆我的瓷砖为4三角形象限，这让我赚更多的有趣的东西。由于每个瓦片变为4个三角形，我认为它们可以用2位以某种方式（并不一定是一个我显示）被引用。我想用尽可能少的比特尽可能标签这些三角形。我打算把我的三角形标记一个点旁边的图块坐标，在[XX]的形式与XX是位表明它是一个三角形。

Now, that's simple enough. However, I want to split my tiles into 4 triangular quadrants, which lets me make more interesting stuff. Since each tile becomes 4 triangles, I assumed that they can be referenced by 2 bits in some manner (not necessarily the one I show). I want to use as few bits as possible to "label" these triangles. I'm going to put my triangle label for a point right next to its tile coordinates, in the form of [XX] with XX being the bits indicating which triangle it is.

不过，我跑进使用这个几个问题。我需要能够把我的现实世界的边界框坐标转换成三角坐标，但现在看来，实在是太有损充分说明边框。在三角地相同的坐标，可以描述包围盒将碰撞不同的三角形。

However, I've ran into several problems using this. I need to be able to convert my real world bounding box coordinates into "triangle coordinates", but it appears that it is too lossy to fully describe the bounding box. The same coordinates in triangle land can describe bounding boxes that would collide with different triangles.

我像以前一样有相同的第一个边界框左侧： R0：0.8，0.7 到 R1：2.2，1.7 在右边，我有一个新的边框 R0：0.8，0.3 到 R1：2.2，1.7 ，所以左上角的y分量向上移动。它们都转换为相同的三角坐标，但碰撞不同三角形如果是做在真实世界坐标。没有什么区别，在三角坐标，虽然如此，数据将丢失，并产生一个不正确的组冲突

I have the same first bounding box as before on the left: R0: 0.8, 0.7 to R1: 2.2, 1.7 On the right, I have a new bounding box R0: 0.8, 0.3 to R1: 2.2, 1.7, so the y component of the top left corner is moved up. They both translate to the same triangle coordinates, but collide with different triangles if it is done in real world coordinates. No distinction is made in triangle coordinates, though, so data is lost and an incorrect set of collisions is generated.

此外，会发生同样的问题与边界开始和结束在同一个三角形的箱子。同样的三角坐标描述边界框，有时是完全在该三角形，有时没有。

Further, the same problem occurs with bounding boxes that start and end in the same triangle. The same triangle coordinates describe bounding boxes that sometimes are totally in that triangle, and sometimes not.

目前已经得到了一种方式，也许用更多的比特，使所有三角坐标中的kd树的范围查询进行比较可以匹配如何在现实世界包围盒将碰撞在现实世界中那些相同的三角形映射这些，坐标。但我不知所措。

There has got to be a way to map these, maybe using more bits, so that all triangle coordinate comparisons performed in the kd-tree range query can match how the real world bounding box would collide with those same triangles in real world coordinates. But I'm at a loss.

我去了兔子洞创建子砖分裂每个平铺在4轴对齐广场，这也沿着它穿过轴分割各象限瓦2，因为我发现很多情况下是由不知道引起的每个三角形的哪一面我的坐标得到映射。

I went down the rabbit hole creating "sub-tiles" to split each tile in 4 axis-aligned squares, which also split each quadrant tile in 2 along the axis it crosses, since I noticed many cases were caused by not knowing which side of each triangle my coordinates got mapped to.

不过，正如我跟着异常后，异常更加详细的规则，我终于结束了把我的分瓦到相同的4象限的三角形设计，结束了在那里我开始，除了与更小的砖。

But as I followed exception after exception to ever more detailed rules, I eventually ended up turning my sub-tiles into the same 4 triangular quadrant design and ending up where I began, except with smaller tiles.

我知道这只是的的的是可能实现这种COM pression，并有适当的比较，但我一直在兜圈子每当我尝试。如何能不能做到？

I know it just has to be possible to achieve this "compression" and have proper comparisons, but I keep going in circles whenever I try. How can it be done??

编辑： Alexey提出了一个解决方案，让我来描述一个边框，但是它与使用kd树找到边框重叠不兼容。随着我kd树（存储左上角和右下角coords）使用范围查询和搜索区域 [X0，Y0]，[X1，Y1] 我做一个范围查询结束：

edit: Alexey proposed a solution that would allow me to describe a bounding box, but it is incompatible with using a kd-tree to find bounding box overlaps. With my kd-tree (storing the top left and bottom right coords) range query and a search region [x0, y0], [x1, y1] I do a range query over:

[0，0，X1，Y1] 到 [X1，Y1，XMAX，YMAX]

不过，阿列克谢的解决方案，不会与这个工作，即使我试图弥补8三维坐标。

But Alexey's solution won't work with this, even if I attempt to compensate for the 8 dimensional coordinates.

我真的不介意，如果一个坐标系是比我原先考虑的，只要它仍然可以体现与三角象限相同的结果八九不离十不同。

I don't really mind if a coordinate system is sorta different than what I was originally considering, as long as it can still manifest the same results with the triangular quadrants.

推荐答案

好像你所需要的最小的细分是每个正方形分成八分圆。每个正方形应该由两条对角线，水平和垂直中线划分。该瓷砖它结束了。如果对于每个角落的箱子（不只是为左上和右下，但所有四个）您存储在其中八分，你将有足够的信息来找到与您的所有原始三角形的瓷砖碰撞（但不是所有的八分圆）。

Seems the minimal subdivision you need is that of each square into octants. Each square should be divided by two diagonals AND the horizontal and vertical midlines. If for each corner of the box (not just for the upper left and lower right, but for all four) you store in which octant of which tile it ended up, you'll have enough information to find collisions with all your original triangular tiles (but not with all octants).