Attention | Topic was automatically imported from the old Question2Answer platform. | |
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:
Attention | Topic was automatically imported from the old Question2Answer platform. | |
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:
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:
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 (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).
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
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.