我有一个光线投射程序，可以查找光线和多边形边缘的交点。在下面的代码片段中，我有一行的 y = mx + b 形式的射线和边缘。我通过顶点((50, 50), (50, 70), (70, 70), (70, 50))定义一个正方形，并向每个顶点投射光线，我的程序计算了与除(70, 70)和(70, 50)之外的每个顶点的交点。对于后一种情况，光线似乎"滑过"了这个顶点，并与穿过点的线相交，(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()
关于我可能做错了什么的任何建议？
在令人失望的混乱之后，为了让你的"最小可重现示例"运行，并进行一些调试，问题在于缺少逻辑：你实际上并没有测试你在射线线和边线之间找到的交点是否实际上在边的线段内 - 你只是假设第一个交点是命中， 即无条件的：
ray.set_endpoint((intersect_x, intersect_y))
ray.set_hit()
一旦"找到"了第一个交集，就不会进行进一步的交集测试，尽管您的代码会继续迭代它们，这似乎是不必要的。无论如何，结果是您只显示与多边形第一条边的"交点"。
要解决此问题，您需要添加射线与边缘相交的测试。您需要允许浮点 (im(精度和舍入，即相交仅计算为边范围之外的渐远距离(但如果与另一条边的相交更好，则不会(。
顺便说一句，使用一般形式 y=mx+b 的一个问题是，当线是 ~垂直时它不是健壮的 - 假设每条线上有两个点，使用参数形式 y=p*(y2-y1(+y1 和 x=p*(x2-x1(+x1 可能更安全，其中 0.0<=p<=1.0 这也很高兴地使检测交集更容易，而无需使用三角函数 ref 在标题下方的"每行给定两个点"下面 https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
此外，如果您必须使用线方向，那么使用math.atan2比描述线方向的math.atan更健壮 - 您不必对 dx 为 ~0 的垂直线进行代码保护，并且因为它知道 dy 和 dx 的符号，它知道线方向的象限并返回范围 +/-pi 的值