Поиск каждой точки пересечения нескольких линий с использованием pygame в python для создания игровой доски

Следующая функция вычисляет пересечение двух линий, заданных точками (P0, P1) и (Q0, Q1):

def lineLineIntersect(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 round(P1[0] * t + P0[0] * (1-t)), round(P1[1] * t + P0[1] * (1-t))
    return None

Алгоритм подробно объясняется в ответе на Проблема с вычислением пересечений линий :

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

Вы должны оценить, пересекает ли линейный сегмент какие-либо другие линейные сегменты. Перебирайте строки во вложенных циклах и найдите пересечение линии с любой другой линией, кроме самой себя, с помощью функции lineLineIntersect:

intersectionPoints = []
for i, line1 in enumerate(board_lines):
    for line2 in board_lines[i:]:
        isectP = lineLineIntersect(line1[:2], line1[2:], line2[:2], line2[2:])
        if isectP:
            intersectionPoints.append(isectP)

Нарисуйте круги в точках пересечения:

for isectP in intersectionPoints:
    pygame.draw.circle(screen, GREEN, isectP, 5)

См. Пример:

import pygame
import math

def lineLineIntersect(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 round(P1[0] * t + P0[0] * (1-t)), round(P1[1] * t + P0[1] * (1-t))
    return None

board_lines = [
    ( 13,15,462,15 ), ( 13,469,462,469 ), #lin1 and line2,outer rect
    ( 62,86,409,86 ), ( 62,389,409,389 ), #line3 and l4,mid reect
    ( 114,186,360,186 ), ( 114,318,360,318 ), #line5,l6,internl rect
    ( 13,15,13,469 ), ( 462,12,462,469 ), #line9,l10,left and right sides
    ( 62,86,62,389 ), ( 409,85,409,389 ), #l7,l8left and right sides
    ( 114,186,114,316), ( 360,187,360,318 ), #l11,lin12left and right sides
    ( 237,15,237,186 ), ( 237,469,237,320 ), #upper V.line,lowerV
    ( 13,242,113,242 ), ( 360,242,462,242 ) #rIGHT LEFT hoRIZONTAL LINE
] 

pygame.init() 

intersectionPoints = []
for i, line1 in enumerate(board_lines):
    for line2 in board_lines[i:]:
        isectP = lineLineIntersect(line1[:2], line1[2:], line2[:2], line2[2:])
        if isectP:
            intersectionPoints.append(isectP)
 
# Define some colors
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
 
# This sets the WIDTH and HEIGHT of each grid location
WIDTH = 20
HEIGHT = 20
 
# This sets the margin between each cell
MARGIN = 5
 
# Create a 2 dimensional array. A two dimensional
# array is simply a list of lists.
grid = []
for row in range(19):
    # Add an empty array that will hold each cell
    # in this row
    grid.append([])
    for column in range(19):
        grid[row].append(0)  # Append a cell
 
# Set row 1, cell 5 to one. (Remember rows and
# column numbers start at zero.)
grid[1][5] = 1
 
WINDOW_SIZE = [800, 600]
screen = pygame.display.set_mode(WINDOW_SIZE)
pygame.display.set_caption("Array Backed Grid")
done = False
clock = pygame.time.Clock()
while not done:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            done = True

    # Set the screen background
    screen.fill(BLACK)
 
    # Draw the grid
    for row in range(19):
        for column in range(19):
            color = WHITE
            if grid[row][column] == 1:
                color = GREEN
                
    for line in board_lines:
        pygame.draw.line(screen, RED, line[:2], line[2:], 3)

    for isectP in intersectionPoints:
        pygame.draw.circle(screen, GREEN, isectP, 5)

    # Limit to 60 frames per second
    clock.tick(60)
    pygame.display.flip()
 
pygame.quit()