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

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

例如(请原谅我糟糕的 ascii 艺术):

 X   X   X  

   X   X   X

 X   X   X   X   

可以映射

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

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

我有点想知道在什么地方你可以找到每对点的 y=mx+b 并且他们在 m 和 b 上对它们进行排序。为每一对找到 [0,pi) 中的角度 θ 并根据角度而不是 m 进行排序，或者通过 cos(2θ) 更好地进行聚类可能是有利的。 -- 关键是线组 {y= -0.0001x + 1, y =1, and y=0.0001x + 1} 非常相似，线组 {y= -10000x + 10, x = 0 和 y=10000x - 10} 也非常相似，但是 cos(2θ) 应该将它们尽可能分开，因为每组之间的任何两对应该几乎垂直。

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

我想，也许，两条线之间的“距离”可能有一些可用的度量，我只是不确定它会是什么。两条几乎平行的线在“屏幕上”(点通常所在的位置)会聚时可能应该被认为是“更近”，而不是它们会聚在距屏幕一万亿个单位的地方——或者应该这样认为？纯粹地说，如果三条线都不平行(如果它们在一个平面上，它们都会在某个地方相遇)，则永远不能成对地认为它们彼此更接近，但直观地说，如果我们有两条线通常为一英寸除了我们关注的区域之外，我们会选择在关注区域内相距一英里的两条相同的尖线上更接近的那一对。这让我觉得也许线之间的区域，以我们的区域*为界，应该被用作一个度量。

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

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

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

编辑二和三:

好的，...您刚刚描述的情况要简单得多，而且不那么通用(尽管说实话，我认为我误读了您最初的查询比实际情况更通用)。

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

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

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