计算线交点的问题 [英] Problem with calculating line intersections
本文介绍了计算线交点的问题的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我试图显示相交线的点，但计算出的点在实际相交之间.
(
P ... 点在 1. 线上R ... 1. 线的方向Q ... 点在 2. 线上S ... 2. 线的方向alpha ... Q-P 和 R 之间的角度beta ... R 和 S 之间的角度伽玛 = 180° - α - βh = |Q-P |*罪(阿尔法)u = h/sin(beta)t = |Q-P |* sin(gamma)/sin(beta)t = 点(Q-P，(S.y，-S.x))/点(R，(S.y，-S.x))=行列式(mat2(Q-P，S))/行列式(mat2(R，S))u = 点(Q-P，(R.y，-R.x))/点(R，(S.y，-S.x))=行列式(mat2(Q-P，R))/行列式(mat2(R，S))X = P + R * t = Q + S * u另见
导入pygame导入数学随机导入def intersect_line_line_vec2(startObs, endObs, origin, endpoint):P = pygame.Vector2(startObs)R = (endObs - P)Q = pygame.Vector2(原点)S = (端点 - Q)d = R.dot((S.y, -S.x))如果 d == 0:返回无t = (Q-P).dot((S.y, -S.x))/du = (Q-P).dot((R.y, -R.x))/d如果 0 <= t <= 1 并且 0 <= u <= 1:X = P + R * t返回 (X.x, X.y)返回无def intersect_line_line(P0, P1, Q0, Q1):d = (P1[0]-P0[0]) * (Q1[1]-Q0[1]) + (P1[1]-P0[1]) * (Q0[0]-Q1[0])如果 d == 0:返回无t = ((Q0[0]-P0[0]) * (Q1[1]-Q0[1]) + (Q0[1]-P0[1]) * (Q0[0]-Q1[0]))/du = ((Q0[0]-P0[0]) * (P1[1]-P0[1]) + (Q0[1]-P0[1]) * (P0[0]-P1[0]))/d如果 0 <= t <= 1 并且 0 <= u <= 1:返回 P1[0] * t + P0[0] * (1-t), P1[1] * t + P0[1] * (1-t)返回无def createRays(中心):返回 [(center[0] + 1200 * math.cos(angle), center[1] + 1200 * math.sin(angle)) 范围内的角度 (0, 360, 10)]def createObstacles(表面):w, h = surface.get_size()返回 [((random.randrange(w), random.randrange(h)), (random.randrange(w), random.randrange(h))) for _ in range(5)]窗口 = pygame.display.set_mode((800, 800))时钟 = pygame.time.Clock()原点 = window.get_rect().center射线 = createRays(origin)障碍物 = 创建障碍物(窗口)move_center = 真运行 = 真运行时:时钟滴答(60)对于 pygame.event.get() 中的事件:如果 event.type == pygame.QUIT:运行 = 错误如果 event.type == pygame.MOUSEBUTTONDOWN:障碍物 = 创建障碍物(窗口)如果 event.type == pygame.KEYDOWN:move_center = 不是 move_center如果移动中心:origin = pygame.mouse.get_pos()射线 = createRays(origin)window.fill(0)对于射线中的端点:pygame.draw.line(窗口，(128, 128, 128)，原点，端点)pygame.draw.circle(window, (255, 255, 255), origin, 10)开始，结束于障碍:pygame.draw.line(窗口，(255, 0, 0)，开始，结束)对于射线中的端点:pos = intersect_line_line(开始，结束，原点，端点)如果位置:pygame.draw.circle(window, (0, 255, 0), (round(pos[0]), round(pos[1])), 3)pygame.display.flip()pygame.quit()出口()I am trying to display the points of intersecting lines, but the calculated points are between the actual intersectings.
(https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection)
I have checked the formulars multiple times and used another formula for calculating the intersecting points x, y [x3+u*(x4-x3), y3+u*(y4-y3)] instead of [x1+t*(x2-x1), y1+t*(y2-y1)], but that just made the points somewhere really wrong
("d" is not referenced on the wikipedia page and is just the divisor for the formulars of t and u)
Function for calculating the intersection
def checkcol(self, startObs, endObs):
x1, y1 = startObs
x2, y2 = endObs
x3, y3 = run.lamp
x4, y4 = self.endpoint
d = (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)
t = ((x1-x3)*(y3-y4)-(y1-y3)*(x3-x4))/d
u = ((x1-x2)*(y1-y3)-(y1-y2)*(x1-x3))/d
if 0 < t < 1 and 1 > u > 0:
pygame.draw.circle(run.screen, pygame.Color('green'), (round(x1+t*(x2-x1)), round(y1+t*(y2-y1))), 3)
The whole code
import pygame
import sys
import math
import random as rd
class Obs(object):
def __init__(self, startp, endp):
self.startp = startp
self.endp = endp
def drawww(self):
pygame.draw.line(run.screen, pygame.Color('red'), (self.startp), (self.endp))
for ray in run.lines:
ray.checkcol(self.startp, self.endp)
class rays(object):
def __init__(self, endpoint):
self.width = 2
self.endpoint = endpoint
def draww(self):
pygame.draw.line(run.screen, pygame.Color('white'), run.lamp, self.endpoint, 2)
def moveEnd(self, xoff, yoff):
self.endpoint[0] += xoff
self.endpoint[1] += yoff
def checkcol(self, startObs, endObs):
x1, y1 = startObs
x2, y2 = endObs
x3, y3 = run.lamp
x4, y4 = self.endpoint
d = (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)
t = ((x1-x3)*(y3-y4)-(y1-y3)*(x3-x4))/d
u = ((x1-x2)*(y1-y3)-(y1-y2)*(x1-x3))/d
if 0 < t < 1 and 1 > u > 0:
pygame.draw.circle(run.screen, pygame.Color('green'), (round(x1+t*(x2-x1)), round(y1+t*(y2-y1))), 3)
class Control(object):
def __init__(self):
self.winw = 800
self.winh = 800
self.screen = pygame.display.set_mode((self.winw, self.winh))
self.fps = 60
self.clock = pygame.time.Clock()
self.lamp = [400, 400]
self.lampr = 13
self.lines = []
self.r = 10
self.Obs = [Obs((rd.randint(0, self.winw), rd.randint(0, self.winh)),
(rd.randint(0, self.winw), rd.randint(0, self.winh))) for i in range(5)]
self.done = False
def event_loop(self):
for event in pygame.event.get():
if event.type == pygame.QUIT:
self.done = True
elif event.type == pygame.KEYDOWN:
if event.key == pygame.K_F5:
self.__init__()
if pygame.mouse.get_pressed() == (1, 0, 0):
self.lamp = (pygame.mouse.get_pos())
for line in self.lines:
line.moveEnd(pygame.mouse.get_rel()[0], pygame.mouse.get_rel()[1])
def draw(self):
self.screen.fill((pygame.Color('black')))
pygame.draw.circle(self.screen, pygame.Color('white'), self.lamp, self.lampr)
for line in self.lines:
line.draww()
for obs in self.Obs:
obs.drawww()
def createlines(self):
self.lines.clear()
for angle in range(0, 361, 9):
self.lines.append(rays([self.lamp[0] + 1200 * math.cos(angle), self.lamp[1] + 1200 * math.sin(angle)]))
def main_loop(self):
while not self.done:
self.event_loop()
self.createlines()
self.draw()
pygame.display.update()
self.clock.tick(self.fps)
pygame.display.set_caption(f"Draw FPS: {self.clock.get_fps()}")
if __name__ == '__main__':
run = Control()
run.main_loop()
pygame.quit()
sys.exit()
Expected the points of intersecting to be at the actual points of intersection.
解决方案
To find the intersection points of 2 rays or line segments in two-dimensional space, I use vector arithmetic and the following algorithm:
P ... point on the 1. line
R ... direction of the 1. line
Q ... point on the 2. line
S ... direction of the 2. line
alpha ... angle between Q-P and R
beta ... angle between R and S
gamma = 180° - alpha - beta
h = | Q - P | * sin(alpha)
u = h / sin(beta)
t = | Q - P | * sin(gamma) / sin(beta)
t = dot(Q-P, (S.y, -S.x)) / dot(R, (S.y, -S.x)) = determinant(mat2(Q-P, S)) / determinant(mat2(R, S))
u = dot(Q-P, (R.y, -R.x)) / dot(R, (S.y, -S.x)) = determinant(mat2(Q-P, R)) / determinant(mat2(R, S))
X = P + R * t = Q + S * u
See also Line–line intersection
If t == 1, then X = P + R. This can be used to assess whether the intersection is on a line segment.
If a line is defined through the 2 points L1 and L2, it can be defined that P = L1 and R = L2-L1. Therefore the point of intersection (X) lies on the line segment from L1 to L2 if 0 <= t <= 1.
The same relation applies to u and S.
The following function implements the above algorithm using pygame.math.Vector2 objects of the pygame.math module:
def intersect_line_line_vec2(startObs, endObs, origin, endpoint):
P = pygame.Vector2(startObs)
R = (endObs - P)
Q = pygame.Vector2(origin)
S = (endpoint - Q)
d = R.dot((S.y, -S.x))
if d == 0:
return None
t = (Q-P).dot((S.y, -S.x)) / d
u = (Q-P).dot((R.y, -R.x)) / d
if 0 <= t <= 1 and 0 <= u <= 1:
X = P + R * t
return (X.x, X.y)
return None
The same algorithm without the use of the pygame.math module, less readable but more or less the same:
def intersect_line_line(P0, P1, Q0, Q1):
d = (P1[0]-P0[0]) * (Q1[1]-Q0[1]) + (P1[1]-P0[1]) * (Q0[0]-Q1[0])
if d == 0:
return None
t = ((Q0[0]-P0[0]) * (Q1[1]-Q0[1]) + (Q0[1]-P0[1]) * (Q0[0]-Q1[0])) / d
u = ((Q0[0]-P0[0]) * (P1[1]-P0[1]) + (Q0[1]-P0[1]) * (P0[0]-P1[0])) / d
if 0 <= t <= 1 and 0 <= u <= 1:
return P1[0] * t + P0[0] * (1-t), P1[1] * t + P0[1] * (1-t)
return None
Applied to your code, this means:
class rays(object):
# [...]
def checkcol(self, startObs, endObs):
P = pygame.Vector2(startObs)
R = (endObs - P).normalize()
Q = pygame.Vector2(run.lamp)
S = (self.endpoint - Q).normalize()
d = R.dot((S.y, -S.x))
if R.dot((S.y, -S.x)) == 0:
return
t = (Q-P).dot((S.y, -S.x)) / d
u = (Q-P).dot((R.y, -R.x)) / d
if 0 <= t <= 1 and 0 <= u <= 1:
X = P + R * t
pygame.draw.circle(run.screen, pygame.Color('green'), (round(X.x), round(X.y)), 3)
Minimal example:
import pygame
import math
import random
def intersect_line_line_vec2(startObs, endObs, origin, endpoint):
P = pygame.Vector2(startObs)
R = (endObs - P)
Q = pygame.Vector2(origin)
S = (endpoint - Q)
d = R.dot((S.y, -S.x))
if d == 0:
return None
t = (Q-P).dot((S.y, -S.x)) / d
u = (Q-P).dot((R.y, -R.x)) / d
if 0 <= t <= 1 and 0 <= u <= 1:
X = P + R * t
return (X.x, X.y)
return None
def intersect_line_line(P0, P1, Q0, Q1):
d = (P1[0]-P0[0]) * (Q1[1]-Q0[1]) + (P1[1]-P0[1]) * (Q0[0]-Q1[0])
if d == 0:
return None
t = ((Q0[0]-P0[0]) * (Q1[1]-Q0[1]) + (Q0[1]-P0[1]) * (Q0[0]-Q1[0])) / d
u = ((Q0[0]-P0[0]) * (P1[1]-P0[1]) + (Q0[1]-P0[1]) * (P0[0]-P1[0])) / d
if 0 <= t <= 1 and 0 <= u <= 1:
return P1[0] * t + P0[0] * (1-t), P1[1] * t + P0[1] * (1-t)
return None
def createRays(center):
return [(center[0] + 1200 * math.cos(angle), center[1] + 1200 * math.sin(angle)) for angle in range(0, 360, 10)]
def createObstacles(surface):
w, h = surface.get_size()
return [((random.randrange(w), random.randrange(h)), (random.randrange(w), random.randrange(h))) for _ in range(5)]
window = pygame.display.set_mode((800, 800))
clock = pygame.time.Clock()
origin = window.get_rect().center
rays = createRays(origin)
obstacles = createObstacles(window)
move_center = True
run = True
while run:
clock.tick(60)
for event in pygame.event.get():
if event.type == pygame.QUIT:
run = False
if event.type == pygame.MOUSEBUTTONDOWN:
obstacles = createObstacles(window)
if event.type == pygame.KEYDOWN:
move_center = not move_center
if move_center:
origin = pygame.mouse.get_pos()
rays = createRays(origin)
window.fill(0)
for endpoint in rays:
pygame.draw.line(window, (128, 128, 128), origin, endpoint)
pygame.draw.circle(window, (255, 255, 255), origin, 10)
for start, end in obstacles:
pygame.draw.line(window, (255, 0, 0), start, end)
for endpoint in rays:
pos = intersect_line_line(start, end, origin, endpoint)
if pos:
pygame.draw.circle(window, (0, 255, 0), (round(pos[0]), round(pos[1])), 3)
pygame.display.flip()
pygame.quit()
exit()
这篇关于计算线交点的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
