Building a minimal spanning tree using java TreeMap

Question

I am working on a project that requires me to track the number of points on a 2d plane. I need to add functionality that allows certain points to detect the proximity of other points. I immediately thought about the immediate problem of the pair and thought that maybe I need to build a minimal spanning tree.

The first problem is that these points are constantly updating their coordinates, and I was wondering if it would even be believable to do this.

Another problem is that I cannot use third-party libraries for this, so there is no jgraph or jung. I was wondering if there is a way to build a minimum reach using only the libraries that gave me. Can I use TreeMap or will I need to do this from scratch?

Answer 1

It looks like you are trying to fulfill Nearest Neighbor queries. This is where you try to find the point (or points) closest to another point. For a naive solution, you can simply save the list of points and drag them through the distance formula to find out which ones are closest. But if you want to execute queries faster, you will need to use a spatial data structure that allows you to perform such queries. I would suggest the KD tree. Java does not come with an implementation of KD Tree in its standard library, so you need to implement this yourself.

TreeMap is just an implementation of the Map interface, which allows you to add and retrieve values ​​by their keys. If you want to write something to create a minimal spanning tree, you will need to do it yourself.

Answer 2

In the object-oriented way of executing this object, Point use the Observer Pattern and register as observers of all the other points, and then, when the positions of the points are points, they can update all the observers that they changed. You can control thresholds for how often changes have occurred or how much this has changed before notifications were sent to Observers. This will work well, as you said that “specific” points should track proximity and not all.