用 Python 计算线交点给出了意外的结果

Question

我有一个光线投射程序，可以找到光线与多边形边的交点。在我下面的代码片段中，我有一条线的 y = mx + b 形式的光线和边缘。我通过顶点 ((50, 50), (50, 70), (70, 70), (70, 50)) 定义了一个正方形，并向每个顶点投射光线，我的程序计算了与除 (70, 70) 和 (70, 50) 之外的每个顶点的交点。对于后一种情况，光线似乎 "slip past" 这个顶点并与通过点 (50, 50) 和 (50, 70) 的线相交在一个意想不到的点 (49.99999999999999 16.666666666666643)。澄清一下，这是我的程序检测到的所有交叉点：

(50.0, 50.00000000000001) # Ray was cast towards (50, 50)
(50.0, 70.0) # Ray was cast towards (50, 70)
(50.0, 50.00000000000001) # Ray was cast towards (70, 70). Also unexpected
(49.99999999999999, 16.666666666666643) # Ray was cast towards (70, 50) Unexpected intersection value

在我的 objects.py 文件中：

from math import atan, pi

class Ray:
    def __init__(self, origin, direction):
        self.origin = origin
        self.direction = direction  # radians

        self.endpoint = None

        self.hit = False

    def set_endpoint(self, point):
        self.endpoint = point

    def set_hit(self):
        self.hit = True


class Line:
    def __init__(self, endpoint1, endpoint2):
        self.p1 = endpoint1
        self.p2 = endpoint2

    def direction(self):
        delta_x = self.p2[0] - self.p1[0]
        delta_y = self.p2[1] - self.p1[1]

        if delta_x == 0:  # Undefined slope

            if delta_y > 0:
                return pi / 2

            else:
                return 3 * pi / 2

        else:
            return atan(delta_y / delta_x)


class Polygon:
    def __init__(self, vertices):
        self.vertices = vertices


    def edges(self):
        edges = []

        for i in range(len(self.vertices)):
            # We mod the endpoint point of the line by the amount of vertices
            # since we want the endpoint of our last edge to be the first vertex
            edges.append(Line(self.vertices[i], self.vertices[(i + 1) % len(self.vertices)]))

        return edges

在我的 caster.py 文件中：

from ART import objects
from math import tan


class ShadowCaster:
    def __init__(self, source, polygons):
        self.source = source
        self.polygons = polygons
        self.rays = []

        print(self.polygons)

    def cast_rays(self):
        for polygon in self.polygons:
            for vertex in polygon.vertices:
                direction_to_vertex = objects.Line(self.source, vertex).direction()
                ray = objects.Ray(self.source, direction_to_vertex)

                self.rays.append(ray)

    def process_endpoints(self):
        for ray in self.rays:
            for polygon in self.polygons:
                for edge in polygon.edges():
                    # We are given the endpoints and direction of both the ray and the edge. Find intersection.
                    # We want to obtain the general form y = mx + b for the ray and edge.

                    # Given: y, m, x; solve for b
                    # b = y - mx

                    if not ray.hit:
                        ray_x = ray.origin[0]
                        ray_y = ray.origin[1]
                        ray_m = tan(ray.direction)

                        ray_b = ray_y - ray_m * ray_x

                        edge_x = edge.p1[0]  # Using either p1 or p2 is fine since the line passes through both.
                        edge_y = edge.p1[1]
                        edge_m = tan(edge.direction())

                        edge_b = edge_y - edge_m * edge_x

                        # General case
                        # {y = ax + b
                        # {y = cx + d
                        #
                        # => ax + b = cx + d
                        # => x(a - c) = d - b
                        # => x = (d - b) / (a - c) therefore y = a((d - b) / (a - c)) + b

                        intersect_x = (edge_b - ray_b) / (ray_m - edge_m)
                        intersect_y = ray_m * intersect_x + ray_b

                        print(intersect_x, intersect_y)

                        ray.set_endpoint((intersect_x, intersect_y))
                        ray.set_hit()

我运行的循环：

caster = engine.ShadowCaster(origin=(100, 100), polygons=[objects.Polygon(((50, 50), (50, 70), (70, 70), (70, 50)))])


while 1:
    caster.cast_rays()
    caster.process_endpoints()

对我可能做错的地方有什么建议吗？

Answer 1

在将 "minimal reproducible example" 变为运行并进行了一些调试之后，令人失望的是，问题缺少逻辑：您实际上并没有测试交点是否指向您在射线线和边缘线之间找到实际上在边缘的线段内 - 您只需假设第一个交点是命中，即无条件：

ray.set_endpoint((intersect_x, intersect_y))
ray.set_hit()

并且一旦第一个交集 "found" 就不会进行进一步的交集测试，尽管您的代码会继续迭代它们，这似乎是不必要的。无论如何，结果是您只显示 "intersections" 与多边形的第一条边。

要解决此问题，您需要添加光线与边缘相交的测试。您需要允许浮点 (im) 精度和舍入，即交点被计算为边缘范围之外的一个很小的距离（但如果与另一条边缘的交点更好）。

顺便说一句，使用一般形式 y=mx+b 的一个问题是，当线是~垂直时，它不稳健——假设每条线上有两个点，使用参数形式 y=p 可能更安全*(y2-y1)+y1 和 x=p*(x2-x1)+x1 其中 0.0<=p<=1.0 也可以在不使用标题 "Given two points on each line" 下方的三角函数 ref 的情况下更轻松地检测交点https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

此外，如果您必须使用线方向，那么使用 math.atan2 比 math.atan 更可靠地描述线方向 - 您不必为 dx 为 ~0 的垂直线编写代码保护，并且因为它知道 dy 和 dx 的符号，所以它知道线方向的象限和 returns 范围内的值 +/-pi

用 Python 计算线交点给出了意外的结果

Calculating line intersections with Python gave unexpected result

python

coordinates

linear-algebra

intersection

vertex