Intersecting Links Example

1 collaborator

Uri Wilensky (Author)

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.

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

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
  ]
  ask endpoints
  [
    hatch-endpoints 1
    [
      setxy random-xcor random-ycor
      create-link-with myself
    ]
  ]
  place-markers
  reset-ticks
end 

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

to place-markers
  ask markers [ die ]
  ;; each pair of segments checks for intersections once
  ask links [
    ;; performing this check on the who numbers keeps
    ;; us from checking every pair twice
    ask links with [self > myself] [
      let result intersection self myself
      if not empty? result [
        ask end1 [
          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]
  let m1 [tan (90 - link-heading)] of t1
  let m2 [tan (90 - link-heading)] of 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)
      let c1 [link-ycor - link-xcor * m1] of t1
      ;; t2 is vertical so we know x already
      let x [link-xcor] of t2
      ;; 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)
  let c1 [link-ycor - link-xcor * m1] of t1
  let c2 [link-ycor - link-xcor * m2] of t2
  ;; 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
  report abs (link-xcor - x) <= abs (link-length / 2 * sin link-heading)
end 

to-report y-within? [y]  ;; turtle procedure
  report abs (link-ycor - y) <= abs (link-length / 2 * cos link-heading)
end 

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

to-report link-ycor
  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.

Uploaded by	When	Description	Download
Uri Wilensky	over 11 years ago	Updated to NetLogo 5.0.4	Download this version
Uri Wilensky	about 12 years ago	Updated version tag	Download this version
Uri Wilensky	almost 13 years ago	Updated to NetLogo 5.0	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Model from NetLogo distribution	Download this version
Uri Wilensky	over 14 years ago	Intersecting Links Example	Download this version
Uri Wilensky	over 14 years ago	Intersecting Links Example	Download this version

Attached files

File	Type	Description	Last updated
Intersecting Links Example.png	preview	Preview for 'Intersecting Links Example'	over 11 years ago, by Uri Wilensky	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo