Efficient way of detecting if a line touched itself

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

I would like to know if is there a efficient way to detect if a line is touching itself, and where it’s touching, like in the picture below:

enter image description here

:bust_in_silhouette: Reply From: Zylann

You can go with some math:

extends Node2D


func _ready():
	var line = get_node("Line2D")
	
	var points = line.points
	var intersections = find_intersections(points)
	
	# Show intersections somehow
	for pos in intersections:
		var icon = Sprite.new()
		icon.position = pos
		icon.texture = preload("res://icon.png")
		icon.scale = Vector2(0.5, 0.5)
		line.add_child(icon)
	

func find_intersections(points):
	var intersections = []
	
	# Iterate all segments to see if they intersect another.
	# (Start at 1 because it's easier to iterate pairs of points)
	for i in range(1, len(points)):
		
		# Note: the +1 makes sure we don't get two results per segment pairs
		# (intersection of A into B and intersection of B into A, which are the same anyways)
		for j in range(1 + i, len(points)):
			
			if abs(j - i) < 2:
				# Ignore self and neighbors
				continue
			
			var begin0 = points[i - 1]
			var end0 = points[i]
			
			var begin1 = points[j - 1]
			var end1 = points[j]
			
			# Calculate intersection of the two segments
			var intersection = get_segment_intersection(begin0, end0, begin1, end1)
			if intersection != null:
				intersections.append(intersection)
	
	return intersections
		

static func get_segment_intersection(a, b, c, d):
	# http://paulbourke.net/geometry/pointlineplane/ <-- Good stuff
	var cd = d - c
	var ab = b - a
	var div = cd.y * ab.x - cd.x * ab.y

	if abs(div) > 0.001:
		var ua = (cd.x * (a.y - c.y) - cd.y * (a.x - c.x)) / div
		var ub = (ab.x * (a.y - c.y) - ab.y * (a.x - c.x)) / div
		var intersection = a + ua * ab
		if ua >= 0.0 and ua <= 1.0 and ub >= 0.0 and ub <= 1.0:
			return intersection
		return null

	# Segments are parallel!
	return null

Another way would eventually involve a StaticBody2D with a collision shape made of segments, which would allow you to ask the collision engine for intersections. How these collision segments would be created depends on how you generate your line (segment colliders are surprisingly difficult to setup from the editor, so using a script would be better here anyways).

This answer sounds great for a line that is created once in the editor, but I fear my case is more specific. I’m creating lines on the fly using the mouse in my game, like this:

enter image description here

And I think that a for loop would be quite slow for this.

Yeldham | 2018-02-17 14:02

My answer still works if you draw lines like this, you would just need to run it when you add points. However you didn’t specify how you created your line, so I provided a generic example :slight_smile: (note that the second for is faster due to pair checking).

If you draw your line this way, you can simplify the code a bit so it doesn’t have to do a double-for loop:
You would basically do one for loop, and check if existing segments intersect with the one you are about to place.
That shouldn’t be too slow for what you show in your gif, but as always there will be a performance limit with too many lines :slight_smile:
Otherwise you can try with the collision approach, which has other restrictions though (such as taking into account that collision shapes can be detected only the frame after they were added).

Zylann | 2018-02-17 14:36

I see. But which do you think it would be faster, via collision or the loop?

Yeldham | 2018-02-17 15:58

Fastest is probably the collision approach (not easier, just faster to execute). Also it depends what you do later with your line, if you want to erase it for example, you will need to keep collision shapes in sync.

Zylann | 2018-02-17 16:08

Zylann, I tried your get_segment_intersection function, but it doesn’t seem to work, I did a small test, but it seems to always return null:

get_segment_intersection(Vector2(0, 0), Vector2(100, 100),
		Vector2(-100, 0), Vector2(0, -100))

Yeldham | 2018-02-17 21:14

The two segments you gave to the function are not intersecting.

Zylann | 2018-02-17 21:16

Yep, now I noticed that. Sometimes even simple vector math goes right through my head, not too used to it.

Thanks for the patience.

Yeldham | 2018-02-17 21:45

:bust_in_silhouette: Reply From: pwab

Thanks @Zylann for the mathematical approach. I wasn’t able to think of it myself so I implemented an approach which is based on SegmentShape2D-CollisionShapes (to know if there is an overlapping) and RayCast2Ds (to know where it happens).

Just create a new project and add a Node2D as root. This node gets the world.gd-script. The other line.gd script should be copied inside the folder next to the world.gd-script. That’s it. Start the app and draw your lines.

The code has the drawback of detecting intersections with other lines but I put some comments about that topic at the top of the line.gd script.

Here are the code files:

world.gd

# For this implementation you will need to activate emulate_touchscreen
# See Project Settings -> Display -> Window -> Handheld -> emulate_touchscreen
#
# (I wanted to do it with:
#	ProjectSettings.set_setting("display/window/handheld/emulate_touchscreen", true)
#  but it did not work...)

extends Node2D

var active_line
var line_script = preload("res://line.gd")

func _input(event):
	# Touch/Mouse Button
	if event is InputEventMouseButton:
		# Button down
		if event.is_pressed():
			# Create new line
			active_line = Line2D.new()
			active_line.position = event.position
			active_line.points = [Vector2(0,0)]
			active_line.default_color = Color(randf(), randf(), randf(), 1)
			add_child(active_line)
		
		# Button up
		else:
			# Let's do the magic
			active_line.set_script(line_script)
			active_line.add_collision_areas()
			
	if event is InputEventScreenDrag:
		# Add some more points to the line when dragging
		var points = active_line.points
		points.append(event.position - active_line.position)
		active_line.points = points

line.gd

# This implementation is based on CollisionShapes and RayCasts.
# It has one major flaw: It detects intersections of different lines and not only of the line itself.
# I'm pretty sure this can be circumvented by changing the collision_layers of each line
# or by keeping track of each line and then excluding their collision_bodies when ray casting
# or by removing all the collision bodies when intersection_scanning is done

extends Line2D

var intersections = []  # Keep track of every intersection
var segments = []  # Keep track of every segment
var collision_shapes = []  # Just a hack to keep the included information of the segment-shapes
	
func _ready():
	# If the script is attached on a line created in the editor
	add_collision_areas()

func add_collision_areas():
	# The line is devided into segments
	for i in range(points.size()-1):
		var segment = create_segment(points[i], points[i+1], i)
		segments.append(segment)
		add_child(segment)
		# The areas shape_entered signal is used to get the information that it collides with something
		segment.connect("area_shape_entered", self, "_on_segment_area_shape_entered")

func create_segment(from, to, name=""):
	var segment = Area2D.new()
	# The naming is optional but looks cleaner in the remote inspector
	segment.name = "segment" + str(name)
	segment.position = from
	
	var collision = CollisionShape2D.new()
	collision.shape = SegmentShape2D.new()
	# Local positions (relative to shapes origin)
	collision.shape.a = Vector2(0,0)
	collision.shape.b = to - from
	
	segment.add_child(collision)
	# We want to keep track of the collision_shapes for later use (just a hack)
	collision_shapes.append(collision)
	return segment

func _draw():
	# Draw the starting points of each segment
	for segment in get_children():
		draw_circle(segment.position, 3, ColorN("Black", 0.5))
	
	# Draw the intersection points if there are any
	for intersection in intersections:
		draw_circle(intersection[2], 7, ColorN("Red", 1))

func _on_segment_area_shape_entered(segment_id, segment, segment_shape, self_shape):
	# This is the heart of the script
	var overlapping_segments = segment.get_overlapping_areas()
	
	# Define the segments neighbours (previous and next segment)
	# This could be refactored with a linked-list...
	var segment_number = segments.find(segment)
	var neighbour_segments = []
	if segment_number == 0:
		# The first segment only has one neigbour: the next one
		neighbour_segments = [segments[segment_number + 1]]
	elif segment_number == segments.size()-1:
		# The last segment only has one neigbour: the previous one
		neighbour_segments = [segments[segment_number - 1]]
	else:
		neighbour_segments = [segments[segment_number - 1], segments[segment_number + 1]]
	
	for overlapping_segment in overlapping_segments:
		# Neighbour segments have nothing to do with the intersection
		if not overlapping_segment in neighbour_segments:
			# We have a real overlapping here!			
			# Now shoot a ray to get the intersection point
			var ray = RayCast2D.new()
			# Exclude the segment itself (the one which is overlapped)
			ray.exclude_parent = true
			# Exclude the neighbours
			for neighbour_segment in neighbour_segments:
				ray.add_exception(neighbour_segment)
			# Send the raycast along the segments length
			# Here we need our little shapes hack...
			ray.cast_to = collision_shapes[segment_number].shape.b
			# And here we go: pew pew
			segment.add_child(ray)
			ray.enabled = true
			
			var intersection_point
			var intersection_point_found = false
			# This sound funny at first but we have to do this if there are multiple
			# intersections on one line. We have to be sure to get the right one.
			while not intersection_point_found:
				# The raycast should be updated immediately
				ray.force_raycast_update()
				var collider = ray.get_collider()
				# A straight line has no collisions
				if ray.is_colliding():
					if collider != overlapping_segment:
						# Here we remove the segments which overlap the line but
						# aren't interesting for us right now.
						ray.add_exception(collider)
					else:
						# RayCast point positions are global
						intersection_point = to_local(ray.get_collision_point())
						intersection_point_found = true
						
						# Organise the intersections
						var intersection = [segment, overlapping_segment, intersection_point]
						if not intersection in intersections:
							intersections.append(intersection)
							update()
				else:
					# Prevent endless loop
					break
			
			# We don't need the raycast anymore
			ray.queue_free()

PS:
I uploaded everything to a gist if you prefer reading the code with githubs syntax highlighting.