DS&A

Simple Shapes

The most primitive geometric objects are points and vectors. But real geometric problems involve shapes like rectangles, triangles, circles, and polygons — or more complex collections of shapes, such as 3D models made of many polygons. In this post we’ll consider how computers can represent some simple kinds of shapes, and solve problems using these representations.

As before, to keep it simple we’ll only consider 2D shapes. The problem we’ll solve is a simple but important one — testing whether a shape contains a point. This is a realistic problem in many applications:

• When you click on a rectangular button in a GUI application, the program has to test whether the point you clicked is inside the rectangle or not.
• When a web browser detects that the mouse position is over a hyperlink, it changes the cursor to indicate the link can be clicked.
• In games and physics simulations, when a point is inside a shape, a collision has occurred.

We’ll consider axis-aligned rectangles and circles.

Rectangle

A rectangle is axis-aligned if two of its sides are exactly horizontal, and the other two are exactly vertical:

In most applications, rectangles are always axis-aligned; for example, buttons and other GUI components, raster images and hitboxes in games. So we usually assume that “rectangle” means “axis-aligned rectangle” unless otherwise stated.

Top-left, bottom-right

One common way to represent a rectangle is with two points: the top-left corner and the bottom-right corner. These determine everything about the rectangle’s shape and position:

To represent this in code, we can define a Rectangle class:

class Rectangle:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2
    def __repr__(self):
        fmt = 'Rectangle({!r}, {!r})'
        return fmt.format(self.p1, self.p2)

The fields p1 and p2 hold the top-left and bottom-right corners respectively. These should be points or vectors.

This is not the only way to represent a rectangle — for example, we could instead store the top-left corner, the width and the height.

Operations

For a Rectangle to be useful, we want to be able to do things with it. There’s no standard set of available operations, but some of the common ones are:

• Create a rectangle with given top-left and bottom-right corners.
• Get the width.
• Get the height.
• Get the area.
• Test whether the rectangle contains a given point.
• Test whether the rectangle overlaps another rectangle.
• Translate the rectangle by a given vector.

Rectangles are not complicated, and these operations are all straightforward to implement. We’ll just consider the contains operation for now.

Point-in-rectangle

Let’s specify the problem:

• Problem: test whether a rectangle contains a given point.
  • Input: a rectangle, represented by its top-left and bottom-right corners.
  • Input: a point.
  • Output: a Boolean indicating whether the point is in the rectangle.
• Example:
  Rectangle(Point(1, 2), Point(5, 6)) does contain Point(3, 4).
• Example:
  Rectangle(Point(1, 4), Point(5, 6)) does not contain Point(3, 2).

It might help to draw diagrams for these examples to make sure they’re correct.

This is the kind of problem which is obvious to humans — we can just look and see whether the point is in the rectangle or not. Unfortunately, computers cannot use visual judgement to solve problems; our data structures represent points and rectangles using numbers, so the algorithms must work using only those numbers.

The key idea is to test that the point’s x is in the correct range, and also that y is in the correct range. Consider the model below:

For x to be in range, it must be between p1.x and p2.y. The condition for y to be in range is similar. Here’s an implementation in Python:

class Rectangle:
    # ...
    def contains(self, point):
        return (
            self.p1.x <= point.x and point.x <= self.p2.x
        ) and (
            self.p1.y <= point.y and point.y <= self.p2.y
        )

We have made a choice here — by comparing with <=, we count points on the boundary as being inside the rectangle. Whether or not this is correct will depend on the situation.

Try it out; you’ll need the Point class defined in the previous post:

>>> rectangle1 = Rectangle(Point(1, 2), Point(5, 6))
>>> rectangle1.contains(Point(3, 4))
True
>>> rectangle2 = Rectangle(Point(1, 4), Point(5, 6))
>>> rectangle2.contains(Point(3, 2))
False
>>> rectangle2.contains(Point(3, 4))
True

Circle

A circle can be defined by a center(1) point and a radius:

To represent this in code, let’s define a Circle class:

class Circle:
    def __init__(self, center, radius):
        self.center = center
        self.radius = radius
    def __repr__(self):
        fmt = 'Circle({!r}, {!r})'
        return fmt.format(self.center, self.radius)

The center should be a point or vector, and the radius should be a number.

Operations

Here are some operations a circle might support:

• Create a circle with a given center and radius.
• Get the diameter.
• Get the area.
• Test whether the circle contains a given point.
• Test whether the circle overlaps another circle.
• Get the minimum bounding rectangle.(2)
• Translate the circle by a given vector.

These are all straightforward to implement. For now, we’ll just consider the contains operation.

Point-in-circle

Let’s specify the problem; in this case it’s convenient to represent the points as vectors.

• Problem: test whether a circle contains a given point.
  • Input: a circle, represented by its center vector and radius.
  • Input: a point, represented as a vector.
  • Output: a Boolean indicating whether the circle contains the vector.
• Example: Circle(Vector(3, 4), 5) contains Vector(1, 1).
• Example: Circle(Vector(5, 5), 4) does not contain Vector(1, 2).

Again, it’s a good idea to draw diagrams to make sure the examples are correct.

To solve this problem computationally, we need to find the distance of the point from the circle’s center. If this distance is bigger than the circle’s radius, then the point is not in the circle.(3)

Using vectors, this is straightforward: the distance between two points is the length of the vector from one to the other. Here’s an implementation in Python:

class Circle:
    # ...
    def contains(self, vector):
        distance = vector.subtract(self.center).length()
        return distance <= self.radius

Try it out; you’ll need the Vector class from the previous post.

>>> circle1 = Circle(Vector(3, 4), 5)
>>> circle1.contains(Vector(1, 1))
True
>>> circle2 = Circle(Vector(5, 5), 4)
>>> circle2.contains(Vector(1, 2))
False

Footnotes

1. Most libraries and APIs use the American spelling “center” rather than the British spelling “centre”.
2. This will always be a square.
3. Again, we arbitrarily choose to count points on the boundary as “inside” the circle.

• Tags: 
• geometry, data structures, algorithms