Hit-testing / 在扭曲的矩形网格中寻找交点

Question

我有一个矩形网格，表示为二维点的二维数组。像这样的东西（受 C# 启发 pseudo-code）：

Point2D[,] mesh = CreateSampleMesh();
mesh.Plot();

重要特征是：

网格在拓扑上是矩形的，但在几何上 "irregular" 如图所示；
每一行的X坐标和每一列的Y坐标是单调的（即不"reverse directions"）；
每个矩形都是凸的（我猜是第 2 项的必然结果）；

我的问题是：给定一个候选 Point2D，我如何找到哪个“ rectangle" 它在里面，如果有的话？这是我建议的方法签名：

GridPosition position = GetIndexOfBottomLeftRectangleContaining(Point2D candidatePoint);
if (position != null)
{
    int pi = Position.I;
    int pj = Positino.J;
}

Answer 1

您可能会发现用于查找 point is inside a convex polygon or not 是否有用的算法。请注意，那里的第二个答案提出了一种在 2D 中花费四个点积的方法，假设乘法需要常数时间，意味着时间复杂度为 4 * O(D) = 4 * O(2) = O(1).

现在您可以发疯并并行检查那里的所有多边形，这当然不会是 O(N²)，但仍然可能有点矫枉过正。

因此，您需要使用您喜欢的任何数据结构对 space 进行分区，其中每个分区都将包含一个多边形。

一个quadtree:

is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.

在那种情况下似乎会派上用场，因为每片叶子都包含一个多边形（或其中几个，由您选择）。

一旦查询落在一片叶子上，您就会去检查该点是否在这片叶子的多边形内并给出答案。

特别是，我会尝试 Region Quadtree，其中 "represents a partition of space in two dimensions by decomposing the region into four equal quadrants, subquadrants, and so on with each leaf node containing data corresponding to a specific subregion."

查询时间是对数的，在最坏的情况下是线性的，您可以在这些 slides 中读到。

Answer 2

您可以使用某种二维二进制搜索。

示例：如果您有一个点 p(px,py) 并且您的网格存储在一个 5x5 数组中 'mesh[i,j]'，您将从 i=5/2=3 和 j=5/2 开始=3。这里有一些基本的示例代码用于说明。:

int i = 3;
int j = 3;
int iOld = i
int jOld = j;
do {
    iOld = i
    jOld = j;

    Point m = mesh[i,j]; 
    //Compare p with m: 
    if (p.x > m.x) {
        i = (i+5)/2;
    } else {
        i = (i/2)/2;
    }
    if (p.y > m.y) {
        j = (j+5)/2;
    } else {
        j = (j/2)/2;
    }
} while (i != iOld && j != jOld);

此代码仅供参考！您可能必须在靠近节点时验证 i 和 j 是否计算正确，并且它们不会振荡，否则退出条件可能永远不会变为真。否则这应该会很快找到您在网格中的点。

编辑：这种方法假设扭曲是 'benign'，这意味着节点不是扭曲，因此它们移动到不同的正方形（这需要网格线会相交）。如果网格线可以交叉，那么这个方法就不行了。

Answer 3

你很幸运有单调链（多段线），这是对平面进行排序的一种方式。

首先，设计一个程序来判断您是在垂直链的左侧还是右侧。为此，您找到垂直面向该点的线段，并绘制一条水平线。交点告诉你是左还是右。这需要在节点纵坐标中进行二分搜索。

使用此过程找到两边最近的两条链，它们定义了点所在的条纹。现在，通过与水平边缘进行比较，在此条纹中进行最终的二分法搜索将告诉您确切的图块。

对于 N² 个节点的数组，这将花费与 Log²N 成比例的时间并且不需要额外的数据结构！

Hit-testing / 在扭曲的矩形网格中寻找交点

Hit-testing / finding intersection in a distorted rectangular mesh

collision-detection

bounding-box

nearest-neighbor

hittest

computational-geometry