Efficient way of detecting if a line touched itself

Question

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:

Answer 1

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

Comments

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:

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

---

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

---

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

---

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

---

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

---

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

Thanks for the patience.

Answer 2

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.