1

The following code says that c1 == c2 and c2 == c3, but c1 != c3.

TOL = 0.11

class C:
    def __init__(self, x):
        self.x = x

    def __eq__(self, other):
        return abs(self.x - other.x) <= TOL

c1 = C(1.1)
c2 = C(1.2)
c3 = C(1.3)

print(c1 == c2)  # True
print(c2 == c3)  # True
print(c1 == c3)  # False

For the same reason the shape in the middle in the image below could be equal to all the other shapes, while no other shape would be equal to all the others.

Slightly different "rectangles"

No matter how small or large the tolerance is, there will always be an angle for the top line of the shapes where the problem arises.

I need to find a reliable way to match the shapes so that when c1 == c1 once, c1 == c1 always. In the example above I can accept that either c2 == c3 or c2 != c3, but whatever is the case, it has to be (1) consistent during the execution and (2) consistent with other comparisons.

If I tighten the tolerance, then no shapes will ever be equal to other shapes, because of the small errors introduced by transformations.

If I loosen the tolerance, then all the shapes will be identical, which is not good.

Perhaps there is a comparison algorithm that remembers the first instance of each value ever compared, and creates a bucket for it? So that in my first example, if I compare c1 to c2 first then the reference value will be 1.1 and c2 will be different from c3, but if i compare c2 to c1 first then the reference value will be 1.2 and they all will be equal.

Is there a way to avoid this problem?

  • Not sure if I understand what problem you are really trying to avoid here, but it sounds like the answer would be to tweak your tolerance, maybe? – Becuzz Nov 4 '16 at 14:59
  • 3
    @Becuzz These problems will, by definition, exist for any possible tolerance value other than 0 or infinity. – Servy Nov 4 '16 at 15:07
  • @Becuzz I added some details about what I am looking for – stenci Nov 4 '16 at 15:09
  • I don't think you can maintain transitivity (see Servy's answer) in this design but you say that you need it. Why do you think you need that? – JimmyJames Nov 4 '16 at 15:20
  • On a second read, perhaps you want a histogram? – JimmyJames Nov 4 '16 at 15:21
1

I think maybe you want something like a histogram but where the categories are based on the data you find and the order in which you find it. It's key to understand that the categories will not be guaranteed to be evenly spaced across the domain as is normally the case in a histogram.

categories = []

def categorize(shape):
  index=0

  for c in categories:
    if c.withinTolerance(shape):
      return c
    elif c.largerThan(shape):
      categories.insert(i, shape)
      return shape

    index += 1        

  categories.append(shape)
  return shape

def equalish(a, b):
  return categorize(a) == categorize(b)

Then based on the 'anchor' for your category based on the above, you can create an equals (although I agree with @Servy that this a different name should be used.)

EDIT

This is a working example that shows how it is consistent (within a session).

TOL = 0.11

class C:
    categories = []

    def __init__(self, x):
        self.x = x

def _compare(self, other):
    return abs(self.x - other.x) < TOL

def __eq__(self, other):
    for c in self.categories:
        self_equal_c = c._compare(self)
        other_equal_c = c._compare(other)
        if self_equal_c or other_equal_c:
            return self_equal_c and other_equal_c
    self.categories.append(self)
    return self._compare(other)

a = C(1.1)
b = C(1.2)
c = C(1.3)

print('a == c', a == c)
print('a == b', a == b)
print('a == c', a == c)
print('b == c', b == c)

This solution is slightly better than an histogram when only two elements are compared because an histogram would make two elements different when they sit in two different buckets even if their distance is below the tolerance.

This solution is much better than an histogram when more than one property are compared. If the class C had more than the one field (as it has in the example above) then using the histogram would cause almost all the elements to be different.

  • The problem with this solution is that the order affects the result. For example (shape2==shape3)=True if it follows (shape2==shape1), not if it follows (shape1==shape2). But as long as the categories collection lives long enough across the comparisons this will work. – stenci Nov 4 '16 at 15:53
  • @stenci Maybe I misunderstand what is meant by "remembers the first instance of each value ever compared, and creates a bucket for it". As noted in the answer, the behavior will absolutely be defined by the order the elements have been encountered but I thought that's what you were looking for. – JimmyJames Nov 4 '16 at 15:57
  • You did understand very well! I was just adding a comment to your answer for the posterity :) – stenci Nov 4 '16 at 16:36
  • This doesn't actually solve the problem of the equality check not being transitive. What's worse, if you write, A == B then B == C then A == C you could get a different result than if you write A == C, so not only is this not transitive, but the same comparison doesn't always produce the same result. And if you add enough values, in the right order, eventually, everything is equal to everything. You can even have values compare as equal, then be considered unequal later, by adding new objects in the right way. – Servy Nov 4 '16 at 17:34
  • @Servy I didn't ask for it to be transitive, I asked for it to be consistent with other comparisons and within the session. Yes, comparing A to B depends on what has been previously compared and will not be consistent between two sessions, but it will be consistent in the same session. And no, everything is not equal to everything (with an implementation more refined than this snippet) – stenci Nov 4 '16 at 18:05
4

You should avoid overriding an objects implicit equality when using a tolerance. Expose a specific method or comparer object that compares the objects using a tolerance (and is very clear about that in it's name/documentation). The object's own implicit equality should remain transitive, which this implementation doesn't meet.

By doing this you ensure that anyone using this method of comparison is aware of the fact that it doesn't maintain all of the properties of a traditional equality comparison, and that they should only use it in a context where that is okay, and you ensure that people using implicit equality don't have their expectations violated about how it behaves.

  • 1
    +1 no developpers will accept the have some object for which = is transitive and for some it's not. This would just be a mess. – Walfrat Nov 4 '16 at 15:26
  • 1
    I agree. My objects often have many comparison operators, sometimes with optional parameters, for example: shape1.equal(shape2, allow_rotation=True, allow_mirroring=False) – stenci Nov 4 '16 at 15:28
0

You're asking the impossible. You either match exactly or you match with a tolerance. You can't do both at the same time.

0

Having read your use case, I can think of one way to deal with this. I understand you always start out with one shape that may be translated and/or copied a couple of times. Why not keep an origin property attached to the shape and compare that instead of the shape itself? If two shapes have the same origin, they must be equal no matter how many times they have been resized or rotated. When a shape is copied it gets the origin id of its template. New shapes get new origin ids.

  • The input is a cad drawing with hundreds of shapes. Some shapes have been created by copying/rotating/mirroring existing shapes and are slightly different from the original because of errors introduced during the transformation. The function needs to find out which ones are identical. Creating a list of "categories" is the correct solution for me. – stenci Nov 5 '16 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.