Найти ближайшую точку на декартовой плоскости? - PullRequest
Новая
       37

Найти ближайшую точку на декартовой плоскости?

0 голосов
/ 06 мая 2019

На декартовой плоскости есть случайные точки. Подобно PlottedPointName (a, b, c) с X-координатами (2,4,2) и Y-координатами (6,3,4), и если мы найдем ближайшую точку для поиска NearestPointTo (a, b), которая является NearestPointName (c ), который является ближайшим к точке (a) и NearestPointName (c), который является ближайшим к точке (b).

Я написал код для него с временной сложностью O (n ^ 3). Вычислив расстояние от findNearestPointTo (a, b) до всех остальных точек и найдите минимум. 

string[] PlottedPointName={"a","b","c"};
int[] x_cord = {2,4,2};
int[] y_cord = {6,3,4};

int min = 0;
int distance =0;
string[] findNearestPointTo = {"a", "b"};
string[] nearestPoints= new string[findNearestPointTo.length];

for(int i=0;i<findNearestPointTo.length;i++)
 {
   min=0;
   for(int j=0;j<PlottedPointName.lenght;j++)
     {
        if(findNearestPointTo[i]==points[j])
          {
            for(int k=0;k<PlottedPointName.length;k++)
             {
               if(k!=j){
               distance = abs(x_cord[i] - x_cord[k]) + abs(y_cord[i] - y_cord[k]);
               if(min==0)
                 {
                   min=distance;
                   nearestPoints[i]= PlottedPointName[k];
                 }
                else if(min>0)
                 {
                   if(min>distance)
                     {
                       min= distance;
                       nearestPoints[i]= PlottedPointName[k];
                     }
                 }
                }
             } 
          }
     }
 }

Есть ли возможность сделать этот код более эффективным с меньшей трудоемкостью.

Ответы [ 2 ]

0 голосов
/ 06 мая 2019

вы можете решить это в O (n ^ 2) без использования первого цикла, так как размер вашего массива запросов и массив, который вы хотите вернуть, будут иметь размер sam, поэтому, если ваше условие, что кординаты равны, а имя запроса такое же на момент итерации, и все остальные условия выполняются, просто добавьте название города в массив nearCity по индексу, который будет таким же для запроса, который вы проверяете для

0 голосов
/ 06 мая 2019

Ну, есть только одна оптимизация, которую я могу порекомендовать:

После того как вы нашли точку в if(findNearestPointTo[i]==points[j]), вы можете break из этого цикла в качестве последнего оператора блока if.

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

Это не уменьшает коэффициент, это будет O (n ^ 2), но на практике, если примерно вдвое уменьшит время (постоянный фактор уменьшится вдвое).

...