how to mark an intersection of lines with iteration

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By EmpressMaia

im trying to write a script that genrates some random lines and draws a sprite on the intersections, i noticed the “line_intersects_line_2d” method in the geometry class states that it uses direction vectors and not normal vectors? am i using the wrong data type to find the intersections and if so is that why the sprites dont appear on the intersections?

func get_intersections(line1,line2):

return Geometry.line_intersects_line_2d(line1.get_points()[0],line1.get_points()[1],line2.get_points()[0],line2.get_points()[1])

for line in nodes:
	if intersections >= nodes.size()-1:
		break
	if get_intersections(line,nodes[intersections]):
		intersections += 1
		var int_sprite = Sprite.new()
	
		int_sprite.texture = load("res://icon.png")
		int_sprite.position.x = get_intersections(line,nodes[intersections]).x
	
		int_sprite.position.y = get_intersections(line,nodes[intersections]).y
		int_sprite.scale.x = .350
		int_sprite.scale.y = .350
		add_child(int_sprite)

i omitted some code i dont think would be useful for my question but the full script can be found here: gd script lines thing - Pastebin.com

:bust_in_silhouette: Reply From: timothybrentwood
if get_intersections(line,nodes[intersections]):
    intersections += 1
    var int_sprite = Sprite.new()

    int_sprite.texture = load("res://icon.png")
    int_sprite.position.x = get_intersections(line,nodes[intersections]).x

    int_sprite.position.y = get_intersections(line,nodes[intersections]).y

First you test if nodes[0] intersects with nodes[1] then you increment intersections so you assign your positions based on the intersection of nodes[0] and nodes[2]. That’s probably why they aren’t drawn at all intersections.

I would recommend doing:

var current_intersection = get_intersections(line,nodes[intersections])
if current_intersection:
    intersections += 1
    var int_sprite = Sprite.new()

    int_sprite.texture = load("res://icon.png")
    int_sprite.position.x = current_intersection.x

    int_sprite.position.y = current_intersection.y

Your algorithm only checks to see if line N intersects with line N+1. It’s possible (though improbable) that you have a single horizontal line that and the rest are vertical lines that all intersect with the single horizontal line, your algorithm would only detect one of these collisions. It’s also possible to have n*n intersections for n lines.

You should iterate through a nested for loop. The outer for loop should iterate from n = 0 to n = nodes.size() - 2 the inner for loop should iterate from m = n + 1 to m = nodes.size() - 1. Then you test the intersection of nodes[n] and nodes[m]. This will ensure that you test the intersection of every possible pair of lines.

i tried implementing your solution but it seems like still not all lines are tested.
also im still trying to figuire out why the spirtes dont appear on the intersections when one is found, im so confused

	for line2d in nodes:
	if n == nodes.size()-2:
		break
	n += 1
	for intersection in nodes:
		if m == nodes.size()-1:
			break
		m += n + 1
		print(intersection_counter)
		if return_intersection(nodes[n],nodes[m]):
			intersection_counter += 1
			print(return_intersection(nodes[n],nodes[m]))
		
			var intersection_sprite = Sprite.new()
			var sprite_position_vector = (return_intersection(nodes[n],nodes[m]))
			intersection_sprite.position.x = sprite_position_vector.x
			intersection_sprite.position.y = sprite_position_vector.y
	
			intersection_sprite.texture = load("res://icon.png")
			intersection_sprite.scale.x = .3
			intersection_sprite.scale.y = .3
			add_child(intersection_sprite)
			sprites.append(intersection_sprite)

EmpressMaia | 2021-11-03 17:42

My apologies, I didn’t see the segment_intersects_segment_2d() function in the Geometry class. That is the applicable function here since you’re creating line segments not lines.

I didn’t catch that you were feeding the wrong arguments to line_intersects_line_2d() either. If you wanted to use that functions (when using lines) in the future you would give it the following arguments:

var direction_for_line_1 = (line1.get_points()[1] - line1.get_points()[0]).normalized()
var direction_for_line_2 = (line2.get_points()[1] - line2.get_points()[0]).normalized()
Geometry.line_intersects_line_2d(line1.get_points()[0], direction_for_line_1, line2.get_points()[0], direction_for_line_2)

I checked this code a handful of times and saw no errors in the sprite placement, please let me know if you have any questions about it!

extends Node2D

export (int) var line_amount

var window_width = ProjectSettings.get("display/window/size/width")
var window_height = ProjectSettings.get("display/window/size/height")

var rng = RandomNumberGenerator.new()
var nodes = []

func get_intersections(line1,line2):
	return Geometry.segment_intersects_segment_2d(line1.get_points()[0],line1.get_points()[1],
													line2.get_points()[0],line2.get_points()[1])
 
func _ready():
	for line in line_amount:
		var line2d = Line2D.new()
		nodes.append(line2d)
		
	for node in nodes:
		rng.randomize()
		var rng_x = Vector2(rng.randf_range(0,window_width),rng.randf_range(0,window_height))
		var rng_y = Vector2(rng.randf_range(0,window_width),rng.randf_range(0,window_height))
		node.width = 5
		add_child(node)
		node.add_point(rng_x)
		node.add_point(rng_y)

	# range(n, m) creates an array of [n, n+1, n+2, ..., m-2, m-1]
    # hence using nodes.size() - 1 and not nodes.size() - 2
	for outer_index in range(0, nodes.size() - 1):
		for inner_index in range(outer_index + 1, nodes.size()):
			
			var current_intersection = get_intersections(nodes[outer_index],nodes[inner_index])
			
			if current_intersection:
				var int_sprite = Sprite.new()
				int_sprite.texture = load("res://icon.png")
				
				int_sprite.position.x = current_intersection.x
				int_sprite.position.y = current_intersection.y
				
				int_sprite.scale.x = .350
				int_sprite.scale.y = .350
				
				add_child(int_sprite)

timothybrentwood | 2021-11-03 20:05

oh awesome! i think i get it, thanks

EmpressMaia | 2021-11-03 20:09