algorithm - 请帮我算一个三角算法

Question

这是问题的图形表示: http://i.imgur.com/aBG3p.jpg

给定起点 (x1,y1) 和终点 (x2,y2)，我必须确定两点之间的路径是否开放，如果不开放，则确定碰撞发生在哪个坐标上。

除了涉及特殊的规则外，这将是一个微不足道的问题:

1. 直线可以截取一个点，将其称为 (i,j) 到一个小的和不同的程度，而不会引起碰撞。如果 (i,j) 直接与 (x1,y1) 相邻，我们可以在不触发碰撞的情况下安全地在其角上切割大约 0.4。然而，如果直接穿过它，我们不能超过 0.4，只能越过拐角。随着我们离 (x,y) 越来越远，这个数字逐渐减小到大约 0.2。不幸的是，我只是想重建我曾经见过的东西，所以我不知道确切的值，我只是近似值。

2. 注意事项 1:如果紧挨着 (i,j) 的空间，在我们相交的平面中，在我们相交的一侧，也被占用，那么无论如何都会发生碰撞.如果我们拦截它太多，碰撞将发生 (i,j)，否则在相关的相邻瓦片中。

我已经多次尝试解决这个问题，但总是以漏报和/或错误瓷砖上的碰撞而告终。我试图在不考虑角度的情况下做到这一点，只是在我们沿着直线行进时查看 x 和 y 的小数点。我不确定是否可以这样做，或者我是否必须以某种方式使用角度，或者以某种方式使用角度是否可以让我的生活更轻松。

如果可以，请帮忙!

Answer 1

通过将占据的网格视为包含单位圆，您似乎可以获得类似于您所描述的结果。这会让你通过角落，但会阻挡任何 2 个相邻的角落，因为它们接触。

所以我会尝试使用您当前的碰撞方法快速检查矩形，然后在发现碰撞后通过测试进入框的线与以框为中心的圆来改进它。