CODEWITHSUNDEEP
python
Rand Akterson
Rand Akterson

Reputation: 11

How to create an intersection function?

I am making a 1 dimensional interval where I have to check if self intersects another object.

Here is what i have so far:

def __init__(self, lbound, rbound):
    """
    Constructs a new interval given its lower and upper bounds.
    """

    self._lbound = lbound
    self._rbound = rbound

And this is my function:

def intersects(self, other):
    """
    Returns True if self intersects other and False othewise.
    """

    s1 = set([self._lbound, self._rbound])
    s2 = set([other._lbound, other._rbound])
    if s1.intersection(s2) and s2.intersection(s1):
        return True

The problem is this function only gives half the answer I want, whats a better way to check if self intersects other?

Upvotes: 1

Views: 214

Answers (2)

Greg Navis
Greg Navis

Reputation: 2934

You can certainly implement this predicate with inequalities. The downside of this approach is poor readability and a high likelihood of making a mistake. I recommend you break this problem down into two subproblems:

  1. Intersecting two intervals.
  2. Checking whether an interval is empty.

I assume that you're using open intervals. If not, please adjust the code accordingly.

Constructing the code

First, let's have a class for representing intervals:

class Interval(object):
    def __init__(self, lhs, rhs):
        self.lhs = lhs
        self.rhs = rhs

An empty interval will be represented as one with lhs >= rhs (which also makes sense from the mathematical point of view). Let's add a predicate that checks whether an interval is empty:

    def is_empty(self):
        return self.lhs >= self.rhs

Let's turn our attention to intersections. An intersection of two intervals is an interval (possibly empty). The left and right endpoints can be computed with min and max like this:

    def intersect(self, other):
        return Interval(max([self.lhs, other.lhs]), min([self.rhs, other.rhs]))

As a last step, let's add __repr__ so that we'll be able to print the interval and see its endpoints:

    def __repr__(self):
        return 'Interval(%r, %r)' % (self.lhs, self.rhs)

Checking for non-empty intersections

The operation you're trying to perform can be expressed as:

a.intersect(b).is_empty()

where a and b are two Intervals.

Full source

I'm including the full source for your convenience.

class Interval(object):
    def __init__(self, lhs, rhs):
        self.lhs = lhs
        self.rhs = rhs

    def is_empty(self):
        return self.lhs >= self.rhs

    def intersect(self, other):
        return Interval(max([self.lhs, other.lhs]), min([self.rhs, other.rhs]))

    def __repr__(self):
        return 'Interval(%r, %r)' % (self.lhs, self.rhs)

Upvotes: 1

Francisco
Francisco

Reputation: 11476

You probably want something like this instead:

def intersects(self, other):
    return (other._lbound < self._lbound < other._rbound or
            other._lbound < self._rbound < other._rbound or
            self._lbound < other._lbound < self._rbound or
            self._lbound < other._rbound < self._rbound)

Upvotes: 2

Related Questions