| 377 | //------------------------------------------------------------------------------ |
| 378 | template <typename TIds> |
| 379 | vtkIdType BucketList<TIds>::FindClosestPointWithinRadius( |
| 380 | double radius, const double x[3], double inputDataLength, double& dist2) |
| 381 | { |
| 382 | int i, j; |
| 383 | double pt[3]; |
| 384 | vtkIdType ptId, closest = -1; |
| 385 | int ijk[3], *nei; |
| 386 | double minDist2; |
| 387 | |
| 388 | double refinedRadius, radius2, refinedRadius2; |
| 389 | double currentRadius; |
| 390 | double distance2ToDataBounds, maxDistance; |
| 391 | int ii, radiusLevels[3], radiusLevel, prevMinLevel[3], prevMaxLevel[3]; |
| 392 | NeighborBuckets buckets; |
| 393 | const vtkLocatorTuple<TIds>* ids; |
| 394 | |
| 395 | // Initialize |
| 396 | dist2 = -1.0; |
| 397 | radius2 = radius * radius; |
| 398 | minDist2 = 1.01 * radius2; // something slightly bigger.... |
| 399 | |
| 400 | vtkDataArray* pointData = static_cast<vtkPointSet*>(this->DataSet)->GetPoints()->GetData(); |
| 401 | |
| 402 | // Find the bucket the point is in. |
| 403 | // |
| 404 | this->GetBucketIndices(x, ijk); |
| 405 | |
| 406 | // Start by searching the bucket that the point is in. |
| 407 | // |
| 408 | vtkIdType numIds; |
| 409 | vtkIdType cno = ijk[0] + ijk[1] * this->xD + ijk[2] * this->xyD; |
| 410 | if ((numIds = this->GetNumberOfIds(cno)) > 0) |
| 411 | { |
| 412 | ids = this->GetIds(cno); |
| 413 | for (j = 0; j < numIds; j++) |
| 414 | { |
| 415 | ptId = ids[j].PtId; |
| 416 | pointData->GetTuple(ptId, pt); |
| 417 | if ((dist2 = vtkMath::Distance2BetweenPoints(x, pt)) < minDist2) |
| 418 | { |
| 419 | closest = ptId; |
| 420 | minDist2 = dist2; |
| 421 | } |
| 422 | } |
| 423 | } |
| 424 | |
| 425 | // Now, search only those buckets that are within a radius. The radius used |
| 426 | // is the smaller of sqrt(minDist2) and the radius that is passed in. To avoid |
| 427 | // checking a large number of buckets unnecessarily, if the radius is |
| 428 | // larger than the dimensions of a bucket, we search outward using a |
| 429 | // simple heuristic of rings. This heuristic ends up collecting inner |
| 430 | // buckets multiple times, but this only happens in the case where these |
| 431 | // buckets are empty, so they are discarded quickly. |
| 432 | // |
| 433 | if (minDist2 < radius2) |
| 434 | { |
| 435 | refinedRadius = sqrt(minDist2); |
| 436 | refinedRadius2 = dist2; |
nothing calls this directly
no test coverage detected