Лучший способ подключения ближайших точек в графике

У меня есть массив точек (городов), и я ищу лучший способ найти 10 ближайших точек и подключить их для создания графика. Это должно быть ровно 10 конусов от каждой точки.Лучший способ подключения ближайших точек в графике

класс Точка:

public class City 
{ 
    int key; 
    public int population; 
    Point position; 

    City(int key, int population, Point position) 
    { 
     this.key = key; 
     this.population = population; 
     this.position = position; 
    } 

    void setPopulation(int newPopulation) 
    { 
     this.population = newPopulation; 
    } 
}

Теперь у меня есть все точки в одном массиве:

City[] cities = new City[3000];

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

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

Вот как выглядят все точки, когда я их рисую. map

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

Любые советы? Спасибо за ответ.

источник

2013-11-01 Sk1X1

Я думаю, что вам нужно больше ограничений. В 1D это тривиально, но в 2D это трудно. Возьмите две точки x и y. Y может быть в 10 ближайших точках x, но x может не находиться в ближайших точках y. Так что они должны быть 10 ближайшими? Или может быть между 10-20 соединениями на каждую точку? – Jason

Если соединения двунаправленные (кажется, так), вам понадобится сводный город, чтобы определить 10 ближайших точек, и вам нужно отметить, что B подключен к A, если вы подключаете A к B. –

Они должны быть подключены с 10 ближайшими. X будет подключаться к Y, тогда Y должен быть подключен к X. Мне нужно создать неопределенный неориентированный граф. – Sk1X1

Относительно быстрые решения заключались бы в использовании адаптированного пятого поиска по каждой точке и установления соединений с первыми 10 точками, с которыми он сталкивается.

источник

2013-11-01 14:28:34

очень простой способ - использовать библиотеку для этого, например. JSI (см nearestN), и вы можете быть уверены, что его быстро (на самом деле, является ДСИ RTree -внедрения оптимизировано для пространственных запросов.

источник

2013-11-01 15:01:19 wrm

Это нормально, когда у вас есть 1 очко и вы хотите, чтобы 10 ближе всего к ней. Но как только вы сделаете это для всех точек, у некоторых точек, скорее всего, будет более 10 соединений. – Cruncher

Лучший способ подключения ближайших точек в графике

ответ

Смежные вопросы