Проблема с вычислением пересечений линий

Question

Я пытаюсь отобразить точки пересекающихся линий, но вычисленные точки находятся между фактическими пересечениями.

(https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection)

Я несколько раз проверял формулы и использовал другую формулу для вычисления пересекающихся точек x, y [x3+u*(x4-x3), y3+u*(y4-y3)] вместо [x1+t*(x2-x1), y1+t*(y2-y1)], но это просто сделало точки где-то действительно неправильными

("d" не упоминается на странице википедии и является просто делителем для формул t и u)

Функция для вычисления пересечения

    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)

Весь код

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()

Ожидается, что точки пересечения окажутся в фактических точках пересечения.

Answer 1

Если я вычисляю пересечения двух линий, то я использую векторную арифметику и следующий алгоритм:

P     ... point on the 1. line
R     ... normalized direction of the 1. line

Q     ... point on the 2. line
S     ... normalized 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

---

В Pygame pygame.math.Vector2 (или даже pygame.math.Vector3) можно использовать.

Применительно к вашему коду это означает:

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()

        t  =  (Q-P).dot((S.y, -S.x)) / R.dot((S.y, -S.x))
        u  =  (Q-P).dot((R.y, -R.x)) / R.dot((S.y, -S.x))

        V = (endObs - P)
        max_t = math.hypot(V.x, V.y)
        if 0 < t < max_t and u > 0:
            X  =  P + R * t
            pygame.draw.circle(run.screen, pygame.Color('green'), (round(X.x), round(X.y)), 3)