| 1480 | // is to be reordered. We will leave these as ints now. |
| 1481 | |
| 1482 | void vtkKdTree::Select_(int dim, float* X, int* ids, int L, int R, int K) |
| 1483 | { |
| 1484 | int N, I, J, S, SD, LL, RR; |
| 1485 | float Z, T; |
| 1486 | int manyTValues = 0; |
| 1487 | |
| 1488 | while (R > L) |
| 1489 | { |
| 1490 | if (R - L > 600) |
| 1491 | { |
| 1492 | // "Recurse on a sample of size S to get an estimate for the |
| 1493 | // (K-L+1)-th smallest element into X[K], biased slightly so |
| 1494 | // that the (K-L+1)-th element is expected to lie in the |
| 1495 | // smaller set after partitioning" |
| 1496 | |
| 1497 | N = R - L + 1; |
| 1498 | I = K - L + 1; |
| 1499 | Z = static_cast<float>(log(static_cast<float>(N))); |
| 1500 | S = static_cast<int>(.5 * exp(2 * Z / 3)); |
| 1501 | SD = static_cast<int>(.5 * sqrt(Z * S * static_cast<float>(N - S) / N) * sign(I - N / 2)); |
| 1502 | LL = vtkMath::Max(L, K - static_cast<int>(I * static_cast<float>(S) / N) + SD); |
| 1503 | RR = vtkMath::Min(R, K + static_cast<int>((N - I) * static_cast<float>(S) / N) + SD); |
| 1504 | Select_(dim, X, ids, LL, RR, K); |
| 1505 | } |
| 1506 | |
| 1507 | float* Xcomponent = X + dim; // x, y or z component |
| 1508 | |
| 1509 | T = Xcomponent[K * 3]; |
| 1510 | |
| 1511 | // "the following code partitions X[L:R] about T." |
| 1512 | |
| 1513 | I = L; |
| 1514 | J = R; |
| 1515 | |
| 1516 | Exchange(X, ids, L, K); |
| 1517 | |
| 1518 | if (Xcomponent[R * 3] >= T) |
| 1519 | { |
| 1520 | if (Xcomponent[R * 3] == T) |
| 1521 | manyTValues++; |
| 1522 | Exchange(X, ids, R, L); |
| 1523 | } |
| 1524 | while (I < J) |
| 1525 | { |
| 1526 | Exchange(X, ids, I, J); |
| 1527 | |
| 1528 | while (Xcomponent[(++I) * 3] < T) |
| 1529 | { |
| 1530 | } |
| 1531 | |
| 1532 | // NOLINTNEXTLINE(bugprone-inc-dec-in-conditions) |
| 1533 | while ((J > L) && (Xcomponent[(--J) * 3] >= T)) |
| 1534 | { |
| 1535 | if (!manyTValues && (J > L) && (Xcomponent[J * 3] == T)) |
| 1536 | { |
| 1537 | manyTValues = 1; |
| 1538 | } |
| 1539 | } |