0

I hope you have a nice day, so here is my problem: I'm trying to find the middle point of most populated positions (X/Y) on a map but i'm stuck and i can't find a good and effective way to do it.

To find this position i've access to an collection of entities (and these entities have a Position property (which is a Vector2D) and map size

public readonly struct Vector2D
{
    private static readonly double Sqrt = Math.Sqrt(2);
    private static readonly Random Random = new Random();
    
    public static Vector2D Zero { get; } = new Vector2D();
    
    public int X { get; }
    public int Y { get; }

    public Vector2D(int x, int y)
    {
        X = x;
        Y = y;
    }

    public Vector2D GetDistanceTo(Vector2D vector2D) => new Vector2D(Math.Abs(vector2D.X - X), Math.Abs(vector2D.Y - Y));

    public int GetDistance(Vector2D destination)
    {
        int x = Math.Abs(X - destination.X);
        int y = Math.Abs(Y - destination.Y);

        int min = Math.Min(x, y);
        int max = Math.Max(x, y);

        return (int)(min * Sqrt + max - min);
    }
    
    public bool IsInRange(Vector2D position, int range)
    {
        int dx = Math.Abs(X - position.X);
        int dy = Math.Abs(Y - position.Y);
        
        return dx <= range && dy <= range && dx + dy <= range + range / 2;
    }

    public override string ToString() => $"{X}/{Y}";
}

That's the only thing i've tried

public Vector2D FindMostPopulatedPosition()
{
    IEnumerable<Vector2D> positions = Entities.Select(x => x.Position);
    return new Vector2D((int)positions.Average(x => x.X), (int)positions.Average(x => x.Y));
}

Here is some example images

Red dot: All entities
Blue dot: The position i'm looking for

Example Example

Thanks for reading (and for your help)

Roxeez
  • 63
  • 4
  • Where are your positions saved, in an Array in a List? – IndieGameDev Jul 17 '20 at 10:01
  • 1
    what kind of structure are you using to represent this data? Please show some sample data, your relevant code so far including any attempts to solve the problem, and examples of expected results. This isn't a free write-my-code service, we expect a bit of effort to research and attempt to deal with the issue yourself first, and then we can help you along the way with some specific problem or query. Also we can't help you in any way at all without some proper sample data etc. Your screenshots are nice illustrations but they don't give us anything concrete to work with. – ADyson Jul 17 '20 at 10:03
  • 2
    Please define 'most populated area' – vc 74 Jul 17 '20 at 10:03
  • See also the [How To Ask](https://stackoverflow.com/help/how-to-ask) help page for more guidance on asking a useful, answerable question. Thanks. – ADyson Jul 17 '20 at 10:06
  • Once you [have algorithm](https://meta.stackexchange.com/q/165519/299295) we can help you with implementing it (you have to show attempt still). – Sinatr Jul 17 '20 at 10:16
  • @ADyson I know it's not a write-my-code service, i'm not even asking for code, just to help me with the algorithm part (since that's my only problem right now) as i said in my post i don't have any idea how can i do it so obviously i can't share anything interesting. Btw i've edited my post with some more information – Roxeez Jul 17 '20 at 10:49
  • 1
    This might help you, I hope: https://stackoverflow.com/questions/17112719/how-can-i-find-the-center-of-a-cluster-of-data-points . The scenario looks similar, from a brief skim of the text. There are code examples in various languages (although not C# unfortunately), but the algorithms are discussed in some depth as well. – ADyson Jul 17 '20 at 10:57
  • Please define "The center". I have an idea on how to find the most populated area, but I don't know what do you mean by "the center". –  Jul 17 '20 at 11:34
  • I would adapt this https://stackoverflow.com/a/21884021/2521214 ... creating the density map and finding biggest one then recursively increase precision around it ... – Spektre Jul 20 '20 at 07:13

0 Answers0