I am responding both of your emails together. > Perhaps I don't understand it. Many opclass are defined for > btree. But since (ordinary) btree handles only one-dimentional, > totally-orderable sets, geometric types even point don't fit > it. Even if we relaxed it by removing EPSILON, multidimentional > data still doesn't fit.
Yes, multidimentional data doesn't fit into btree. Let's say we would have to introduce operators called *<, *<=, *>, *>= to support btree opclass for point. I agree those operators would be useless, but btree opclass is used for other purposes too. "ORDER BY point", merge-joins, btree index support for ~= would be useful. Lack of ORDER BY, GROUP BY, and DISTINCT support is the major inconvenience about the geometric types. There are many complaints about this on the mailing list. Many frameworks and ORMs are not prepared to deal with getting an error when they use certain types on those clauses. >> - Only some operators are using the epsilon. >> >> I included the list of the ones which doesn't use the epsilon on >> initial post of this thread. This makes the operators not compatible >> with each other. For example, you cannot say "if box_a @> box_b and >> box_b @> point then box_a @> box_b". > > (It must be "then box_a @> point".) Yes, I am sorry. > Both of the operators don't > seem to use EPSILON so the transitivity holds, but perhaps we > should change them to more appropriate shape, that is, to use > EPSILON. Even having the tolerance, we can define the operators > to keep the transitivity. Yes, that would be another way. In my view, this would make things worse, because I believe epsilon approach is completely broken. The operators which are not using the epsilon are the only ones people can sanely use to develop applications. >> > - The application of epsilon is implementation dependent. >> > >> > Epsilon works between two numbers. There is not always a single way >> > of implementing geometric operators. This is surprising to the users. >> > For example, you cannot say "if box_a @> box_b then box_a <-> box_b <= >> > epsilon". >> >> Maybe it should be like "if box_a ~= box_b && box_b @< box_a then >> ..". I'm not sure off-hand. But I don't see the relationship is >> significant. What I meant was the behaviour being unclear to even people who knows about the epsilon. If two boxes are overlapping with each other, one who knows about EPSILON can expect the distance between them to be less than EPSILON, but this wouldn't be true. >> - Some operators are violating commutative property. >> >> For example, you cannot say "if line_a ?|| line_b then line_b ?|| line_a". > > Whether EPSILON is introduced or not, commutativity cannot be > assured for it from calculation error, I suppose. It can easily be assured by treating both sides of the operator the same. It is actually assured on my patch. >> - Some operators are violating transitive property. >> >> For example, you cannot say "if point_a ~= point_b and point_b ~= >> point_c then point_a ~= point_c". > > It holds only in ideal (or mathematical) world, or for similars > of integer (which are strictly implemented mathematica world on > computer). Without the EPSILON, two points hardly match by > floating point error, as I mentioned. I don't have an evidence > though (sorry), mere equality among three floating point numbers > is not assured. Of course, it is assured. Floating point numbers are deterministic. >> - The operators with epsilon are not compatible with float operators. >> >> This is also surprising for the users. For example, you cannot say >> "if point_a << point_b then point_a < point_b". > > It is because "is strictly left of" just doesn't mean their > x-coordinates are in such a relationship. The difference might be > surprising but is a specification (truely not a bug:). Then what does that mean? Every operator with EPSILON is currently surprising in different way. People use databases to build applications. They often need to implement same operations on the application side. It is very hard to be bug-compatible with our geometric types. >> = Missing Bits on the Operator Classes > This final section seems to mention the application but sorry, it > still don't describe for me what application that this patch > aiming to enable. But I can understand that you want to handle > floating point numbers like integers. The epsilon is surely quite > annoying for the purpose. I will try to itemise what applications I am aiming to enable: - Applications with very little GIS requirement PostGIS can be too much work for an application in s different business domain but has a little requirement to GIS. The built-in geometric types are incomplete to support real world geography. Getting rid of epsilon would make this worse. In contrary, it would allow people to deal with the difficulties on their own. - Applications with geometric objects I believe people could make use the geometric types in many different business areas, if they would be in better shape. I am working for a gaming company. There is great overlap between the logic of many games and the geometric types. I could support using them more, if they wouldn't be so buggy and impractical. - Demonstrating indexes We require indexing features to be committed with an example. Geometric types have served this purpose many times. Many operators are actually added to demonstrate indexes. These examples are also used by other projects like PostGIS. They can re-use part of the implementations, or the implementation as a starting point. I believe we should make those examples as clean as possible. > Ok, returning to the basis of the current geometric types, it is > described as below. It is not perfect (so needs amendment) but > achived to a certain degree. > > 1. For geometric types, equality needs to be defined with some > tolerance. Concretely an absolute value of 1E-06, which is > quite random but would be suitable to ignore error of > longitude and latitude. I don't agree this requirement as it is put. Returning true to something like "point(0.000001, 0.000001) ~= point(0.000002, 0.000002)" is obviously wrong. > 2. Translative comparisons should consider the tolerance to make > a result that does not contradict the equality. The current implementation fails to provide it: > hasegeli=# select point(0.000001, 0.000001) ~= point(0.000002, 0.000002); > ?column? > ---------- > t > (1 row) > > hasegeli=# select point(0.000001, 0.000001) << point(0.0000021, 0.0000021); > ?column? > ---------- > t > (1 row) > > hasegeli=# select point(0.000002, 0.000002) << point(0.0000021, 0.0000021); > ?column? > ---------- > f > (1 row) > 3. It is not sure about other comparsons such like parallel and > perpendicular, but it is hardly usable without any amount of > tolerance. I agree. I don't think they are useable with our tolerance either. > On the other hand, some people complains about the following. I believe have listed enough complaints on my previous post. > As a presupposition, we have the common knowlegde, or principle, > about floating point handling on a digital computer. > > X. We shouldn't detect equalty of two floating point numbers just > using '=' for real usage. It hardly works for arbitrary > numbers including results of any arithmetics, so it should > incorporate any amount of tolerance that differs among > applications. > > Sorry for some refrains from the past discussion, but the above X > and 1-3 are the immovable basis in this area. (I belive it . But > any objection are welcome) > > You might want to object that float has an equality operator, but > it is because it is an atomic type, which has no specific > purpose. On the contrary geometric types are application types, > which is assumed specific purpose and it should behave > reasonablly against the expected purpose. Are they really? We have really simple geometric types which are not for any specific kind of application. We are not claiming that they are for earth scale or any other scale. I think we should aim of making them predictable, extensible, as general purpose as possible to let people use them for their purpose. > That being said, if we want to, for example, use btree index for > each coordinate of geometric types, it is doable by normalizing > the values before applying operators, instead of applying epsilon > arbitrarily in operators. > > Normalization may be done both on storing or on-the-fly just > befor usage. It depends on whether we want to preserve precision > of stored values. If we want, normalization should be done just > before comparisons, or on creating indexes. > > I don't know much about the normalization method for floating > point numbers but libgeos might give some hints. Me neither. I have been told that storing the minimum and and maximum possible value is a good strategy for tolerance. Then all operators can return true, false, or maybe. This would be a much bigger and incompatible change that I don't think I can implement. We cannot come into an agreement. Geometric types are not well maintained. I am trying my best to put them into a shape. Please help me do that. Let's try to find a way to leave them better than we found. -- Sent via pgsql-hackers mailing list (email@example.com) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers