在2D平面上查找无法访问的点

Question

我一直在研究JavaScript/JQuery代码,它允许输入框之间的箭头键移动(是的,我知道这打破了标准UI).

它通过循环遍历每个元素并在每个方向(左,右,上和下)找到最接近的方法.

例

P1:(0,0),P2:(1,0),P3:(0,2)

P1有一个指向右侧(P2)和一个点向上(P3).

P2有一个点向左(P1)和一个点向上(P3).
禁止摄影

P3有两个点(P1和P2),但P1更接近.

因此最后的动作是:

Up
  1 -> 3
  2 -> 3
Right
  1 -> 2
Down
  3 -> 1
Left
  2 -> 1

对于此示例:
P1有两个传入和两个传出连接.
P2有一个传入和两个传出连接.
P3有两个传入和一个传出连接.

这让我想到了.
是否有一组点使得一个或多个点不可访问(0个传入连接),或者可以证明没有这样的集合存在？

---

旁注:
如果忽略向上/向下组件(仅使用左和右垂直分割),则在P1中将P3指向不可访问:(0,0),P2:(2,0),P3:(1,4 ).

---

这是JavaScript/JQuery代码,如果它可以帮助任何人.

function arrowKeyNavigation(elements) {
    // Get the position of each element.
    var elementOffsets = [];
    elements.each(function(key, element) {
        elementOffsets[key] = $(element).offset();
    });

    // Find the closest point in each direction and store the points in data('keyNav') for later use.
    for (var i = 0; i < elementOffsets.length; i++) {
        var closestPoints = [];

        for (var j = 0; j < elementOffsets.length; j++) {
            if (i != j) {
                var distance = calcDistanceSquared(elementOffsets[i], elementOffsets[j]);
                var quadrant = calcQuadrant(elementOffsets[i], elementOffsets[j]);

                if (closestPoints[quadrant] == undefined || calcDistanceSquared(elementOffsets[i], elementOffsets[closestPoints[quadrant]]) > distance) {
                    closestPoints[quadrant] = j;
                }
            }
        }

        var closestElements = [];
        for (var j = 0; j < closestPoints.length; j++) {
            closestElements[j] = elements[closestPoints[j]];
        }

        $(elements[i]).data('keyNav', closestElements);
    }
}

// Returns the distance between two points squared.
function calcDistanceSquared(offset1, offset2) {
    ...
}

// Returns 0, 1, 2 or 3 for left, up, right and down respectively.
// If a point is EXACTLY 45 degrees it will be classified as either left / right.
function calcQuadrant(offset1, offset2) {
    ...
}

Answer 1

我想了更多，我想我有解决办法。证明草图如下：

假设平面上有有限数量的点 (R^2)。选取任意一点并将其称为目的地。然后取任何其他点。该点将 R^2 分为四个象限，如您用红色绘制的那样。根据定义，目的地位于这四个象限之一。朝那个方向移动。可能会发生以下两种情况之一：
1) 您到达目的地并完成任务
2) 您移动到另一点。

如果为 2，那么您已经靠近了（编辑：通过 1 范数距离，d((x1,y1),(x2,y2)) = |x1-x2|+|y1-y2|）。这需要更多的证据，但我只是草图。目的地现在位于这个新点的某个象限中。

现在请注意，如果您重复此操作，始终朝目的地方向靠近一步（这可能会改变每一步），您到目的地点的距离将每一步减少；你永远无法重新访问某个点，因为你的距离总是在减小。因此，如果您的点数有限，您最终将到达目的地。