1 /*
2 * Copyright (C) 2017 Alberto Irurueta Carro (alberto@irurueta.com)
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.irurueta.geometry;
18
19 import java.lang.reflect.Array;
20 import java.util.Collection;
21
22 /**
23 * Implementation of a k-D tree in an arbitrary dimension.
24 * Once a K-D tree is built for a collection of points, it can later be used to efficiently do certain operations
25 * such as point location, nearest points searches, etc.
26 */
27 public abstract class KDTree<P extends Point<P>> {
28
29 /**
30 * Minimum number of allowed points to be stored in the tree.
31 */
32 public static final int MIN_PTS = 3;
33
34 /**
35 * A very large value to consider as the maximum allowed coordinate value.
36 */
37 protected static final double BIG = Double.MAX_VALUE;
38
39 /**
40 * Number of tasks that can be queued.
41 */
42 private static final int N_TASKS = 50;
43
44 /**
45 * Array of boxes stored in this tree as its nodes.
46 */
47 protected BoxNode<P>[] boxes;
48
49 /**
50 * Indices of points going from boxes in the tree to the input collection of points.
51 * Indices are sorted as the tree is built.
52 */
53 private final int[] ptIndx;
54
55 /**
56 * Indices of points going from input collection of points to boxes in the tree.
57 * This is the reverse of mPtIndx.
58 */
59 private final int[] rPtIndx;
60
61 /**
62 * Number of points stored by the tree.
63 */
64 private final int nPts;
65
66 /**
67 * Array of points containing input collection of points.
68 */
69 private P[] pts;
70
71 /**
72 * Constructor.
73 *
74 * @param pts collection of points to store in the tree.
75 * @param clazz class of point implementation to use.
76 */
77 protected KDTree(final Collection<P> pts, final Class<P> clazz) {
78 nPts = pts.size();
79 if (nPts < MIN_PTS) {
80 throw new IllegalArgumentException("number of points must be at least 3");
81 }
82
83 //noinspection unchecked
84 this.pts = (P[]) Array.newInstance(clazz, pts.size());
85 this.pts = pts.toArray(this.pts);
86 ptIndx = new int[nPts];
87 rPtIndx = new int[nPts];
88 final int dim = getDimensions();
89
90 // build tree
91 int ntmp;
92 int m;
93 int k;
94 int kk;
95 int j;
96 int nowtask;
97 int jbox;
98 int np;
99 int tmom;
100 int tdim;
101 int ptlo;
102 int pthi;
103 int hpOffset;
104 int cpOffset;
105 final var taskmom = new int[N_TASKS];
106 final var taskdim = new int[N_TASKS];
107 for (k = 0; k < nPts; k++) {
108 ptIndx[k] = k;
109 }
110 m = 1;
111 for (ntmp = nPts; ntmp != 0; ntmp >>= 1) {
112 m <<= 1;
113 }
114 var nboxes = 2 * nPts - (m >> 1); // number of boxes to store points
115 if (m < nboxes) {
116 nboxes = m;
117 }
118 nboxes--;
119 //noinspection unchecked
120 boxes = (BoxNode<P>[]) Array.newInstance(BoxNode.class, nboxes);
121 final var coords = new double[dim * nPts];
122 for (j = 0, kk = 0; j < dim; j++, kk += nPts) {
123 for (k = 0; k < nPts; k++) {
124 coords[kk + k] = this.pts[k].getInhomogeneousCoordinate(j);
125 }
126 }
127 P lo = createPoint(-BIG);
128 P hi = createPoint(BIG);
129 boxes[0] = new BoxNode<>(lo, hi, 0, 0, 0, 0, nPts - 1);
130 jbox = 0;
131 taskmom[1] = 0;
132 taskdim[1] = 0;
133 nowtask = 1;
134 while (nowtask != 0) {
135 tmom = taskmom[nowtask];
136 tdim = taskdim[nowtask--];
137 ptlo = boxes[tmom].ptLo;
138 pthi = boxes[tmom].ptHi;
139 hpOffset = ptlo;
140 cpOffset = tdim * nPts;
141 np = pthi - ptlo + 1;
142 kk = (np - 1) / 2;
143 selecti(kk, hpOffset, ptIndx, np, cpOffset, coords);
144
145 hi = copyPoint(boxes[tmom].getHi());
146 lo = copyPoint(boxes[tmom].getLo());
147
148 final var value = coords[tdim * nPts + ptIndx[hpOffset + kk]];
149 hi.setInhomogeneousCoordinate(tdim, value);
150 lo.setInhomogeneousCoordinate(tdim, value);
151
152 boxes[++jbox] = new BoxNode<>(copyPoint(boxes[tmom].getLo()), hi, tmom, 0, 0, ptlo, ptlo + kk);
153 boxes[++jbox] = new BoxNode<>(lo, copyPoint(boxes[tmom].getHi()), tmom, 0, 0, ptlo + kk + 1,
154 pthi);
155 boxes[tmom].dau1 = jbox - 1;
156 boxes[tmom].dau2 = jbox;
157 if (kk > 1) {
158 taskmom[++nowtask] = jbox - 1;
159 taskdim[nowtask] = (tdim + 1) % dim;
160 }
161 if (np - kk > 3) {
162 taskmom[++nowtask] = jbox;
163 taskdim[nowtask] = (tdim + 1) % dim;
164 }
165 }
166 for (j = 0; j < nPts; j++) {
167 rPtIndx[ptIndx[j]] = j;
168 }
169 }
170
171 /**
172 * Gets distance between points located at provided positions on input collection.
173 *
174 * @param jpt index of 1st point.
175 * @param kpt index of 2nd point.
176 * @return distance between points or BIG if indices are equal.
177 */
178 public double distance(final int jpt, final int kpt) {
179 if (jpt == kpt) {
180 return BIG;
181 } else {
182 return pts[jpt].distanceTo(pts[kpt]);
183 }
184 }
185
186 /**
187 * Gets position of smallest box containing provided point in the input list of points.
188 *
189 * @param pt point to locate its containing box. Does not need to be contained in input collection.
190 * @return position of smallest box containing the point.
191 */
192 public int locateBoxIndex(final P pt) {
193 final var dim = getDimensions();
194
195 var nb = 0;
196 int d1;
197 var jdim = 0;
198 while (boxes[nb].dau1 != 0) {
199 d1 = boxes[nb].dau1;
200 if (pt.getInhomogeneousCoordinate(jdim) <= boxes[d1].getHi().getInhomogeneousCoordinate(jdim)) {
201 nb = d1;
202 } else {
203 nb = boxes[nb].dau2;
204 }
205 jdim = ++jdim % dim;
206 }
207 return nb;
208 }
209
210 /**
211 * Gets smallest box containing provided point in the input list of points.
212 *
213 * @param pt point to locate its containing box. Does not need to be contained in input collection.
214 * @return smallest box containing the point.
215 */
216 public BoxNode<P> locateBox(final P pt) {
217 return boxes[locateBoxIndex(pt)];
218 }
219
220 /**
221 * Index in provided input list of points of closest point to provided one.
222 *
223 * @param pt point to check against. Does not need to be contained in input collection.
224 * @return position of closest point.
225 */
226 public int nearestIndex(final P pt) {
227 int i;
228 int k;
229 int nrst = 0;
230 int ntask;
231 int pi;
232 final var task = new int[N_TASKS];
233 var dnrst = BIG;
234 double d;
235
236 // find the smallest box index containing point
237 k = locateBoxIndex(pt);
238 for (i = boxes[k].ptLo; i <= boxes[k].ptHi; i++) {
239 pi = ptIndx[i];
240 d = pts[pi].distanceTo(pt);
241 if (d < dnrst) {
242 nrst = pi; // index of nearest point
243 dnrst = d; // distance to nearest point
244 }
245 }
246
247 // check other boxes in case they contain any nearer point
248 task[1] = 0;
249 ntask = 1;
250 while (ntask != 0) {
251 k = task[ntask--];
252 if (boxes[k].getDistance(pt) < dnrst) {
253 if (boxes[k].dau1 != 0) {
254 task[++ntask] = boxes[k].dau1;
255 task[++ntask] = boxes[k].dau2;
256 } else {
257 for (i = boxes[k].ptLo; i <= boxes[k].ptHi; i++) {
258 d = pts[ptIndx[i]].distanceTo(pt);
259 if (d < dnrst) {
260 nrst = ptIndx[i];
261 dnrst = d;
262 }
263 }
264 }
265 }
266 }
267 return nrst;
268 }
269
270 /**
271 * Closest point to provided one.
272 *
273 * @param pt point to be checked. Does not need to be contained in input collection.
274 * @return closest point.
275 */
276 public P nearestPoint(final P pt) {
277 return pts[nearestIndex(pt)];
278 }
279
280 /**
281 * Gets n nearest point indices to a given one in the input collection.
282 *
283 * @param jpt index of point to search nearest ones for.
284 * @param nn array containing resulting indices of nearest points up to the number of found points.
285 * @param dn array containing resulting distances to nearest points up to the number of found points.
286 * @param n number of nearest points to find.
287 * @throws IllegalArgumentException if number of nearest points is invalid or if length of arrays
288 * containing results are not valid either.
289 */
290 public void nNearest(final int jpt, final int[] nn, final double[] dn, final int n) {
291 if (n < 0) {
292 throw new IllegalArgumentException("no neighbours requested");
293 }
294 if (n > nPts - 1) {
295 throw new IllegalArgumentException("too many neighbours requested");
296 }
297 if (nn.length != n || dn.length != n) {
298 throw new IllegalArgumentException("invalid result array lengths");
299 }
300
301 int i;
302 int k;
303 int ntask;
304 int kp;
305 final var task = new int[N_TASKS];
306 double d;
307 for (i = 0; i < n; i++) {
308 dn[i] = BIG;
309 }
310 kp = boxes[locate(jpt)].mom;
311 while (boxes[kp].ptHi - boxes[kp].ptLo < n) {
312 kp = boxes[kp].mom;
313 }
314 for (i = boxes[kp].ptLo; i <= boxes[kp].ptHi; i++) {
315 if (jpt == ptIndx[i]) {
316 continue;
317 }
318 d = distance(ptIndx[i], jpt);
319 if (d < dn[0]) {
320 dn[0] = d;
321 nn[0] = ptIndx[i];
322 if (n > 1) {
323 siftDown(dn, nn, n);
324 }
325 }
326 }
327 task[1] = 0;
328 ntask = 1;
329 while (ntask != 0) {
330 k = task[ntask--];
331 if (k == kp) {
332 continue;
333 }
334 if (boxes[k].getDistance(pts[jpt]) < dn[0]) {
335 if (boxes[k].dau1 != 0) {
336 task[++ntask] = boxes[k].dau1;
337 task[++ntask] = boxes[k].dau2;
338 } else {
339 for (i = boxes[k].ptLo; i <= boxes[k].ptHi; i++) {
340 d = distance(ptIndx[i], jpt);
341 if (d < dn[0]) {
342 dn[0] = d;
343 nn[0] = ptIndx[i];
344 if (n > 1) {
345 siftDown(dn, nn, n);
346 }
347 }
348 }
349 }
350 }
351 }
352 }
353
354 /**
355 * Gets n nearest point indices to a given point in the input collection.
356 *
357 * @param pt point to search nearest ones for.
358 * @param nn array containing resulting indices of nearest points up to the number of found points.
359 * @param dn array containing resulting distances to nearest points up to the number of found points.
360 * @param n number of nearest points to find.
361 * @throws IllegalArgumentException if number of nearest points is invalid or if length of arrays
362 * containing results are not valid either.
363 */
364 public void nNearest(final P pt, final int[] nn, final double[] dn, final int n) {
365 nNearest(nearestIndex(pt), nn, dn, n);
366 }
367
368 /**
369 * Gets n nearest points to a given point index in the input collection.
370 *
371 * @param jpt index of point to search nearest ones for.
372 * @param pn array containing nearest points up to the number of found points.
373 * @param dn array containing resulting distances to nearest points up to the number of found points.
374 * @param n number of nearest points to find.
375 * @throws IllegalArgumentException if number of nearest points is invalid or if length of arrays
376 * containing results are not valid either.
377 */
378 public void nNearest(final int jpt, final P[] pn, final double[] dn, final int n) {
379 if (n < 0) {
380 throw new IllegalArgumentException("no neighbours requested");
381 }
382
383 final var nn = new int[n];
384
385 nNearest(jpt, nn, dn, n);
386
387 for (var i = 0; i < n; i++) {
388 pn[i] = pts[nn[i]];
389 }
390 }
391
392 /**
393 * Gets n nearest points to a given point in the input collection.
394 *
395 * @param pt point to search nearest ones for.
396 * @param pn array containing nearest points up to the number of found points.
397 * @param dn array containing resulting distances to nearest points up to the number of found points.
398 * @param n number of nearest points to find.
399 * @throws IllegalArgumentException if number of nearest points is invalid or if length of arrays
400 * containing results are not valid either.
401 */
402 public void nNearest(final P pt, final P[] pn, final double[] dn, final int n) {
403 nNearest(nearestIndex(pt), pn, dn, n);
404 }
405
406 /**
407 * Locates some near points to provided one up to a certain radius of search.
408 * This method only returns up to nmax results, which means that not all points within required
409 * radius are returned if more points than provided nmax value are within such radius.
410 *
411 * @param pt point to search nearby.
412 * @param r radius of search.
413 * @param list list where indices of found points are stored up to the number of found points.
414 * @param nmax maximum number of points to search.
415 * @return number of found points.
416 * @throws IllegalArgumentException if radius is negative or maximum number of points to search is zero or negative,
417 * or list where indices are stored is not large enough.
418 */
419 public int locateNear(final P pt, final double r, final int[] list, final int nmax) {
420 if (r < 0.0) {
421 throw new IllegalArgumentException("radius must be non-negative");
422 }
423 if (nmax <= 0) {
424 throw new IllegalArgumentException("number of points to search must be at least 1");
425 }
426 if (list.length < nmax) {
427 throw new IllegalArgumentException("result might not fit into provided list");
428 }
429
430 final int dim = getDimensions();
431
432 int k;
433 int i;
434 int nb;
435 int nbold;
436 int nret;
437 int ntask;
438 int jdim;
439 int d1;
440 int d2;
441 final var task = new int[N_TASKS];
442 nb = jdim = nret = 0;
443
444 while (boxes[nb].dau1 != 0) {
445 nbold = nb;
446 d1 = boxes[nb].dau1;
447 d2 = boxes[nb].dau2;
448 final var coord = pt.getInhomogeneousCoordinate(jdim);
449 if (coord + r <= boxes[d1].getHi().getInhomogeneousCoordinate(jdim)) {
450 nb = d1;
451 } else if (coord - r >= boxes[d2].getLo().getInhomogeneousCoordinate(jdim)) {
452 nb = d2;
453 }
454 jdim = ++jdim % dim;
455 if (nb == nbold) {
456 break;
457 }
458 }
459 task[1] = nb;
460 ntask = 1;
461 while (ntask != 0) {
462 k = task[ntask--];
463 if (boxes[k].getDistance(pt) > r) {
464 continue;
465 }
466 if (boxes[k].dau1 != 0) {
467 task[++ntask] = boxes[k].dau1;
468 task[++ntask] = boxes[k].dau2;
469 } else {
470 for (i = boxes[k].ptLo; i <= boxes[k].ptHi; i++) {
471 if (pts[ptIndx[i]].distanceTo(pt) <= r && nret < nmax) {
472 list[nret++] = ptIndx[i];
473 }
474 if (nret == nmax) {
475 return nmax;
476 }
477 }
478 }
479 }
480 return nret;
481 }
482
483 /**
484 * Locates near points to provided one up to a certain radius of search defined in a bounding box.
485 *
486 * @param pt point to search nearby.
487 * @param r radius of search defining a bounding box.
488 * @param plist list where found points are stored up to the number of found points.
489 * @param nmax maximum number of points to search.
490 * @return number of found points.
491 * @throws IllegalArgumentException if radius is negative or maximum number of points to search is zero or negative,
492 * or list where points are stored is not large enough.
493 */
494 public int locateNear(final P pt, final double r, final P[] plist, final int nmax) {
495 if (r < 0.0) {
496 throw new IllegalArgumentException("radius must be non-negative");
497 }
498 if (nmax <= 0) {
499 throw new IllegalArgumentException("number of points to search must be at least 1");
500 }
501 if (plist.length < nmax) {
502 throw new IllegalArgumentException("result might not fit into provided list");
503 }
504
505 final var list = new int[nmax];
506 final var result = locateNear(pt, r, list, nmax);
507
508 for (int i = 0; i < result; i++) {
509 plist[i] = pts[list[i]];
510 }
511
512 return result;
513 }
514
515 /**
516 * Gets number of dimensions supported by this k-D tree implementation on provided list of points.
517 *
518 * @return number of dimensions.
519 */
520 public abstract int getDimensions();
521
522 /**
523 * Creates a point.
524 *
525 * @param value value to be set on point coordinates.
526 * @return created point.
527 */
528 protected abstract P createPoint(final double value);
529
530 /**
531 * Copies a point.
532 *
533 * @param point point to be copied.
534 * @return copied point.
535 */
536 protected abstract P copyPoint(final P point);
537
538 /**
539 * Gets position of point on input collection for provided internal boxes position.
540 *
541 * @param jpt internal position in the boxes.
542 * @return position in the input collection of points.
543 */
544 private int locate(final int jpt) {
545 var nb = 0;
546 int d1;
547 final var jh = rPtIndx[jpt];
548 while (boxes[nb].dau1 != 0) {
549 d1 = boxes[nb].dau1;
550 if (jh <= boxes[d1].ptHi) {
551 nb = d1;
552 } else {
553 nb = boxes[nb].dau2;
554 }
555 }
556 return nb;
557 }
558
559 /**
560 * Makes a selection so that we obtain ordered index at provided k position so that
561 * distances are ordered in such a way that resulting array arr contains distances
562 * as follows: arr[indx[0 .. k-1]] <= arr[indx[k]] <= arr[indx[k+1 .. n]].
563 * So that positions between 0 and k-1 are not in any particular order but is less than
564 * k position, and positions between k+1 and n neither have any particular order but is
565 * more than k position.
566 *
567 * @param k sorted position to retrieve.
568 * @param indxOffset offset where indx search starts.
569 * @param indx array to be sorted (i.e. selected).
570 * @param n length of arrays.
571 * @param arrOffset offset of distances array. This is usually equal to indxOffset.
572 * @param arr resulting array containing distances to each selected point.
573 * @return index of selected point.
574 */
575 @SuppressWarnings("UnusedReturnValue")
576 private static int selecti(final int k, final int indxOffset, final int[] indx, final int n, final int arrOffset,
577 final double[] arr) {
578 int i;
579 int ia;
580 var ir = n - 1;
581 int j;
582 var l = 0;
583 int mid;
584 double a;
585
586 for (; ; ) {
587 if (ir <= l + 1) {
588 if (ir == l + 1 && arr[arrOffset + indx[indxOffset + ir]] < arr[arrOffset + indx[indxOffset + l]]) {
589 swap(indx, indxOffset + l, indx, indxOffset + ir);
590 }
591 return indx[indxOffset + k];
592 } else {
593 mid = (l + ir) >> 1;
594 swap(indx, indxOffset + mid, indx, indxOffset + l + 1);
595 if (arr[arrOffset + indx[indxOffset + l]] > arr[arrOffset + indx[indxOffset + ir]]) {
596 swap(indx, indxOffset + l, indx, indxOffset + ir);
597 }
598 if (arr[arrOffset + indx[indxOffset + l + 1]] > arr[arrOffset + indx[indxOffset + ir]]) {
599 swap(indx, indxOffset + l + 1, indx, indxOffset + ir);
600 }
601 if (arr[arrOffset + indx[indxOffset + l]] > arr[arrOffset + indx[indxOffset + l + 1]]) {
602 swap(indx, indxOffset + l, indx, indxOffset + l + 1);
603 }
604 i = l + 1;
605 j = ir;
606 ia = indx[indxOffset + l + 1];
607 a = arr[arrOffset + ia];
608 for (; ; ) {
609 do {
610 i++;
611 } while (arr[arrOffset + indx[indxOffset + i]] < a);
612 do {
613 j--;
614 } while (arr[arrOffset + indx[indxOffset + j]] > a);
615 if (j < i) {
616 break;
617 }
618 swap(indx, indxOffset + i, indx, indxOffset + j);
619 }
620 indx[indxOffset + l + 1] = indx[indxOffset + j];
621 indx[indxOffset + j] = ia;
622 if (j >= k) {
623 ir = j - 1;
624 }
625 if (j <= k) {
626 l = i;
627 }
628 }
629 }
630 }
631
632 /**
633 * Moves things around.
634 *
635 * @param heap array of distances.
636 * @param ndx array of indices.
637 * @param nn number of indices to move.
638 */
639 private static void siftDown(final double[] heap, final int[] ndx, final int nn) {
640 final var n = nn - 1;
641 var j = 1;
642 var jold = 0;
643 final var ia = ndx[0];
644 final var a = heap[0];
645 while (j <= n) {
646 if (j < n && heap[j] < heap[j + 1]) {
647 j++;
648 }
649 if (a >= heap[j]) {
650 break;
651 }
652 heap[jold] = heap[j];
653 ndx[jold] = ndx[j];
654 jold = j;
655 j = 2 * j + 1;
656 }
657 heap[jold] = a;
658 ndx[jold] = ia;
659 }
660
661 /**
662 * Swaps values.
663 *
664 * @param a 1st array containing values to swap.
665 * @param posA position to be swapped on 1st array.
666 * @param b 2nd array containing values to swap.
667 * @param posB position to be swapped on 2nd array.
668 */
669 private static void swap(final int[] a, final int posA, final int[] b, final int posB) {
670 final var tmp = a[posA];
671
672 a[posA] = b[posB];
673 b[posB] = tmp;
674 }
675
676 /**
677 * Contains a node of a KD Tree.
678 */
679 public static class BoxNode<P extends Point<P>> extends Box<P> {
680
681 /**
682 * Position of mother node in the list of nodes of a tree.
683 */
684 private final int mom;
685
686 /**
687 * Position of 1st daughter node in the list of nodes of a tree.
688 */
689 private int dau1;
690
691 /**
692 * Position of 2nd daughter node of a tree.
693 */
694 private int dau2;
695
696 /**
697 * Low index of list of points inside this box.
698 * mPtLo and mPtHi define the range of points inside the box.
699 */
700 private final int ptLo;
701
702 /**
703 * High index of list of points inside this box.
704 * mPtLo and mPtHi define the range of points inside the box.
705 */
706 private final int ptHi;
707
708 /**
709 * Constructor.
710 *
711 * @param lo low coordinate values.
712 * @param hi high coordinate values.
713 * @param mom index of mother node.
714 * @param d1 index of 1st daughter.
715 * @param d2 index of 2nd daughter.
716 * @param ptLo low index of list of points inside this box.
717 * @param ptHi high index of list of points inside this box.
718 */
719 public BoxNode(final P lo, final P hi, final int mom, final int d1, final int d2, final int ptLo,
720 final int ptHi) {
721 super(lo, hi);
722 this.mom = mom;
723 dau1 = d1;
724 dau2 = d2;
725 this.ptLo = ptLo;
726 this.ptHi = ptHi;
727 }
728
729 /**
730 * Gets position of mother node in the list of nodes of a tree.
731 *
732 * @return position of mother node in the list of nodes of a tree.
733 */
734 public int getMom() {
735 return mom;
736 }
737
738 /**
739 * Gets position of 1st daughter node in the list of nodes of a tree.
740 *
741 * @return position of 1st daughter node in the list of nodes of a tree.
742 */
743 public int getDau1() {
744 return dau1;
745 }
746
747 /**
748 * Gets position of 2nd daughter node of a tree.
749 *
750 * @return position of 2nd daughter node of a tree.
751 */
752 public int getDau2() {
753 return dau2;
754 }
755
756 /**
757 * Gets low index of list of points inside this box.
758 * getPtLo() and {@link #getPtHi()} define the range of indices of points
759 * contained in this box.
760 *
761 * @return low index of list of points inside this box.
762 */
763 public int getPtLo() {
764 return ptLo;
765 }
766
767 /**
768 * Gets high index of list of points inside this box.
769 * {@link #getPtLo()} and getPtHi() define the range of indices of points
770 * contained in this box.
771 *
772 * @return high index of list of points inside this box.
773 */
774 public int getPtHi() {
775 return ptHi;
776 }
777
778 /**
779 * Sets low coordinate values.
780 *
781 * @param lo low coordinate values.
782 * @throws IllegalArgumentException always thrown.
783 */
784 @Override
785 public void setLo(final P lo) {
786 throw new IllegalArgumentException();
787 }
788
789 /**
790 * Sets high coordinate values.
791 *
792 * @param hi high coordinate values.
793 * @throws IllegalArgumentException always thrown.
794 */
795 @Override
796 public void setHi(final P hi) {
797 throw new IllegalArgumentException();
798 }
799
800 /**
801 * Sets boundaries.
802 *
803 * @param lo low coordinate values.
804 * @param hi high coordinate values.
805 * @throws IllegalArgumentException always thrown.
806 */
807 @Override
808 public void setBounds(final P lo, final P hi) {
809 throw new IllegalArgumentException();
810 }
811 }
812 }