 ### 1 collaborator Uri Wilensky (Author)

### Tags

code example

Tagged by Reuven M. Lerner over 9 years ago

Model group CCL | Visible to everyone | Changeable by group members (CCL)
Model was written in NetLogo 5.0.4 • Viewed 692 times • Downloaded 47 times • Run 3 times Download this modelEmbed this model

## WHAT IS IT?

This code example shows how to determine if two links intersect.

## HOW IT WORKS

The work is done in the procedure called `intersection`. First the code computes the intersection point of the lines containing the segments between the two nodes of the link, then checks to see if that intersection point is actually within both segments. (The second check is easy to do because we already know the intersection point is on the lines, so we only need to check that the point's x coordinate.) If two segments have the same slope, no intersections are marked.

Since slope is undefined for vertical lines, special case code is used if either of the segments is vertical.

## THINGS TO NOTICE

The `intersection` procedure computes m and c for both segments every time it is called. This is wasteful if we are checking every turtle against every other turtle looking for intersections. To speed up the model, make m and c link variables instead and compute them for all segments before checking for any intersections.

The math assumes that the links don't extend beyond the edges of the world. If you need to intersect turtles which go off the edges of the world, you'll need to add extra code.

## RELATED MODELS

• Code Examples -> Intersecting Lines Example: same as this example, but for line turtles instead of links
• Games -> Planarity: has shorter code for determining whether two line segments intersect, without bothering to compute the location of the intersection point

## CREDITS AND REFERENCES

To keep the math relatively simple, the code represents lines in slope-intercept form (y=mx+c); see http://mathworld.wolfram.com/Slope.html.

Thanks to Gagandeep Singh for his work on this example.

Click to Run Model

```breed [ markers marker ]
breed [ endpoints endpoint ]

to setup
clear-all
set-default-shape markers "circle"
create-endpoints 9
[
setxy random-xcor random-ycor
]
[
hatch-endpoints 1
[
setxy random-xcor random-ycor
]
]
place-markers
reset-ticks
end

to go
ask endpoints [ rt random-float .5 fd 0.01 ]
place-markers
tick
end

to place-markers
;; each pair of segments checks for intersections once
;; performing this check on the who numbers keeps
;; us from checking every pair twice
let result intersection self myself
if not empty? result [
hatch-markers 1 [
set color gray
set size 1
setxy (first result) (last result)
]
]
]
]
]
end

;; reports a two-item list of x and y coordinates, or an empty
;; list if no intersection is found

to-report intersection [t1 t2]
;; treat parallel/collinear lines as non-intersecting
if m1 = m2 [ report [] ]
;; is t1 vertical? if so, swap the two turtles
if abs m1 = tan 90
[
ifelse abs m2 = tan 90
[ report [] ]
[ report intersection t2 t1 ]
]
;; is t2 vertical? if so, handle specially
if abs m2 = tan 90 [
;; represent t1 line in slope-intercept form (y=mx+c)
;; t2 is vertical so we know x already
;; solve for y
let y m1 * x + c1
;; check if intersection point lies on both segments
if not [x-within? x] of t1 [ report [] ]
if not [y-within? y] of t2 [ report [] ]
report list x y
]
;; now handle the normal case where neither turtle is vertical;
;; start by representing lines in slope-intercept form (y=mx+c)
;; now solve for x
let x (c2 - c1) / (m1 - m2)
;; check if intersection point lies on both segments
if not [x-within? x] of t1 [ report [] ]
if not [x-within? x] of t2 [ report [] ]
report list x (m1 * x + c1)
end

to-report x-within? [x]  ;; turtle procedure
end

to-report y-within? [y]  ;; turtle procedure
end

report ([xcor] of end1 + [xcor] of end2) / 2
end

report ([ycor] of end1 + [ycor] of end2) / 2
end

; Public Domain:
; To the extent possible under law, Uri Wilensky has waived all
; copyright and related or neighboring rights to this model.
```

There are 10 versions of this model.

Uri Wilensky over 9 years ago Updated to NetLogo 5.0.4 Download this version
Uri Wilensky almost 10 years ago Updated version tag Download this version
Uri Wilensky over 10 years ago Updated to NetLogo 5.0 Download this version