Java - 检测给定坐标的直线

5

补充信息:

我正在使用一个正方形内部作为竞技场。在开始时,正方形会以随机位置和旋转角度生成,并且我无法访问任何正方形的属性。

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

为什么是3个点呢?如果物体撞到墙的一侧,然后又撞到墙的另一侧,那么我将从一侧绘制一条线到另一侧,从而给出错误的有关墙位置的数据。

如果Java看到三个(或更多)点在一条直线上,它就知道物体撞到了同一堵墙(不管是上面还是下面)。

继续:

我正试图通过给定的坐标数据映射出线条。基本上,我有一个保存X和Y坐标的数组,并且我希望能够数学上检测它们是否组成一条直线(或多或少地)。 (这些坐标是正方形的边框)

例如,数组可能像这样:

[x0][y0] - 1,1

[x1][y1] - 2,2

[x2][y2] - 5,5

这将呈现正方形一侧的对角线,如下所示:

enter image description here

但有时我可能会混合使用正方形的某一侧的一组坐标和另一侧的一组坐标(而且不一定是90度的角度!)。因此,我希望能够运行整个数组,并检测哪些坐标构成一条线(或正方形的边框),如下图所示:

enter image description here

因此,现在我有一个二维数组:

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个点,则会检测到任何和所有点)...你注意到这开始看起来像是一个正方形的边界了吗?

enter image description here

2个回答

2
这似乎基本上是一个聚类问题,而这些问题通常会很难。聚类难的一部分原因是可能存在多个适用的映射。
例如(请原谅我的糟糕 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和y=0.0001x+1}非常相似,线组{y=-10000x+10,x=0和y=10000x-10}也非常相似,但cos(2θ)应该将它们尽可能地分开,因为每个组之间的任意两个对都应该几乎垂直。
请注意,在我的例子中,对于几乎垂直于x轴的线条,b并不重要,因此“b”在直接聚类方面可能没有那么有用。
我猜,也许存在一些可利用的“距离”度量方法来衡量两条线之间的距离,但我不确定它应该是什么。在屏幕上(通常有点的地方)汇聚的几乎平行的两条线可能应该被认为比它们在屏幕一万亿个单位外汇聚更“近” - 还是应该这样?纯粹地说,如果三条线都不平行,则它们之间永远不可能成对地彼此更靠近(如果它们在一个平面上,则它们将在某个地方相遇),但直觉告诉我们,如果我们有两条线,在我们关心的区域内通常相距一英寸,我们会选择这对线比起在我们关心的区域内相距一英里的两条完全相同方向的线更加靠近。这使我想到也许应该使用作为度量标准的线之间的区域,由我们的区域限制。
抱歉,我不确定所有这些头脑风暴可能有多有用,但它可能会使事情变得不同。
编辑:你知道吗,也许可以通过研究这个找到更好的答案。

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

第二和第三次编辑:
好的,你刚刚描述的情况要简单得多,也不那么通用(虽然,说实话,我认为我最初误读了你的查询,认为它比实际情况更通用)。
你有4个候选墙。让你的人工智能在墙壁之间弹跳,直到找到三个共线点。这应该是一个简单的组合测试。将这三个点分配给一面墙。根据你所拥有的其他点,你实际上可能能够确定或至少估计其他三面墙(假设它是一个正方形)。如果你有5个点,其中3个在不同的墙上,你应该能够计算出墙之间的距离,从而确定第四面墙的位置。为了测试另外两个点是否在不同的墙上,请确保它们两两之间没有与你的墙定义的线垂直或平行的线,或者如果它们在平行线上,请测试它们之间的距离是否小于墙与它们之间的距离(如果是这种情况,它们就在第一个候选墙的对面)。假设它们在不同的墙上,其中一个面向第一个找到的墙,或者它们在垂直于那堵墙的墙上。无论哪种方式,你都可以通过一些巧妙的几何学方法找到定义墙壁的线。
实际上,为确定尺寸,我认为您甚至不需要测试是否有3个共线点......我认为您只需要测试是否已经进行了两次转向......最少需要4个点,但如果不幸的话可能需要更多。其中两个点必须能够确定在与另外两个点不同的墙上,这意味着非常大的反弹!这涉及到一些数学问题,而我今晚有点累,无法进一步解释。我也不知道您想利用多少关于正方形周围点的几何性质,因为您无法在更一般的情况下使用这些属性,所以我就说到这里吧,也许稍后还会删除我的其他先前的头脑风暴产物。

好的,目前我正在使用三个嵌套的for循环来处理它,因此它同时查看3个x和y坐标,将它们相加然后求平均值(0,3 1,4 2,4 = 1,4)。然后,我使用公式y == mx + b来检查我的移动对象位置是否靠近正方形的边缘。唯一的问题是,我不知道m或b的值。 - Oliver Jones
另外,我已经在我的问题中添加了额外的信息 - 希望这能让您更好地了解我的情况。谢谢。 - Oliver Jones
太棒了,我现在正在使用“(y1-y2) * (x1-x3) == (y1-y3) * (x1-x2)”来检查任意三个坐标是否共线,如果是,则有一堵墙。 - Oliver Jones
我现在需要以某种方式检查它与我的对象位置是否相符 - 我将立即开始处理。 - Oliver Jones

0
如果你有两个点,你可以使用 Math.atan2 计算连接线的斜率。

谢谢,但这在我的情况下行不通,因为一个坐标可能来自一侧,另一个来自另一侧,这会让Java认为那就是正方形的边界。 - Oliver Jones
斜率在讨论函数导数时很有用,但在如此几何空间中却不是那么有用。因为:连接点(0,0)和(0,1)之间的连线斜率是多少? - Chris Martin
好的,斜率是随机的,像正方形一样,在启动时会随机放置并随机旋转(请记住,我无法从正方形本身获取任何属性或信息,只能获取坐标)。谢谢。 - Oliver Jones

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接