दो अंक के बीच निकटतम दूरी (असंबंधित समूह)

Question

यह समस्या दो असंबंधित समूह के बीच करीबी जोड़ी का एक प्रकार है। उपरोक्त तस्वीर इस समस्या को व्यक्त किया गया है। दो प्रकार के डिजॉइंट सेट, एक्स प्लेन में ब्लू डॉट्स, + एक्स प्लेन में लाल डॉट्स हैं।

मैं कम से कम दूरी की गणना करना चाहते हैं (दूरी है | y2-y1 | + | x2 - x 1 |) एक नीले डॉट और एक लाल डॉट के बीच, और मैं दूरी को खोजने के लिए लगता है कि उपयोग द्विआधारी खोज। द्विआधारी खोज इस तरह की समस्या का उपयोग कैसे करें? मैं केवल पर बाइनरी खोज को दो डिजॉइंट सेट व्यक्त करने पर संघर्ष करता हूं। मैं पहले से ही एक सेट के लिए जानता हूं, लेकिन मुझे दो अलग-अलग सेटों के मामले में पता नहीं है।

++) यह डेलाउन त्रिभुज का उपयोग कर रैखिक समय में हो सकता है? (आह, यह केवल मेरी जिज्ञासा है, मैं बाइनरी खोज का उपयोग करना चाहता हूं)

कोड के नीचे जो मैंने पहले से ही एक सेट केस कोडिंग (समस्या सुलझाने की तकनीक, विभाजन और कोंककर का उपयोग करके) और दो अपमान सेट को कवर किया था। मुझे समझ में नहीं आता कि दो सेट में कैसे करना है। उदाहरण, संकेत। ठीक है .. कृपया कोई मेरी मदद करो?

#include <iostream> 
#include <algorithm> 
#include <iomanip> 
#include <cmath> 

/** 
test input 
10 
-16 -4 
-1 -3 
-9 -1 
-4 -10 
-11 -6 
-20 4 
-13 6 
-3 -10 
-19 -1 
-12 -4 
10 
8 2 
10 3 
10 10 
20 -3 
20 3 
16 2 
3 -5 
14 -10 
8 -2 
14 0 

10 
-3 39 
-2 -28 
-1 20 
-3 11 
-3 45 
-2 -44 
-1 -47 
-5 -35 
-5 -19 
-5 -45 
10 
27 5 
28 0 
28 5 
21 5 
2 3 
13 -1 
16 -2 
20 -2 
33 -3 
27 1 
**/ 


using namespace std; 

const int MAX = 10001; 

struct point{ 
    int x,y; 
}; 

bool xCompare(struct point, struct point); 
bool yCompare(struct point, struct point); 
int dis(struct point, struct point); 

int absd(int); 
int trace(int,int,int,int); 

point p[MAX], q[MAX], tmp[MAX]; 

int main(){ 

    int left; 
    int right; 

    scanf("%d\n", &left); 
    memset(p,0,sizeof(p)); 
    memset(q,0,sizeof(q)); 
    memset(tmp,0,sizeof(tmp)); 


    for(int i=0; i<left; i++){ 
     cin >> p[i].x >> p[i].y; 
    } 

    scanf("%d\n", &right); 

    for(int j=0; j<right; j++){ 
     cin >> q[j].x >> q[j].y; 
    } 

    sort(p, p+left, xCompare); 
    sort(q, q+right, xCompare); 

    int min = trace(0,0, left-1, right-1); 

    printf("%d\n", min); 


    /** this is one set case. 
    while(true){ 
     cin >> n; 

     if(n == 0) break; 

     memset(p,0,sizeof(p)); 
     memset(tmp,0,sizeof(tmp)); 

     for(int i= 0;i<n;i++) 
      cin >> p[i].x >> p[i].y; 

     sort(p,p+n,xCompare); 

     int min = trace(0,n-1); 

     if(min < 10000 && n > 1){ 
      cout << fixed; 
      cout << setprecision(4) << min << endl; 
     } 
     else 
      cout << "INFINITY" << endl; 
    } 
    **/ 

    return 0; 
} 

int trace(int low1, int low2, int high1, int high2){ 

    if(high1 - low1 < 3){ 
     int value = dis(p[low1],q[low2+1]); 
     int nextValue; 

     if(high1 - low1 == 2){ 
      nextValue = dis(p[low1],q[low2+2]); 

      if(value > nextValue) 
       value = nextValue; 

      nextValue = dis(p[low1+1],q[low2+2]); 

      if(value > nextValue) 
       value = nextValue; 
     } 
     return value; 
    } 
    else{ 

     /* DIVIDE & QONQUER */ 

     int mid1 = (low1 + high1) >> 1; 
     int mid2 = (low2 + high2) >> 1; 
     int cnt = 0; 

     int leftValue = trace(low1,low2,mid1,mid2);  // left trace 
     int rightValue = trace(mid1+1,mid2+1,high1,high2); // right trace 

     // min value find 
     int value = leftValue < rightValue ? leftValue : rightValue; 

     /* Middle Condition Check : Y Line */ 

     // saving left 
     for(int i = low1;i<=mid1;i++){ 
      if(abs(p[i].x - q[mid2].x) <= value) 
       tmp[cnt++] = p[i]; 
     } 

     // saving right 
     for(int i = mid1+1;i<=high1;i++){ 
      if(absd(p[i].x - q[mid2+1].x) <= value) 
       tmp[cnt++] = p[i]; 
     } 

     sort(tmp,tmp+cnt,yCompare); 

     for(int i = 0;i<cnt;i++){ 
      int count = 0; 

      for(int j = i-3;count < 6 && j < cnt;j++){ 
       if(j >= 0 && i != j){ 
        int distance = dis(tmp[i],tmp[j]); 

        if(value > distance) 
         value = distance; 

        count++; 
       } 
      } 
     } 
     return value; 
    } 
} 

int absd(int x){ 
    if(x < 0) 
     return -x; 
    return x; 
} 

int dis(struct point a, struct point b){ 
    return (abs(a.x-b.x) + abs(a.y-b.y)); 
} 

bool xCompare(struct point a, struct point b){ 
    return a.x < b.x; 
} 

bool yCompare(struct point a, struct point b){ 
    return a.y < b.y; 
} 

Answer 1

इस समस्या को आमतौर पर निकटतम बिच्रोमैटिक जोड़ी समस्या कहा जाता है। यहां कुछ दृष्टिकोण हैं।

1. डेलाउने त्रिकोण। (यह निश्चित रूप से एल (= यूक्लिडियन) दूरी के साथ काम करता है; मुझे लगता है कि चरण एल को सामान्यीकृत करते हैं।) प्रत्येक डेलाउने त्रिभुज के लिए (अपर्याप्त मामलों में एक से अधिक हो सकते हैं), वहां एक न्यूनतम स्पैनिंग पेड़ मौजूद है जिसका अस्तित्व है किनारों सभी त्रिभुज से संबंधित हैं। बदले में, इस न्यूनतम स्पैनिंग पेड़ में रंग वर्गों के बीच काट पार करने वाला सबसे छोटा किनारा होता है।

2. निकटतम पड़ोसी डेटा संरचनाएं।

3. यह दिया जाता है कि लाल अंक नीले अंक से एक्स में अलग होती है, तो आप हे (एन) के सबसे नज़दीक Shamos-Hoey विभाजन और जीत एल्गोरिथ्म के कदम विलय अनुकूल करने के लिए सक्षम हो सकता है (monochromatic) जोड़ी समस्या, वर्णित here।

Answer 2

मैं एक ऐसी ही समस्या है जहाँ मैं एक सदस्य एक समूह के भीतर एक समूह से संबंध रखते हैं, तो पहचान करने के लिए एक निकटतम सदस्य की तलाश करनी है पर काम किया। मैं क्लस्टर के भीतर समूहों की पहचान करने की कोशिश कर रहा था। यहां कोड है, यह आपको प्रारंभ करने में मदद कर सकता है।

/** 
* Find the nearest neighbor based on the distance threshold. 
* TODO: 
* @param currentPoint current point in the memory. 
* @param threshold dynamic distance threshold. 
* @return return the neighbor. 
*/ 

private double nearestNeighbor(double currentPoint) { 

    HashMap<Double, Double> unsorted = new HashMap<Double, Double>(); 
    TreeMap<Double, Double> sorted = null; 
    double foundNeighbor = 0.0; 

    for (int i = 0; i < bigCluster.length; i++) { 
     if (bigCluster[i] != 0.0 && bigCluster[i] != currentPoint) { 
      double shortestDistance = Math.abs(currentPoint - bigCluster[i]); 
      if (shortestDistance <= this.getDistanceThreshold()) 
       unsorted.put(shortestDistance, bigCluster[i]); 
     } 
    } 
    if (!unsorted.isEmpty()) { 
     sorted = new TreeMap<Double, Double>(unsorted); 
     this.setDistanceThreshold(avgDistanceInCluster()); 
     foundNeighbor = sorted.firstEntry().getValue(); 
     return foundNeighbor; 
    } else { 
     return 0.0; 
    } 
} 


/** 
* Method will check if a point belongs to a cluster based on the dynamic 
* threshold. 
*/ 
public void isBelongToCluster() { 


     for (int i=0; i < tempList.size(); i++) { 

      double aPointInCluster = tempList.get(i); 

      cluster.add(aPointInCluster); 
      double newNeighbor = nearestNeighbor(aPointInCluster); 
      if (newNeighbor != 0.0) { 
       cluster.add(newNeighbor); 
       if (i + 1 > tempList.size() && (visited[i] != true)) { 
        isBelongToCluster(); 
       } 
      } 

     } 

    for (int i=0; i < cluster.size(); i++) { 
     if (cluster.get(i) != 0.0) 
      System.out.println("whats in the cluster -> " + cluster.get(i)); 
    } 
} 

Answer 3

आप स्थानिक डेटा पर द्विआधारी खोज करना चाहते हैं, तो आप इस तरह के एक quadtree या एक k-घ पेड़ के रूप में एक स्थानिक डेटा संरचना, इस्तेमाल कर सकते हैं।

Answer 4

यहाँ एक और उपाय है। यह मूल रूप से क्या करता है, दोनों बिंदुओं के सेट को दो केडी पेड़ के उदाहरणों में लोड करता है (जिसने एक्स और वाई अक्ष पर पेड़ को टुकड़ा करने के लिए तंत्र बनाया है) और फिर दोनों नोडों की जांच करके दोनों पेड़ों के माध्यम से नेविगेट करता है यदि दोनों के बीच की दूरी पूर्व नोड्स के बीच की दूरी से कम, यदि हां, तो तब तक जारी रखें जब तक आपसी दूरी किसी भी अन्य से कम न हो।

नीचे कोड कोड नोड्स के बीच नेविगेट करते समय प्राप्त दूरी को प्रिंट करता है और उन्हें प्रिंट करता है। अंक के दोनों सेट को भी एल्गोरिदम की शुद्धता देखने के लिए देखा जा सकता है।

इस कोड को सही ढंग से, निकटतम नोड्स पा सकते हैं, भले ही एक सेट नेस्ट है या नहीं, सही पर,, बाएं, ऊपर या अन्य के नीचे

#include <iostream> 

using namespace std; 

int const k=2; // the number of dimensions 
double min_distance = 10000; // set a large default value, in this example all distance will be shorter than this. 

double distance(int arr[], int arr2[]) 
{ 
return sqrt(pow(arr2[0] - arr[0], 2) + pow(arr2[1] - arr[1], 2)); 

} 

struct Node { 
int point[k]; 
Node *left, *right; 
Node() 
{ 
    left = right = NULL; 

} 
}; 

// A method to create a node of K D tree 
struct Node* newNode(int arr[]) 
{ 
struct Node* temp = new Node; 

for (int i = 0; i<k; i++) temp->point[i] = arr[i]; 

return temp; 
} 

Node * insertNode(Node * node, int arr[], int d) 
{ 
if (node == NULL) 
    return newNode(arr); 

int dim = d%k; 


if (node->point[dim] > arr[dim]) 
{ 


    node->left = insertNode(node->left, arr, dim + 1); 
} 
else 
{ 

    node->right = insertNode(node->right, arr, dim + 1); 
} 

return node; 
} 
Node * Nearest=NULL; 

Node * FindnearestNode(Node * head1, int arr[], int d) 
{ 
// if empty tree, return 
if (head1 == NULL) 
    return NULL; 

// check for each tree. 
    if (min_distance > distance(head1->point, arr)) 
{ 
    min_distance = distance(head1->point, arr); 
    Nearest = head1; 
} 

if (head1->left == NULL && head1->right == NULL) 
    return head1; 

// findout current dimension, in this case it either x or y i.e. 0 or 1 
int dim = d%k; 

// navigate through the tree as if inserting to a new member (to remain to the nearest member in closeness). in the path for insert it will find the nearest member. 
if (head1->right && head1->point[dim] < arr[dim]) return FindnearestNode(head1->right, arr, d+1); 
else if(head1->left && head1->point[dim] > arr[dim]) 
    return FindnearestNode(head1->left, arr, d+1); 

return Nearest; 
} 


int main() 
{ 
int const an = 10; 
int const bn = 10; 

int ax[an] = { 34,55,11,79,77,65,3,9,5,66 }; 
int ay[an] = { 5, 6, 7, 9, 32,3,15,7,10,35 }; 

int bx[bn] = { 5,35,4,41,32,64,41,54,87,3 }; 
int by[bn] = { 23,33,17,15,32,22,33,23,21,32 }; 



Node * head1=NULL; 
Node * head2 = NULL; 



double Final_Min_Distance = min_distance; 

// fill the K-D trees with the two dimensional data in two trees. 
for (int i = 0; i < an; i++) 
{ 
    int temp[k]; 
    temp[0] = ax[i]; 
    temp[1] = ay[i]; 

    head1=insertNode(head1, temp, 0); 
    temp[0] = bx[i]; 
    temp[1] = by[i]; 

    head2=insertNode(head2, temp, 0); 


} 
Node * AnearB=NULL; 

Node * BnearA = NULL; 



min_distance = 1000; 
    Final_Min_Distance = min_distance; 
for (int i = 0; i < an; i++) { int temp[k]; temp[0] = bx[i]; temp[1] = by[i]; Node * Nearer2 = FindnearestNode(head1, temp, 0); if (Final_Min_Distance > min_distance) 
    { 
    BnearA = Nearer2; 
    Final_Min_Distance = min_distance; 
    } 
    cout << " distance of B (" << temp[0] << "," << temp[1] << ") to nearest A (" << BnearA->point[0] << "," << BnearA->point[1] << ") distance:" << Final_Min_Distance << endl; 
    min_distance = 1000; 


} 
cout << "Minimum Distance is " << Final_Min_Distance<<endl<<endl; 


min_distance = 1000; 
Final_Min_Distance = min_distance; 
for (int i = 0; i < an; i++) { int temp[k]; temp[0] = ax[i]; temp[1] = ay[i]; Node * Nearer2 = FindnearestNode(head2, temp, 0); if (Final_Min_Distance > min_distance) 
    { 
    AnearB = Nearer2; 
    Final_Min_Distance = min_distance; 
    } 
    cout << " distance of A (" << temp[0] << "," << temp[1] << ") to nearest B (" << AnearB->point[0] << "," << AnearB->point[1] << ") distance:" << Final_Min_Distance << endl; 
    min_distance = 1000; 


} 
cout << "Minimum Distance is " << Final_Min_Distance; 



system("pause"); 

} 

https://tahirnaeem.net/finding-closest-pair-of-points-in-two-disjoint-sets-of-points