From: <raygall@ei...>  20020611 15:50:52
Attachments:
Message as HTML
overlap.jpg

I got this class written, called ExtentMosaic, which is basically a patchwork mosaic of Extents. There is one tricky little bug, though, that I'm not sure how to get rid of. Basically the way ExtentMosaic works is to split apart any new Extent added to it to fit around the Extents which are already there using the Extent.difference() method, so that no Extent in the mosaic overlaps. The problem is that when two Extents overlap by a very small value (say 1.0E17) they don't get picked up as overlapping. So very small Extents with a width of 1.0E17 have shown up 'hiding' along the edges of other Extents. The best I can fathom is that it's an error with how the JVM handles doubles. If it try to add a width of 1.0E17 to a whole number, then the error will be ignored as it's outside of the prescision range for doubles. Any suggestions? Has GeoRectangle done this sort of thing before? The attached picture is from a graphical test, giving 100 random Extents to the ExtentMosaic. Each red/blue rectangle pair is a pair of overlapping rectangles. In each case the resultant overlap is 1.0E17 or thereabouts. Wierd. 
From: Martin Desruisseaux <martin.desruisseaux@te...>  20020612 09:09:32
Attachments:
EnvelopeExtent.png

Hello all raygall@... wrote: > The problem is that when two Extents overlap by a very small value > (say 1.0E17) they don't get picked up as overlapping. So very small > Extents with a width of 1.0E17 have shown up 'hiding' along the edges > of other Extents. > > The best I can fathom is that it's an error with how the JVM handles > doubles. If it try to add a width of 1.0E17 to a whole number, then > the error will be ignored as it's outside of the prescision range for > doubles. I didn't find the ExtentMosaic on the CVS tree, so I can't really figure out what is going for now. However, it is likely to be related to rounding error as Ray suggested. Rounding error are not really related to the JVM: they exist in C/C++ and Fortran too. They are related to the way the processor work according the IEEE 754 standard. Adding 1E17 value to an other double may or may not have an effect according the value of the number added to. To be more precise, computing "x + y" will have no effect if the ratio x/y is too different from 1. For example: 1E17 + 1E16 is okay (result is 1.1E16) 1E17 + 1 lost the 1E17 part, which is too small relative to 1. 1E+17 + 1 lost the 1 part, which is too small relative to 1E+17. Some observations about EnvelopeExtent, which seems to be the default Extent implementation: * This object is basically just a wrapper around Envelope. Futhermore, its functionalities is similar to java.awt.geom.Rectangle2D. The EnvelopeExtent.createIntersect method really duplicate Rectangle2D.createIntersection. I fell that we have a fair amount of redundancies between Extent, JTS's Envelope, OpenGIS's Envelope and Java2D's Rectangle2D. I would like to clear this thing a little bit. * Methods 'intersection' and 'difference' cast the Extent argument to an EnvelopeExtent. Consequently, those methods will fail (throw a ClassCastException) for any other arbitrary class of extents. * The algorithm for method 'difference' is to split the original rectangle into up to 4 rectangles. In comparaison, the java.awt.geom.Area class has a more sophesticated approach. It is able to compute the whole shape corresponding to one rectangle minus one other (if fact, it can compute one arbitrary shape minus an other arbitrary shape). See the attached picture. This Area shape is pretty powerfull, and I wonder if we should use it instead of cooking our own solution. Martin. 
From: Ian Turton <ian@ge...>  20020612 12:12:08

At 11:13 12/06/02 +0200, Martin Desruisseaux wrote: >Hello all > > >Some observations about EnvelopeExtent, which seems to be the default >Extent implementation: > >* This object is basically just a wrapper around Envelope. Futhermore, > its functionalities is similar to java.awt.geom.Rectangle2D. The > EnvelopeExtent.createIntersect method really duplicate > Rectangle2D.createIntersection. I fell that we have a fair amount > of redundancies between Extent, JTS's Envelope, OpenGIS's Envelope > and Java2D's Rectangle2D. I would like to clear this thing a little > bit. > >* Methods 'intersection' and 'difference' cast the Extent argument > to an EnvelopeExtent. Consequently, those methods will fail (throw > a ClassCastException) for any other arbitrary class of extents. > >* The algorithm for method 'difference' is to split the original > rectangle into up to 4 rectangles. In comparaison, the > java.awt.geom.Area class has a more sophesticated approach. > It is able to compute the whole shape corresponding to one > rectangle minus one other (if fact, it can compute one arbitrary > shape minus an other arbitrary shape). See the attached picture. > This Area shape is pretty powerfull, and I wonder if we should use > it instead of cooking our own solution. In general it is more useful to get back rectangles rather than a single shape, since searches based on rectangles are much faster on any practical implementation I know of. But you are right we do need to revisit the ogc envelope and our extent objects, to see what simplifications we can make. As we develop more extents this interface will mature. Ian 
From: Ian Turton <ian@ge...>  20020614 11:19:17

At 11:05 13/06/02, Martin Desruisseaux wrote: >Hello > >>In general it is more useful to get back rectangles rather than a single >>shape, since searches based on rectangles are much faster on any >>practical implementation I know of. > >Maybe, but I wonder if we should benchmark it to be sure. For example, >calling "difference" many time may result in a quick explosion of the >amount of rectangles. See attached figure for an example. Since Area try >to do an intelligent work, it is not obvious to me that the Rectangle >approach would be faster when the amount of Rectangles is big. > >If performance is the prime concern, than a more efficient algorithm with >rectangles would be: > >R1 = the orange rectangle >N1 = the first white rectangle >N2 = the second white rectangle >if (R1.contains(P) && !N1.contains(P) && !N2.contains(P)) > > >It would probably be more efficient than > >if (R1.contains(P)  R2.contains(P)  R3.contains(P)  > R4.contains(P)  R5.contains(P)  R6.contains(P)) That's not quite what I meant. In general the difference between two extents is going to be used by a datasource to return new features. So it will be quicker to say getFeatures(R[i]) [for i=0,3] than getFeatures(complex area). Obviously this is best for rectangles but still applies when working with complex polygons and their bounding boxes. >In anycase, my point is that Extend.difference shoud not returns an array >of Extent. It should returns a single Extent instead. This single Extent >may be a packageprivate implementation wrappind an array of other >Extents, or a combinaison of AND/OR/NOT operations among the line of Rob's >filters. I think in this case I prefer an array of extents rather than an opaque object, its more generalizable. >>But you are right we do need to revisit the ogc envelope and our extent >>objects, to see what simplifications we can make. As we develop more >>extents this interface will mature. > > >Two questions here: > >1) Are Extent always twodimensional? >2) Are Extent always rectangular in shape? > >If the answer is true for 1 and 2, then Extent is basically a >java.awt.geom.Rectangle2D. If 1 is false and 2 is true, then Extent is >basically a org.opengis.pt.PT_Envelope. If both 1 and 2 are false, then I >see no direct equivalence. In this last case, the Extent existence is >easier to justify. Both are false to my mind, for example an extent may be the UK in the 18th Century. > Regards, > > Martin. Ian Ian Turton, Centre for Computational Geography, School of Geography, University of Leeds, Leeds, LS2 9JT. ***0113 3433392  New Phone No*** URL: http://www.geog.leeds.ac.uk/staff/i.turton/ 
From: Martin Desruisseaux <martin.desruisseaux@te...>  20020614 11:45:13

Ian Turton wrote: > In general the difference between two > extents is going to be used by a datasource to return new features. So > it will be quicker to say getFeatures(R[i]) [for i=0,3] than > getFeatures(complex area). Obviously this is best for rectangles but > still applies when working with complex polygons and their bounding boxes. I was thinking about something along the line: Extent requestedExtent = ... Extent datasourceExtent = ... if (datasourceExtent.intersects(requestedExtent)) { // implements loading of this particular feature here } My rational was that a datasource may know the extents of any features in its backing store, so Extent.intersects(Extent) is an easy and pretty general way to figure out what to load. Furthermore, since an Extent may be nonrectangular, a getFeature(R[i]) would have to deal with complex Extent anyway, unless we specifiy in the Javadoc that all Extents are assumed to be rectangular. Neither Sun Microsystems (with their Area classes) neither OpenGIS (with the Filter packages) seems to returns an array of Area/Filter as a result of "Area.substract(Area)" or "Filter.or(Filter)" operation. Maybe there is a rational behind their choice? > I think in this case I prefer an array of extents rather than an opaque > object, its more generalizable. I see it in a different way. To me, the opaque Extent object seems more general than an array of Extents. What is the full Extent of an array? array[0].intersection(array[1]) or array[0].union(array[1])? This kind of detail would have to be said in the JavaDoc. An opaque Extent object could use whatever operation he want (AND/OR/NOT). > For example an extent may be the UK in the 18th Century. I agree with that. When I said that I see Extent as a Filter specialized in spatial conditions, I should have said in spatiotemporal conditions (time is a coordinate like space to me). But if Extent is going to encompass more conditions than time and space, what would be the difference between Extent and Filter then? Regards, Martin. 
From: Martin Desruisseaux <martin.desruisseaux@te...>  20020613 10:01:34
Attachments:
difference2.png

Hello > In general it is more useful to get back rectangles rather than a single > shape, since searches based on rectangles are much faster on any > practical implementation I know of. Maybe, but I wonder if we should benchmark it to be sure. For example, calling "difference" many time may result in a quick explosion of the amount of rectangles. See attached figure for an example. Since Area try to do an intelligent work, it is not obvious to me that the Rectangle approach would be faster when the amount of Rectangles is big. If performance is the prime concern, than a more efficient algorithm with rectangles would be: R1 = the orange rectangle N1 = the first white rectangle N2 = the second white rectangle if (R1.contains(P) && !N1.contains(P) && !N2.contains(P)) It would probably be more efficient than if (R1.contains(P)  R2.contains(P)  R3.contains(P)  R4.contains(P)  R5.contains(P)  R6.contains(P)) If we want to implement the (R1,N1,N2) algorithm instead of the (R1,R2,R3,R4,R5,R6) one, then we are going closer to Rob architecture with his Filter (AND, OR, NOT operations, etc.). It bring us to the point Rob made some time ago, that Extends are just special kind of Filters. In anycase, my point is that Extend.difference shoud not returns an array of Extent. It should returns a single Extent instead. This single Extent may be a packageprivate implementation wrappind an array of other Extents, or a combinaison of AND/OR/NOT operations among the line of Rob's filters. > But you are right we do need to revisit the ogc envelope and our extent > objects, to see what simplifications we can make. As we develop more > extents this interface will mature. Two questions here: 1) Are Extent always twodimensional? 2) Are Extent always rectangular in shape? If the answer is true for 1 and 2, then Extent is basically a java.awt.geom.Rectangle2D. If 1 is false and 2 is true, then Extent is basically a org.opengis.pt.PT_Envelope. If both 1 and 2 are false, then I see no direct equivalence. In this last case, the Extent existence is easier to justify. Regards, Martin. 