Quick hull demo

turtles-own [name link_to alt closed inside cone]

globals [waiter sectors sector who0a who1a who2a who3a above to_who Aline Bline hlist online below thisintercept answer newcorner up youwho Im Ib Ax1 Ay1 Ax2 Ay2 Bx1 By1 Bx2 By2 Bm Bb Am Ab reset x3 y3 x4 y4 thisslope Ix Iy radius ExtList wholist step pos Ax Ay Bx By Cx Cy ABx ABy ABm ABb BCx BCy BCm BCb CAx CAy CAm CAb]
patches-own [pinside]
links-own [state]

to makepoints
  ;make color set
  ca
  reset-ticks
  ask patches [set pcolor 7]
  clear-output
  ;show "==========="
  ;show "    "
  ;show "New hull...."
  set pos 0
  ;make points
  set sectors []
  repeat 4  [set sectors lput (list (one-of [-3 -2 -1 1 2 3] * (world-width / 8)) (one-of [-3 -2 -1 1 2 3] * (world-height / 8))) sectors]
  ;show sectors
  set hlist []
  repeat points [  ;(10 + random 30) [
    set hlist lput random 360 hlist
  ]
  set hlist sort hlist
  ;show hlist
  foreach hlist [
    set sector one-of sectors
    crt 1 [setxy first sector last sector set shape "square" set closed false set size 2 set name "point" set heading ? jump ((random (world-width / 4)) + (random 100) / 100) ]
  ]
  ask turtles [set link_to -1]
  ask min-one-of turtles [xcor] [set name "corner" set shape "star" set color grey set link_to [who] of max-one-of turtles [xcor] create-link-to max-one-of turtles [xcor]]
  ask max-one-of turtles [xcor] [set name "corner" set shape "star" set color grey set link_to [who] of min-one-of turtles [xcor] create-link-to min-one-of turtles [xcor]]
  ;ask turtles with [name = "corner"][show (se "link_to" link_to)]
  ;;showlinks
end 

to hull
  if count links with [state != "done"] != 0[
   carefully [tick][reset-ticks]
   display
   ask links [
    ask both-ends[set name "corner" set closed true set color violet ]
    do_altitude
    ifelse count turtles with [name = "point" and closed = false and alt >= 0] > 0     ;   are there any potential corner turtles
        [set color violet set thickness 0.5
         display
         set newcorner [who] of max-one-of turtles with [name = "point" and closed = false and alt >= 0][alt]
           ask end1 [create-link-to turtle newcorner [set color 23 set thickness 0.5 set state "new"]]
           display
           ask end2 [create-link-from turtle newcorner [set color 23 set thickness 0.5 set state "new"]]
           display
           ask links [ask both-ends [set name "corner"]]
           ask turtles with [name = "point" and closed = false][set inside 0]
           close-triangle newcorner
           ask both-ends [set closed true set color red
           display]
          die]
        [set state "done" set color green set thickness 1 ask both-ends [set color red set closed true display]]
      ]

   ask links with [state = "done"][set color green]
   tick
   display
   ]
  ask patches [set pcolor 7]
end 

to whole_hull
  while [ count links with [state != "done"] > 0][
   carefully [tick][reset-ticks]
   display
   ask links [
    ask both-ends[set name "corner" set closed true set color violet ]
    do_altitude
    ifelse count turtles with [name = "point" and closed = false and alt >= 0] > 0     ;   are there any potential corner turtles
        [set color violet set thickness 0.5
         display
         set newcorner [who] of max-one-of turtles with [name = "point" and closed = false and alt >= 0][alt]
           ask end1 [create-link-to turtle newcorner [set color 23 set thickness 0.5 set state "new"]]
           display
           ask end2 [create-link-from turtle newcorner [set color 23 set thickness 0.5 set state "new"]]
           display
           ask links [ask both-ends [set name "corner"]]
           ask turtles with [name = "point" and closed = false][set inside 0]
           close-triangle newcorner
           ask both-ends [set closed true set color red
           display]
          die]
        [set state "done" set color green set thickness 1 ask both-ends [set color red set closed true display]]
      ]

   ask links with [state = "done"][set color green]
   tick
   display
   ]
  ask patches [set pcolor 7]
end 

to do_altitude  ;point to line distance.  who1 and [link_to] of turtle who1 are the line.  who2 is the point being evaluated
    ;;show (se "p2l_dist" who1 who2 who3);input point coordinates
    ;p1 p2 is the line and p3 is the point to measure
    set Ax1 [xcor] of end1
    set Ay1 [ycor] of end1
    set Ax2 [xcor] of end2
    set Ay2 [ycor] of end2
    ask turtles with [name = "point" and closed = false]
      [
      set alt -1
      set Bx1 xcor
      set By1 ycor
      ifelse Ax1 = Ax2
        [set Ix Ax1 set Iy By1 set alt abs (Ax1 - Bx1)]
        [set Am (Ay1 - Ay2) / (Ax1 - Ax2)
         set Ab Ay1 - (Am * Ax1)
         ;'B' bisector slope and intercept
         set Bm -1 / Am  ;use the original slope to get the slope at right angle
         set Bb By1 - (Bm * Bx1) ;get the y intercept
         set Bx2 0
         set By2 Bb
         ;solve for point intersection at right angle
         set Ix (( Bb - Ab) / (Bm - Am)) * -1
         set Iy Bm * Ix + Bb
         ;check that Ix,Iy is on the segment
         set online false
         if (Ix <= Ax1 and Ix >= Ax2) or (Ix >= Ax1 and Ix <= Ax2) and (Iy <= Ay1 and Iy >= Ay2) or (Iy >= Ay1 and Iy <= Ay2) [set online true]
         ;report the distance
         set alt pntdist Bx1 By1 Ix Iy]
      ifelse By1 > Iy
        [set up true]
        [set up false]
      if Ax1 < Ax2 and (not up or not online) [set alt -1] ; the point is above the line and intersects perpendicular so it needs to be evaluated
      if Ax1 > Ax2 and (up or not online) [set alt -1] ; the point is below the line and intersects perpendicular so it needs to be evaluated
      ]
end 

to close-triangle [who2]  ; called by a link, who3 is the third corner of the triangle
  set who0a [who] of end1
  set who1a [who] of end2
  ;show (se "both-end who numbers:" who0a who1a )
  ;show (se "count closed = false" count turtles with [name = "point" and closed = false])
  ;align the turtles to define a triangle area
  ask turtle who0a [set shape "default" set size 3 set heading meanangle (towards turtle who1a) (towards turtle who2) set cone abs (subtract-headings towards turtle who1a towards turtle who2)]
  ask turtle who1a [set shape "default" set size 3 set heading meanangle (towards turtle who0a) (towards turtle who2) set cone abs (subtract-headings towards turtle who0a towards turtle who2)]
  ask turtle who2 [set shape "default" set size 3 set heading meanangle (towards turtle who1a) (towards turtle who0a) set cone abs (subtract-headings towards turtle who1a towards turtle who0a)]
  ;highlight the turtles in the target triangle - consumes processing time
  display
  ask patches with [pinside > 0][set pinside 0 set pcolor 7]
  ask turtle who0a [ask patches in-cone (world-width * 2) cone [set pinside pinside + 1]]
  ask turtle who1a [ask patches in-cone (world-width * 2) cone [set pinside pinside + 1]]
  ask turtle who2 [ask patches in-cone (world-width * 2) cone [set pinside pinside + 1]]
  ask patches with [pinside = 3][set pcolor yellow]
  display
  ;compare each turtle relative to the cones of the triangle corners
  ask turtles with [name = "point" and closed = false] [set inside 0]
  ask turtle who0a [ask turtles with [name = "point" and closed = false] in-cone (world-width * 2) cone [set inside inside + 1]]
  ask turtle who1a [ask turtles with [name = "point" and closed = false] in-cone (world-width * 2) cone [set inside inside + 1]]
  ask turtle who2 [ask turtles with [name = "point" and closed = false] in-cone (world-width * 2) cone [set inside inside + 1]]
  ;show (list "closed false points" [who] of turtles with [name = "point" and closed = false and inside = 3])
  ask turtles with [name = "point" and closed = false and inside = 3][set closed true set color black] ;show (se "just closed" who)]
  display
end 

to-report slope [x1 y1 x2 y2]
  carefully [set thisslope ((y1 - y2) / (x1 - x2))]
     [set thisslope 10000000000000]
  report thisslope
end 

to-report intercept [x y m]
  report (y - (m * x))
end 

to-report meanangle [a b]
  report atan ((sin a + sin b) / 2) ((cos a + cos b) / 2)
end 

to-report pntdist [x1 y1 x2 y2]
  report (((x1 - x2) ^ 2) + ((y1 - y2) ^ 2)) ^ 0.25
end