Ближайшее расстояние дважды в мультикарте - PullRequest
Новая
       11

Ближайшее расстояние дважды в мультикарте

0 голосов
/ 16 мая 2018

Здравствуйте, у меня есть возможность найти ближайшие точки к другому.
Я начал с проверки, близко ли расстояние, если одна точка (которую я называю х) и другая.
Затем я сохраняю его на вкладке multimap (Int, int) с ключом, точка под названием x, а ad определяет ближайшую точку под названием x.
Проблема в том, что у меня есть одни и те же данные дважды, потому что если x близко к y, y тоже близко к x.
У меня есть список, как этот: [[25:{26,27}],[26:{25,27}], [27:{25}]]
Я пытался сравнить значения с ключами и пытался удалить их, если ключ равен значению другого ключа. Может ли кто-нибудь помочь мне найти логику, пожалуйста?

Ответы [ 3 ]

0 голосов
/ 16 мая 2018

Я бы попытался создать двумерный массив, чтобы проверить, посещена ли уже пара или нет.Например, 

int[][] visited = new int[x][y];//a pair (x , y)
 for(int i = 0; i < x; i++){
     for(int j = 0; j < y; j++){
         if(!visited[x][y] && !visited[y][x]){
            //check if (x, y) or (y, x) is already visited
            //if the pair is not visited yet, do what you want for the pair.
            visited[x][y] = true;
            visited[y][x] = true;
         }
 }
0 голосов
/ 16 мая 2018

Итак, я попробовал что-то вроде этого: 

public static ArrayList<Multimap<Integer, Integer>>  detectNode(ArrayList<Point> arrayList) {
    ArrayList<Multimap<Integer,Integer>> allresults= new ArrayList<>(); 
    for (int i = 0; i < arrayList.size(); i++) {
    Multimap<Integer,Integer> key = ArrayListMultimap.create();
    for (int j = 0; j < arrayList.size(); j++) {
    Double d=distance(arrayList.get(i),arrayList.get(j));
    if(d<5.0 && d!=0 && j>i) {
    key.put(i,j);
                              }         
                                                }
    if(!key.isEmpty()) {
    allresults.add(key);
                        }   
                                                 }
    return allresults;
                                                                      }

и я получаю это на главном:

[{25 = [28, 29, 33]}, {27 = [34, 35]}, {28 = [29]}, {31 = [32, 33]}, {32 = [33] }]

что почти нормально. Единственное, чего сейчас не хватает, так это того, что если номер 33 принадлежит ключу 25, то 31 и 32 тоже принадлежат 25!

Я попробовал этот код ниже, проверив, не является ли значение ключом где-то еще и тот же результат:

[{25 = [28, 29, 33]}, {27 = [34, 35]}, {28 = [29]}, {31 = [32, 33]}, {32 = [33] }] 

public static ArrayList<Multimap<Integer, Integer>>  detectNode(ArrayList<Point> arrayList) {
    ArrayList<Multimap<Integer,Integer>> allresults= new ArrayList<>(); 
    for (int i = 0; i < arrayList.size(); i++) {
         Multimap<Integer,Integer> key = ArrayListMultimap.create();
        for (int j = 0; j < arrayList.size(); j++) {
            Double d=distance(arrayList.get(i),arrayList.get(j));
            if(d<5.0 && d!=0 && j>i) {
                if(allresults.isEmpty()) {
                key.put(i,j);
                                    }
                for (int k = 0; k < allresults.size(); k++) {
                    if(!allresults.get(k).containsKey(j) &&  !allresults.get(k).containsEntry(i,j)) {
                        key.put(i,j);
                        break;
                    }
                }
                                    }
        }
        if(!key.isEmpty()) {
            allresults.add(key);
            }   
    }
    return allresults;
}
0 голосов
/ 16 мая 2018

Самый простой способ справиться с этим - исключить повторяющиеся пары из понимания. Например, если у вас есть итерация с вложенным циклом, вы можете просто выполнить итерацию следующим образом: 

for (int i = 0; i < points.size() - 1; ++i) {
    for (int j = i + 1; j < points.size(); ++j) {
        ... you can safely evaluate distance here and put it in multimap
    }
}

общий подход заключается в установлениикакой-то предикат и сравнивать две точки, только если это верно для, например, в коде, который я предоставил ранее, предикат заключается в том, что мы сравниваем точку points[i] с points[j] только тогда, когда i < j, что означает, что вы сравнили бы двеОчки только один раз.

...