Java - 检测具有给定坐标的直线

Question

添加信息：

我正在使用正方形的内部作为竞技场。启动时，方块会以随机位置和旋转方式生成，但我无法访问任何方块属性。

然后我在广场内有一个移动的物体，我正在为其构建人工智能，我希望该物体“学习”竞技场墙壁的位置。每次物体撞到墙上时，我都会得到一个触摸返回，所以我知道它是否被击中。我正在使用它来映射物体撞击墙壁的全局位置并保存它......在同一面墙上击中 3 次后，我想在数学上“画一条直线”沿着那些将代表竞技场墙壁的点- 有了这个，我可以告诉我的对象不要靠近这些坐标。

3个点的原因？好吧，如果物体撞到墙的一侧，然后又撞到墙的另一侧，我会从一侧画一条线到另一侧，给出关于墙在哪里的错误数据。

如果 Java 看到三个（或更多）内联点，它就知道该对象撞到了同一堵墙（或者更靠上）。

继续：

我正在尝试用给定的坐标数据绘制线条。基本上我有一个保存 X 和 Y 坐标的数组，我希望能够从数学上检测它们是否构成一条直线（给出或获取几个像素）。（坐标是一个正方形的边界）

例如，数组可能是这样的：

[x0][y0] - 1,1

[x1][y1] - 2,2

[x2][y2] - 5,5

这将在正方形的一侧呈现一条对角线，如下所示：

但有时我可能会得到正方形一侧的一个坐标，然后是另一侧，所有这些都混淆了（也不一定是 90 度角！）。所以我希望能够遍历数组，并检测哪些坐标构成一条线（或正方形的边界），如下所示：

所以现在，我有一个二维数组：

private double wallLocations[][] = new double[10][10];

和一个不能完成工作的 while 循环。我真的不知道从哪里开始这个：

for(int r = 0; r < wallIndex; r++){
            for(int c = 0; c < wallIndex; c++){

                int index = 0;
                if(wallLocations[r][index] == wallLocations[r][c] && wallLocations[r][index + 1] == wallLocations[r][c] &&
                        wallLocations[r][index + 2] == wallLocations[r][c]){

                    System.out.println("***** Wall Here! *****");
                    index++;
                }

            }
        }

- - 更新 - -

这是我正在寻找的一个更好的例子。红点代表进入的坐标，当 3 个或更多点排列时检测到一条线（如果它是 2 个点，那么它会检测到任何一个点）......你注意到这开始看起来像边界一个正方形？

Answer 1

这似乎本质上是一个聚类问题，而且这些问题通常非常困难。聚类困难的部分原因是可能有多个适用的映射。

\n\n

例如（请原谅我糟糕的 ASCII 艺术）：

\n\n

 X   X   X  \n\n   X   X   X\n\n X   X   X   X   \n

\n\n

可以被映射

\n\n

 X---X---X          X   X   X \n                     \\ / \\ / \\ \n   X---X---X   or     X   X   X\n                     / \\ / \\   \\\n X---X---X---X      X   X   X   X \n

\n\n

我已经看到使用混合高斯模型的期望最大化算法用于此类事情（当有很多点但只有几条预期线时），但您通常必须为该算法提供一定数量的簇，虽然它的结果很好，但它是一个相当慢的算法，可能需要多次迭代。我有点想我已经看到了一些通常更快的东西，那就是某种图像处理算法，但我必须做一些研究。

\n\n

我有点想知道你会发现每对点 y=mx+b 并根据 m 和 b 对它们进行排序。在 [0,pi) 中找到每一对的角度 \xce\xb8 可能是有利的，并对角度而不是 m 进行排序，或者可能更好地聚类 -cos(2\xce\xb8)要点是线组 {y = -0.0001x + 1, y =1, 和 y=0.0001x + 1} 非常相似，线组 {y= -10000x + 10, x = 0, 和 y=10000x - 10} 也非常相似，但 cos(2\xce\xb8) 应该将它们放置得尽可能远，因为每组之间的任何两对都应该几乎垂直。

\n\n

另请注意，在我的示例中，b 对于几乎垂直于 x 轴的线来说并不重要，因此“b”对于直接聚类可能不太有用。

\n\n

我想，也许两条线之间可能有一些可用的“距离”度量，我只是不确定它会是什么。两条几乎平行并在“屏幕上”（点通常所在的位置）会聚的线可能应该被认为比它们在距屏幕一万亿个单位处会聚的情况“更近”——或者它们应该被认为是“更接近”吗？纯粹地说，如果三条线都不平行（如果它们在一个平面上，它们都会在某个地方相交），那么它们永远不会被认为成对地彼此靠近，但直观上，如果我们有两条线，通常是在我们关注的区域中相距一英寸，我们会选择在关注区域中相距一英里的两条相同尖线上距离较近的那对线。这让我觉得也许应该将线之间的面积（由我们的面积*所限制）用作度量。

\n\n

抱歉，我不确定头脑风暴有多大用处，但它可能会给事情带来不同的看法。

\n\n

编辑：你知道吗，通过研究这个可能会找到更好的答案：

\n\n

http://en.wikipedia.org/wiki/Hough_transform

\n\n

编辑二、三：

\n\n

好吧，...您刚刚描述的情况要简单得多，而且不太通用（尽管说实话，我认为我误读了您的初始查询，认为它比实际情况更通用）。

\n\n

您有 4 堵候选墙。让你的 AI 四处弹跳，直到找到三个共线点。这应该是一个简单的组合测试。将这三个点指定为一面墙。根据您拥有的其他点，您实际上可能能够确定或至少估计其他三堵墙（假设它是正方形）。如果您有 5 个点，其中 3 个位于不同的墙上，您应该能够计算出墙之间的距离，从而计算出第 4 堵墙的可能位置。要测试其他两个点是否位于单独的墙壁上，请确保它们成对地不与垂直或平行于墙壁定义的线的线共线，或者如果它们位于平行线上，请测试看看它们之间的距离是否小于墙壁和它们之间的距离（如果是这种情况，则它们位于第一个候选墙对面的墙上）。鉴于它们位于不同的墙壁上，要么面向第一个找到的墙壁，要么位于与该墙壁垂直的墙壁上。无论哪种方式，你都可以找到用一些棘手的几何形状定义墙壁的线条。

\n\n

（实际上，为了确定尺寸，我认为您甚至不需要测试来看看是否有 3 个共线点...我认为您只需要测试来看看您是否已经转了两圈...这至少需要 4 分，但如果你运气不好，可能会更多。必须确定其中两个点与其他两个点位于不同的墙上，这意味着非常大的反弹！）

\n\n

这涉及到一些数学知识，今晚我有点累了，无法进一步解释，而且我不知道您想利用正方形周围点的几何形状，因为您不会\无法在更一般的情况下使用这些属性，所以我将保留它，也许稍后还会删除我之前的一些其他头脑风暴的废品。

\n