# Generate random line path with no intersection

The idea is to generate a path with a certain distance m. Currently the generation pseudo code is as follows:

lines: List of line

lines: line starting at (x:0, y:0) and ending at (x:0, y:1)
for i: 1 to m:
random_angle: randomly generate angle between -90 and 90 degress.
lines[i]: new line starting at the end of lines[i-1] forming and angle = random_angle
between lines[i-1] and and lines[i]


The general idea is illustrated in the below: But the problem is that when m is big enough the lines create a loop and end up intersecting each other. Any solution to this ?

1- Been trying to find a good math library that detects the intersection between 2 lines, then check for each new line if it intersects the others already created, but no library was found

2- Any another algorithm that can generate a random line path ?

• Why do you need a math library to detect a line intersection? We have existing Q&A that shows you how to do that from first principles. Then if an intersection is detected, you can constrain the random angle to a range that does not intersect that segment and try again. Jul 5, 2022 at 19:30
• In general a math library would be useful for future cases. "We have existing Q&A that shows you how to do that from first principles." Can you please provide a link for that ?
– EEAH
Jul 5, 2022 at 19:45
• Just type the keywords you want into the search box. Asking for library recommendations is not on-topic for this site. Jul 5, 2022 at 22:16
• @EEAH Are there any additional constraints about the min/max length of individual segments, segments being the same length, free vertex positions vs. grid-based approaches...? Adding just one constraint will limit the freedom of your path, but will bind the set of possible solutions and make it easier to come up with one. Jul 6, 2022 at 12:40

Finding a line-line intersection has a well documented solution, and while the equation might look complicated it is really simple enough to not warrant a library to solve.

In python it might look like this:

# line is a tuple of two Vector2 (the two end points of the line)
def line_length(line:tuple):
a = Vector2(line)
b = Vector2(line)
return (b - a).length()

# line is a tuple of two Vector2 (the two end points of the line)
def line_contains_point(line:tuple, point:Vector2):
a = line
b = line
if a == point or b == point:
return True

l = line_length(line)

a_to_point = point - a
b_to_point = point - b

return a_to_point.length() <= l and b_to_point.length() <= l

# line_to_check is a tuple of two Vector2 (the two end points of the line)
# line_to_check_against is a tuple of two Vector2 (the two end points of the line)
def find_line_intersection(line_to_check:tuple, line_to_check_against:tuple):
x1 = line_to_check.x
y1 = line_to_check.y
x2 = line_to_check.x
y2 = line_to_check.y

x3 = line_to_check_against.x
y3 = line_to_check_against.y
x4 = line_to_check_against.x
y4 = line_to_check_against.y

denominator = (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4)
if denominator == 0:
return (True, None)

xNominator = (x1*y2 - y1*x2)*(x3 - x4) - (x1 - x2)*(x3*y4 - y3*x4)
yNominator = (x1*y2 - y1*x2)*(y3 - y4) - (y1 - y2)*(x3*y4 - y3*x4)

px = xNominator / denominator
py = yNominator / denominator

point = Vector2(px, py)
on_line = line_contains_point(line_to_check, point) and line_contains_point(line_to_check_against, point)
return (on_line is not None and on_line, point)


An algorithm that creates a path that does not intersects with itself simple enough to create, as all it has to do is to check the new line to see if it intersects with any of the previous lines:

lines: line starting at (x:0, y:0) and ending at (x:0, y:1)
for i: 1 to m:
possible_angles = -90 to 90 in random order
for random_angle in possible_angle

new_line: new line starting at the end of lines[i-1] forming and angle = random_angle
between new_line and and lines[i]
if not intersects(new_line,lines)
lines[i]: new_line
break


What is harder is to find an algorithm that never "wraps in" on itself to the point where there is no next line that does not intersect an existing line. But this can potentially be solved by detecting that state, and in those cases remove a number of path segments and then trying again.

This sort of solution gets progressively slower as the max length of the path goes up, but depending on your use-case it could work. In the above example I manually add a segment on a key-press to slow the process down, I also reduce the path manually when it's stuck in a loop, but that would just be a matter of saying if stuck remove N number of segments.

Full python source for the above example:

import random
import pygame
from pygame.math import Vector2

pygame.init()
screen = pygame.display.set_mode((400, 300))
should_run = True

# line is a tuple of two Vector2 (the two end points of the line)
def line_length(line:tuple):
a = Vector2(line)
b = Vector2(line)
return (b - a).length()

# line is a tuple of two Vector2 (the two end points of the line)
def line_contains_point(line:tuple, point:Vector2):
a = line
b = line
if a == point or b == point:
return True

l = line_length(line)

a_to_point = point - a
b_to_point = point - b

return a_to_point.length() <= l and b_to_point.length() <= l

# line_to_check is a tuple of two Vector2 (the two end points of the line)
# line_to_check_against is a tuple of two Vector2 (the two end points of the line)
def find_line_intersection(line_to_check:tuple, line_to_check_against:tuple):
x1 = line_to_check.x
y1 = line_to_check.y
x2 = line_to_check.x
y2 = line_to_check.y

x3 = line_to_check_against.x
y3 = line_to_check_against.y
x4 = line_to_check_against.x
y4 = line_to_check_against.y

denominator = (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4)
if denominator == 0:
return (True, None)

xNominator = (x1*y2 - y1*x2)*(x3 - x4) - (x1 - x2)*(x3*y4 - y3*x4)
yNominator = (x1*y2 - y1*x2)*(y3 - y4) - (y1 - y2)*(x3*y4 - y3*x4)

px = xNominator / denominator
py = yNominator / denominator

point = Vector2(px, py)
on_line = line_contains_point(line_to_check, point) and line_contains_point(line_to_check_against, point)
return (on_line is not None and on_line, point)

def extend_path(path:list, line_length:float):
from_point = path[-1]
to_point = Vector2()
possible_angles = list(range(-90, 90, 1))
random.shuffle(possible_angles)

last_direction = (path[-1] - path[-2]) if len(path) > 1 else Vector2(line_length, 0)
while len(possible_angles) > 0:
angle = possible_angles.pop(0)
to_point = from_point + last_direction.rotate(angle)
path.append(to_point)
if check_if_path_is_valid(path):
return True
path.pop()

return False

def check_if_path_is_valid(path:list):
lines = []
for index in range(1, len(path)):
lines.append( (path[index - 1], path[index]))

for line in lines:
for index in range(1, len(path)):
other_line = (path[index - 1], path[index])
intersects_on_line, intersection_point = find_line_intersection(line, other_line)
if other_line != line and intersects_on_line:
if intersection_point != line and intersection_point != line:
return False
return True

point = Vector2(200, 150)
path = [ point ]
mouse_position = Vector2()
extend_path(path, 16)

while should_run:
screen.fill((10, 20, 40))
# Build two-point segments from path
lines = []
for index in range(1, len(path)):
lines.append( (path[index - 1], path[index]))

for line in lines:
pygame.draw.line(screen, (40, 80, 160), line, line)

pygame.display.flip()

for events in pygame.event.get():
if events.type == pygame.KEYDOWN:
if events.key == pygame.K_w:
if not extend_path(path, 16):
path.pop()
if events.key == pygame.K_q:
path = [ point ]
if events.key == pygame.K_e:
path.pop()

if events.type == pygame.MOUSEMOTION:
mouse_position = pygame.mouse.get_pos()
if events.type == pygame.QUIT:
should_run = False

• Thank you. Regarding the math library it would be helpful having a library that does this kind of stuff in general in game development. Moreover can you post a solution in 3d space ? It should be the same idea but with different equations right ?
– EEAH
Jul 8, 2022 at 13:57
• There are plenty of libraries that does the intersection test for you, I am not sure what language you're using but finding a library should be trivial. As for the 3D solution, it's analog to the 2D with an added z component. Jul 10, 2022 at 16:11