Mid point between turtles in a turtleset in a wrapping world

Question

I'm trying to find the mid-point between a set of turtles in a world that wraps, both along the x- and y-axis. The obvious solution is to

let mid-point list mean [xcor] turtles mean [ycor] turtles

but when the world wraps, this returns a result that isn't exactly what I'm looking for. I.e. if two turtles are at respectively [0 -25] and [0 23] in a 25 x 25 world, I would like to return [0 24] (or maybe [0 24.5]?). But the mean-approach returns [0 1]. Does anyone have a good suggestion for how to do this? One approach would be to find the patch that has the lowest sum of distances to the relevant turtles, but I'd prefer to find the exact point.

Does this make sense? Any suggestions?

Answer 1

I first misread the question and thought it was a matter of finding the midpoint between only two turtles, so I suggested this:

to setup
  clear-all
  resize-world -25 25 -25 25
  create-turtles 2
  ask turtle 0 [ setxy 0 -25 ]
  ask turtle 1 [ setxy 0 23 ]
  show midpoint turtle 0 turtle 1
end

to-report midpoint [ t1 t2 ]
  let result (list)
  ask t1 [
    hatch 1 [
      face t2
      forward distance t2 / 2
      set result list xcor ycor
      die
    ]
  ]
  report result
end

Provided world wrapping is turned on, running setup will print [0 24.5].

But Arthur pointed out that what he actually wanted was to find the midpoint for a whole set of turtles (i.e., a centroid). After a some thinking, I realized I could apply a very similar method:

• Create one temporary turtle for each one in the original set (I call them points);
• Make the first one of those a "seeker" turtle that will move around until it finds the centroid.
• Have the seeker move half-way to the first of the other points, then a third of the way to the second one, then a fourth of the way to the third one, etc., until there are no more points left.

Aside from intuition, I have no mathematical proof that this works, but when world wrapping is turned off, it does give the same result as the "mean coordinates" method, so I assume it also works with wrapping on. It also works for the [0 24.5] case. I'd be happy to get corrected if I'm mistaken, though.

Here it is:

to setup
  clear-all
  ask n-of (2 + random 10) patches [ sprout 1 ]

  ; Show centroid with the "seeker" method
  show centroid turtles

  ; Show centroid calculated with mean coordinates for comparison.
  ; If wrapping is on, it will probably be different from
  ; `centroid turtles`. If wrapping is off, it should be the
  ; same, with very small floating point variations:  
  show list mean [xcor] of turtles mean [ycor] of turtles  

end

to-report centroid [ set-of-turtles ]
  let points (list)
  ask set-of-turtles [
    hatch 1 [ set points lput self points ]
  ]
  report seek-centroid first points but-first points 2
end

to-report seek-centroid [ seeker points n ]
  if-else not empty? points [
    let target first points
    ask seeker [
      face target
      forward distance target / n
    ]
    ask target [ die ]
    report seek-centroid seeker but-first points (n + 1)
  ]
  [
    let result [ list xcor ycor ] of seeker
    ask seeker [ die ]
    report result
  ]
end

Note: adding ask first points [ pen-down ] before calling report seek-centroid ... is a fun way to get a feel for how the algorithm works.

Answer 2

Think of the 1D case with points in a unit interval. You can visualise this as points lying round a circle, and you want some sort of notion of average of the points. This comes under field of [Directional statistics] (https://en.wikipedia.org/wiki/Directional_statistics) and is a non-trivial thing to work with. One way might be to think of the circle as lying in the plane, take the average of these, calculate its angle giving a point on the circle and then a point on the circle.

Wikipedia mentions "A simple way to calculate the mean of a series of angles (in the interval [0°, 360°)) is to calculate the mean of the cosines and sines of each angle, and obtain the angle by calculating the inverse tangent." There is an article Mean of circular quantities which I think gives you the concept of mean your thinking of.

You could treat x and y separately. Calculating

let X-sin-mean mean [sin (xcor * 2 * pi /25)]
let X-cos-mean mean [cos (xcor * 2 * pi /25)]
let Y-sin-mean mean [sin (ycor * 2 * pi /25)]
let Y-cos-mean mean [cos (ycor * 2 * pi /25)]
let X-angle-mean [atan2 X-sin-mean X-cos-mean]
let Y-angle-mean [atan2 Y-sin-mean Y-cos-mean]
let X-mean (X-angle-mean * 25 / ( 2 * pi))
let Y-mean (Y-angle-mean * 25 / ( 2 * pi))

my netlogo syntax might be a bit faulty. I hope you get the gist.

Answer 3

To get the patch that contains the center point, you can do

min-one-of patches [ sum [ distance myself ] of turtles ]

Answer 4

A question on the mean heading of turtles got me thinking of another solution to this problem based on circular means. Basically, you can just take the circular mean of the x-coordinates and y-coordinates. Here's the code:

;; lower and upper should be equivalent on the circle, but upper > lower in the reals
;; For circles, lower = 0 and upper = 360.
;; For clocks, lower = 0 and upper = 12 (or 24)
;; For x-coordinates, lower = min-pxcor - .5 and upper = max-pxcor + .5
to-report circular-mean [ lower upper vals ]
  let width upper - lower
  let angles map [ 360 * (? - lower) / width ] vals
  let mean-x mean map [ cos ? ] angles
  let mean-y mean map [ sin ? ] angles

  ; not doing turtle headings here, so we flip atan's arguments
  report width * (atan mean-y mean-x) / 360 + lower
end

to-report mean-xcor [ xs ]
  report (circular-mean (min-pxcor - .5) (max-pxcor + .5) xs)
end

to-report mean-ycor [ ys ]
  report (circular-mean (min-pycor - .5) (max-pycor + .5) ys)
end

This really treats the two dimensions as circular. If you think of a dimension as a circle, this finds the point on that circle that has the smallest square distance to all the other points, where distance here is the euclidean distance between the points, rather than the distance around the circle (which is what most of the answers have been using).

Answer 5

This SO question has several answers that discuss both how hard this problem is and a few algorithms for solving it. Unfortunately, it is not trivial. The algorithms are all iterative (e.g. variations of gradient descent) and the solution space has many local optima.

"Center of Mass" between a set of points on a Toroidally-Wrapped Map that minimizes average distance to all points