Graphviz 13.0.0~dev.20241220.2304
Loading...
Searching...
No Matches
nearest_neighbor_graph_ann.cpp
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#include <ANN/ANN.h> // ANN declarations
13#include <utility>
14#include <vector>
15
16static const int dim = 4; // dimension
17
18static void sortPtsX(int n, ANNpointArray pts){
19 /* sort so that edges always go from left to right in x-doordinate */
20 for (int i = 0; i < n; i++){
21 ANNpoint p = pts[i];
22 if (p[0] < p[2] || (p[0] == p[2] && p[1] < p[3])) continue;
23 std::swap(p[0], p[2]);
24 std::swap(p[1], p[3]);
25 }
26}
27
28static void sortPtsY(int n, ANNpointArray pts){
29 /* sort so that edges always go from left to right in x-doordinate */
30 for (int i = 0; i < n; i++){
31 ANNpoint p = pts[i];
32 if (p[1] < p[3] || (p[1] == p[3] && p[0] < p[2])) continue;
33 std::swap(p[0], p[2]);
34 std::swap(p[1], p[3]);
35 }
36}
37
38void nearest_neighbor_graph_ann(int nPts, int k, const std::vector<double> &x,
39 int &nz0, std::vector<int> &irn,
40 std::vector<int> &jcn,
41 std::vector<double> &val) {
42
43 /* Gives a nearest neighbor graph is a list of dim-dimendional points. The connectivity is in irn/jcn, and the distance in val.
44
45 nPts: number of points
46 dim: dimension
47 k: number of neighbors needed
48 x: nPts*dim vector. The i-th point is x[i*dim : i*dim + dim - 1]
49 nz: number of entries in the connectivity matrix irn/jcn/val
50 irn, jcn: the connectivity
51 val: the distance
52
53 note that there could be repeates
54 */
55
56 // error tolerance
57 const double eps = 0;
58
59 ANNpointArray dataPts = annAllocPts(nPts, dim); // allocate data points
60 std::vector<ANNidx> nnIdx(k); // allocate near neighbor indices
61 std::vector<ANNdist> dists(k); // allocate near neighbor dists
62
63 for (int i = 0; i < nPts; i++){
64 double *xx = dataPts[i];
65 for (int j = 0; j < dim; j++) xx[j] = x[i*dim + j];
66 }
67
68 //========= graph when sort based on x ========
69 int nz = 0;
70 sortPtsX(nPts, dataPts);
71 ANNkd_tree kdTree( // build search structure
72 dataPts, // the data points
73 nPts, // number of points
74 dim); // dimension of space
75 for (int ip = 0; ip < nPts; ip++){
76 kdTree.annkSearch( // search
77 dataPts[ip], // query point
78 k, // number of near neighbors
79 nnIdx.data(), // nearest neighbors (returned)
80 dists.data(), // distance (returned)
81 eps); // error bound
82
83 for (int i = 0; i < k; i++) { // print summary
84 if (nnIdx[i] == ip) continue;
85 val[nz] = dists[i];
86 irn[nz] = ip;
87 jcn[nz++] = nnIdx[i];
88 }
89 }
90
91
92 //========= graph when sort based on y ========
93 sortPtsY(nPts, dataPts);
94 kdTree = ANNkd_tree( // build search structure
95 dataPts, // the data points
96 nPts, // number of points
97 dim); // dimension of space
98 for (int ip = 0; ip < nPts; ip++){
99 kdTree.annkSearch( // search
100 dataPts[ip], // query point
101 k, // number of near neighbors
102 nnIdx.data(), // nearest neighbors (returned)
103 dists.data(), // distance (returned)
104 eps); // error bound
105
106 for (int i = 0; i < k; i++) { // print summary
107 if (nnIdx[i] == ip) continue;
108 val[nz] = dists[i];
109 irn[nz] = ip;
110 jcn[nz++] = nnIdx[i];
111 }
112 }
113
114 nz0 = nz;
115
116 annDeallocPts(dataPts);
117 annClose(); // done with ANN
118
119
120
121}
static void sortPtsY(int n, ANNpointArray pts)
static void sortPtsX(int n, ANNpointArray pts)
void nearest_neighbor_graph_ann(int nPts, int k, const std::vector< double > &x, int &nz0, std::vector< int > &irn, std::vector< int > &jcn, std::vector< double > &val)
static const int dim