Triangle minimum enclosing disk solution

Triangle minimum enclosing disk solution preview image

1 collaborator

Eugene_martin Eugene Martin (Author)

Tags

geometry 

"line intersection"

Tagged by Eugene Martin about 3 years ago

gis 

"vector line intersect"

Tagged by Eugene Martin about 3 years ago

Visible to everyone | Changeable by the author
Model was written in NetLogo 5.3.1 • Viewed 170 times • Downloaded 14 times • Run 0 times
Download the 'Triangle minimum enclosing disk solution' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


Comments and Questions

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

Click to Run Model

turtles-own [name]
globals [Ix Iy radius ExtList wholist step pos slopes intercepts Ax Ay Bx By Cx Cy ABx ABy ABm ABb BCx BCy BCm BCb CAx CAy CAm CAb midx midy]

to doit
  if step = 0 [triangle]
  if step = 1 [midpoints]
  if step = 2 [bisect]
  if step = 3 [bi_intersect]
  set step step + 1
  if step > 4 [set step 0 ca clear-output]
end 

to triangle
  ;make color set
  set pos 0
  ;make points
  foreach ["A" "B" "C"][
     crt 1 [set shape "square" set size 2 set color 48 set name ? set label name set heading random 360 jump (10 + random 10 + (random 100) / 100)]
  ]
  set wholist []
  ask turtles[set wholist lput who wholist]
  set wholist sort wholist
  set pos 0
  repeat (length wholist - 1) [
   set pos pos + 1
   ask turtle (item pos wholist) [create-link-with turtle (item (pos - 1) wholist)]]
  ask turtle (last wholist) [create-link-with turtle (first wholist)]
  ask links [set thickness 0.5 set color 5]
end 

to midpoints
  set Ax [xcor] of one-of turtles with [name = "A"]
  set Ay [ycor] of one-of turtles with [name = "A"]
  set Bx [xcor] of one-of turtles with [name = "B"]
  set By [ycor] of one-of turtles with [name = "B"]
  set Cx [xcor] of one-of turtles with [name = "C"]
  set Cy [ycor] of one-of turtles with [name = "C"]
  set ABx first midpoint Ax Ay Bx By
  set ABy last midpoint Ax Ay Bx By
  crt 1 [set name "AB" set label name setxy ABx ABy set shape "triangle" set color yellow]
  set BCx first midpoint Bx By Cx Cy
  set BCy last midpoint Bx By Cx Cy
  crt 1 [set name "BC" set label name setxy BCx BCy set shape "triangle" set color yellow]
  set CAx first midpoint Cx Cy Ax Ay
  set CAy last midpoint Cx Cy Ax Ay
  crt 1 [set name "CA" set label name setxy CAx CAy set shape "triangle" set color yellow]
end 

to bisect
  set ABm -1 / (slope Ax Ay Bx By)
  set ABb intercept ABx ABy ABm
  set BCm -1 / (slope Bx By Cx Cy)
  set BCb intercept BCx BCy BCm
  set CAm -1 / (slope Cx Cy Ax Ay)
  set CAb intercept CAx CAy CAm
  ;draw them
  ;find the intercept with the world-height and world-width?
  ;extend the lines

  let scale 0.95
  set ExtList []
  ;set the x to the world left edge and see of the y value is within the range of the height.  If so keep the coordinates
  carefully [if abs ((ABm * ((world-width * scale) / -2.0)) + ABb) < ((world-height * scale) / 2) [set ExtList lput (list ((world-width * scale) / -2.0) ((ABm * ((world-width * scale) / -2.0)) + ABb))  ExtList]][]
  carefully [if abs ((ABm * ((world-width * scale) / 2.0)) + ABb) < ((world-height * scale) / 2) [set ExtList lput (list ((world-width * scale) / 2.0) ((ABm * ((world-width * scale) / 2.0)) + ABb))  ExtList]][]
  carefully [if abs ((((world-height * scale) / 2.0) - ABb) / ABm) < ((world-width * scale) / 2) [set ExtList lput (list ((((world-height * scale) / 2.0) - ABb) / ABm) ((world-height * scale) / 2.0))  ExtList]][]
  carefully [if abs ((((world-height * scale) / -2.0) - ABb) / ABm) < ((world-width * scale) / 2) [set ExtList lput (list ((((world-height * scale) / -2.0) - ABb) / ABm) ((world-height * scale) / -2.0))  ExtList]][]
  carefully [create-turtles 1 [set name "AB1" set xcor first first ExtList set ycor last first ExtList set color white set shape "dot"]][]
  carefully [create-turtles 1 [set name "AB2" set xcor first last ExtList set ycor last last ExtList set color white set shape "dot"]][]
  carefully [ask one-of turtles with [name = "AB1"] [create-link-with one-of turtles with [name = "AB2"]]][]
  carefully[ask link ([who] of one-of turtles with [name = "AB1"]) ([who] of one-of turtles with [name = "AB2"]) [set thickness 0.2 set color red]][]
  set ExtList []
  carefully [if abs ((BCm * ((world-width * scale) / -2.0)) + BCb) < ((world-height * scale) / 2) [set ExtList lput (list ((world-width * scale) / -2.0) ((BCm * ((world-width * scale) / -2.0)) + BCb))  ExtList]][]
  carefully [if abs ((BCm * ((world-width * scale) / 2.0)) + BCb) < ((world-height * scale) / 2) [set ExtList lput (list ((world-width * scale) / 2.0) ((BCm * ((world-width * scale) / 2.0)) + BCb))  ExtList]][]
  carefully [if abs ((((world-height * scale) / 2.0) - BCb) / BCm) < ((world-width * scale) / 2) [set ExtList lput (list ((((world-height * scale) / 2.0) - BCb) / BCm) ((world-height * scale) / 2.0))  ExtList]][]
  carefully [if abs ((((world-height * scale) / -2.0) - BCb) / BCm) < ((world-width * scale) / 2) [set ExtList lput (list ((((world-height * scale) / -2.0) - BCb) / BCm) ((world-height * scale) / -2.0))  ExtList]][]
  carefully [create-turtles 1 [set name "BC1" set xcor first first ExtList set ycor last first ExtList set color white set shape "dot"]][]
  carefully [create-turtles 1 [set name "BC2" set xcor first last ExtList set ycor last last ExtList set color white set shape "dot"]][]
  carefully [ask one-of turtles with [name = "BC1"] [create-link-with one-of turtles with [name = "BC2"]]][]
  carefully[ask link ([who] of one-of turtles with [name = "BC1"]) ([who] of one-of turtles with [name = "BC2"]) [set thickness 0.2 set color red]][]
  set ExtList []
  carefully [if abs ((CAm * ((world-width * scale) / -2.0)) + CAb) < ((world-height * scale) / 2) [set ExtList lput (list ((world-width * scale) / -2.0) ((CAm * ((world-width * scale) / -2.0)) + CAb))  ExtList]][]
  carefully [if abs ((CAm * ((world-width * scale) / 2.0)) + CAb) < ((world-height * scale) / 2) [set ExtList lput (list ((world-width * scale) / 2.0) ((CAm * ((world-width * scale) / 2.0)) + CAb))  ExtList]][]
  carefully [if abs ((((world-height * scale) / 2.0) - CAb) / CAm) < ((world-width * scale) / 2) [set ExtList lput (list ((((world-height * scale) / 2.0) - CAb) / CAm) ((world-height * scale) / 2.0))  ExtList]][]
  carefully [if abs ((((world-height * scale) / -2.0) - CAb) / CAm) < ((world-width * scale) / 2) [set ExtList lput (list ((((world-height * scale) / -2.0) - CAb) / CAm) ((world-height * scale) / -2.0))  ExtList]][]
  ;show ExtList
  carefully [create-turtles 1 [set name "CA1" set xcor first first ExtList set ycor last first ExtList set color white set shape "dot"]][]
  carefully [create-turtles 1 [set name "CA2" set xcor first last ExtList set ycor last last ExtList set color white set shape "dot"]][]
  carefully [ask one-of turtles with [name = "CA1"] [create-link-with one-of turtles with [name = "CA2"]]][]
  carefully[ask link ([who] of one-of turtles with [name = "CA1"]) ([who] of one-of turtles with [name = "CA2"]) [set thickness 0.2 set color red]][]
end 

to bi_intersect
  set Ix ((ABb - BCb) / (BCm - ABm))
  set Iy (ABm * Ix + ABb)
  ifelse abs Ix < world-width / 2 and abs Iy < world-height / 2
     [
     set radius (((Ix - Ax) ^ 2) + ((Iy - Ay) ^ 2)) ^ 0.5
     set pos 0
     carefully[
       repeat 179 [
         set pos pos + 2
         crt 1 [set name "circle" setxy Ix Iy set size 3 set shape "dot" set color white set size 1 set heading pos]
         ]
     ]
     []
     ][show "outside of view"]
     ask turtles with [name = "circle"] [carefully[jump radius set shape "line" set heading heading + 90][die]]
end 

to-report slope [x1 y1 x2 y2]
  report ((y1 - y2) / (x1 - x2))
end 

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

to-report midpoint [px py qx qy]
  set midx ((px + qx) / 2)
  set midy ((py + qy) / 2)
  ;show (list px py qx qy midx midy)
  report (list midx midy)
end 

There are 2 versions of this model.

Uploaded by When Description Download
Eugene Martin about 3 years ago manual alternative to layout-circle Download this version
Eugene Martin about 3 years ago Initial upload Download this version

Attached files

File Type Description Last updated
Triangle minimum enclosing disk solution.png preview Preview for 'Triangle minimum enclosing disk solution' about 3 years ago, by Eugene Martin Download

This model does not have any ancestors.

This model does not have any descendants.