01: /*
02: * The JTS Topology Suite is a collection of Java classes that
03: * implement the fundamental operations required to validate a given
04: * geo-spatial data set to a known topological specification.
05: *
06: * Copyright (C) 2001 Vivid Solutions
07: *
08: * This library is free software; you can redistribute it and/or
09: * modify it under the terms of the GNU Lesser General Public
10: * License as published by the Free Software Foundation; either
11: * version 2.1 of the License, or (at your option) any later version.
12: *
13: * This library is distributed in the hope that it will be useful,
14: * but WITHOUT ANY WARRANTY; without even the implied warranty of
15: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16: * Lesser General Public License for more details.
17: *
18: * You should have received a copy of the GNU Lesser General Public
19: * License along with this library; if not, write to the Free Software
20: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21: *
22: * For more information, contact:
23: *
24: * Vivid Solutions
25: * Suite #1A
26: * 2328 Government Street
27: * Victoria BC V8T 5G5
28: * Canada
29: *
30: * (250)385-6040
31: * www.vividsolutions.com
32: */
33: package com.vividsolutions.jts.index.quadtree;
34:
35: /**
36: * Provides a test for whether an interval is
37: * so small it should be considered as zero for the purposes of
38: * inserting it into a binary tree.
39: * The reason this check is necessary is that round-off error can
40: * cause the algorithm used to subdivide an interval to fail, by
41: * computing a midpoint value which does not lie strictly between the
42: * endpoints.
43: *
44: * @version 1.7
45: */
46: public class IntervalSize {
47:
48: /**
49: * This value is chosen to be a few powers of 2 less than the
50: * number of bits available in the double representation (i.e. 53).
51: * This should allow enough extra precision for simple computations to be correct,
52: * at least for comparison purposes.
53: */
54: public static final int MIN_BINARY_EXPONENT = -50;
55:
56: /**
57: * Computes whether the interval [min, max] is effectively zero width.
58: * I.e. the width of the interval is so much less than the
59: * location of the interval that the midpoint of the interval cannot be
60: * represented precisely.
61: */
62: public static boolean isZeroWidth(double min, double max) {
63: double width = max - min;
64: if (width == 0.0)
65: return true;
66:
67: double maxAbs = Math.max(Math.abs(min), Math.abs(max));
68: double scaledInterval = width / maxAbs;
69: int level = DoubleBits.exponent(scaledInterval);
70: return level <= MIN_BINARY_EXPONENT;
71: }
72: }
|