我有一个射线投射程序，可以找到射线和多边形边缘的交点。在下面的代码片段中，我的射线和边缘的形式是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，很高兴地是，这也可以使检测交点变得更容易，而不需要使用三角函数，参考标题下面的 "考虑到每条线上有两个点"。https:/en.wikipedia.orgwikiLine%E2%80%93line_intersection。
此外，如果你必须使用线型方向，那么使用 math.atan2 是比 math.atan 用于描述线的方向--在dx为~0的情况下，你不需要为垂直线编写guard，而且因为它知道dy和dx的符号，所以它知道线方向的象限，并返回一个范围为+-pi的值。