построение минимального остовного дерева с использованием JavaMap TreeMap

Question

Я работаю над проектом, который требует, чтобы я отслеживал количество точек на 2-й плоскости.Мне нужно добавить функциональность, которая позволяет определенным точкам обнаруживать близость других точек.Я сразу подумал о проблеме ближайшей пары и подумал, что, возможно, мне следует построить минимальное остовное дерево.

Первая проблема заключается в том, что эти точки постоянно обновляют свои координаты, и мне было интересно, будет ли это возможно сделать.

Другая проблема в том, что я не могу использовать сторонние библиотеки для этого, поэтому нет jgraph или jung.Мне было интересно, есть ли способ построить минимальный охват, используя только библиотеки, которые мне дали.Можно ли использовать TreeMap или мне придется делать это с нуля?

Answer 1

На очень объектно-ориентированном способе это будет иметь Point Объекты, использующие Observer Pattern и регистрирующие себя в качестве наблюдателей всех других точек, тогда, когда положение точек изменяется, они могут обновить всех наблюдателей, которых они изменили. Вы можете контролировать пороги того, как часто происходили изменения или сколько изменений нужно было сделать, прежде чем уведомления были отправлены наблюдателям. Это хорошо сработало, поскольку вы сказали, что «определенные» точки должны отслеживать близость, а не все.

Answer 2

Похоже, вы пытаетесь выполнить Ближайший сосед запросов. Именно здесь вы пытаетесь найти точку (или точки), ближайшую к другой точке. Для наивного решения вы можете просто сохранить список точек и перебрать их, используя формулу расстояния, чтобы выяснить, какие из них ближе всего. Но если вы хотите выполнять запросы быстрее, вам нужно использовать пространственную структуру данных, которая разрешает подобные запросы. Я бы предложил KD Tree. Java не поставляется с реализацией KD Tree в своей стандартной библиотеке, поэтому вам нужно реализовать это самостоятельно.

TreeMap - это просто реализация интерфейса Map, который позволяет вводить и извлекать значения по их ключам. Если вы хотите написать что-то для создания минимального связующего дерева, вам нужно сделать это самостоятельно.