Finding the mean point in tiling space?

Question

I have a collection of points in tiling 2D space (I believe its called toroidal geometry/space), and I want to find their mean:

The basic approach would be to just take their mean 'locally' where you would just treat the space as non-tiling. Looking at the example, I'd guess that that would be somewhere in about the middle. However, looking at the extended example, I'd say that the middle is probably one of the worst representations of the data.

I'd say the objective is to find a location where the total variation from the mean is at a minimum

One potential method would be to try all combinations of points in each of the 9 neighbours, and then see which one has the lowest variance, but that becomes extremely inefficient very quickly: Big O = O(8^n) I believe it could probably be made more efficient by doing something like treating the x and y independently, but that would only reduce it to O(5^n), so still not manageable.

Perhaps hill-climbing might work? Where I have a random point, and then calculate the lowest possible variance for each point, then make some random adjustments and test again reverting if the variance decreases, I then repeat this until I reach a seemingly optimal value.

Is there a better method? Or maybe some sort of heuristic 'good enough' method?

Answer 1

as of my understanding, you are trying to find the center of mass. to do so (for each tile) you have to find the sum of each positions multiplied by its weight (assume it is 1 because they are just identical points positioned differently) then divide this by the sum of the weights (which is the number of points in this example as weight = 1). The formula

<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS_HTML-full"></script> <script type="text/x-mathjax-config"> MathJax.Hub.Config({"HTML-CSS": { preferredFont: "TeX", availableFonts:["STIX","TeX"], linebreaks: { automatic:true }, EqnChunk:(MathJax.Hub.Browser.isMobile ? 10 : 50) }, tex2jax: { inlineMath: [ ["$", "$"], ["\\\\(","\\\\)"] ], displayMath: [ ["$$","$$"], ["\\[", "\\]"] ], processEscapes: true, ignoreClass: "tex2jax_ignore|dno" }, TeX: { noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } }, Macros: { href: "{}" } }, messageStyle: "none" });   </script>

$$G\left( x,y \right) =\frac{\sum_{i=1}^n{m_i\cdot p_i\left( x_i\,\,,y_i \right)}}{\sum_{i=1}^n{m_i}}$$

in our example:

<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS_HTML-full"></script> <script type="text/x-mathjax-config"> MathJax.Hub.Config({"HTML-CSS": { preferredFont: "TeX", availableFonts:["STIX","TeX"], linebreaks: { automatic:true }, EqnChunk:(MathJax.Hub.Browser.isMobile ? 10 : 50) }, tex2jax: { inlineMath: [ ["$", "$"], ["\\\\(","\\\\)"] ], displayMath: [ ["$$","$$"], ["\\[", "\\]"] ], processEscapes: true, ignoreClass: "tex2jax_ignore|dno" }, TeX: { noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } }, Macros: { href: "{}" } }, messageStyle: "none" });   </script>

$$G\left( x,y \right) =\frac{\sum_{i=1}^n{p_i\left( x_i\,\,,y_i \right)}}{n}$$

here is a python implementation :

#assuming l is a list of 2D tuples as follow: [(x1,y1),(x2,y2),...]

def findCenter(l):
    cx,cy = 0,0
    for p in l:
        cx += p[0]
        cy += p[1]
    return (cx / len(l), cy / len(l))

    # the result is a tuple of non-integer, if you need
    # an integer result use: return (cx // len(l),cy // len(l))
    # remove the outer parenthesis to take result as 2 separate values 

as for multiple tiles you can calculate the center for each tile then the center for the centers, or treat all points from multiple tiles as points from one big tile and calculate the center of all of them.