## Simple Shapes

Apr 232018The 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:

Left: an axis-aligned rectangle. Right: a rectangle which is not axis-aligned.

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
```

## There are no published comments.