Technical Exam - Simple 2D Coordinate Library

This technical exam question revolves around writing a quick library to handle working with some shapes in a Cartesian coordinate system:

Create a small object-oriented PHP library for working with primitive geometric shapes.

1. It should support 2D points, circles and polygons.
2. You only need to implement two operations: scaling and translating. Scaling should expand or contract the shape relative to the origin, translating should move the shape.
3. No libraries or build processes, keep everything in one self-contained file, even if it contains several classes.

You do not need to output anything, but please include several usage examples and an analysis of your work and design.

Initial Notes

Let's break this down into some basic points we can start working with:

Shapes

• Primitive polygons are an array of coordinates, where the first and last coordinate must be the same, otherwise the shape is not enclosed and therefore is invalid. Optionally we could append the first coordinate to the end of the array and close the shape for the user.
• There are 3 different types of elements we need to support, Circles, Polygons, and Points.

• There are 3 different types of elements we need to support, Circles, Polygons, and Points.
  • Points are the most basic shape available.
  • Circles are just points with additional info (radius)
  • Polygons are an array of points.

Scale

Scaling involves expanding or shrinking the area of the object based on its origin.

• Point
  • Scaling a point has no effect, since a single point has no area.
• Circle
  • Scaling a circle modifies the radius property of the object.
• Polygon
  • Scaling a polygon requires multiplying the difference between the location of the point and the origin by the scaling value, then adding the location of the origin back into the result. This needs to be done for each point in th array.

Translate

Translating an object requires moving the position of it by an x and/or y value.

• Point
  • Simple addition.
• Circle
  • No difference between scaling a point and a circle.
• Polygon
  • Apply the transformation to each point in the array.

Architecture

Overall, each different shape needs to support both the scale and the translate functions, and we will probably want some sort of __toString() implementation for debugging. Looking at our notes on the scaling of a polygon, we're also going to need to be able to retrieve the origin of an object, so we'll need a getOrigin() function. This makes the "plottable" shapes candidates to implement a basic interface to guarantee the functionality is available. That interface looks like:

Additionally, a scale operation requires both an x and a y property to function (although they can be 0). Similarly, every point that makes up a shape in our list of needed functionality requires one or more sets of x and y coordinates. To validate that the parameters being used are all valid for our graph, we can pass a Coordinate object around for each location or translation, since a point can be thought of as a vector from the point of origin (0, 0).

Interface

The Plottable interface represents any shape that we are able to "plot" on our Cartesian coordinate system. The Point, Circle, and Polygon classes will all implement this interface.

interface Plottable
{
    public function scale(float $scale): void;
    public function translate(Coordinate $translate): void;
    public function getOrigin(): Coordinate;
    public function __toString(): string;
}

This ensures that the two functions we need to be able to call on each shape (scale and translate) are available, as well as the getOrigin function for use in both the scale and the __toString() functions and the __toString() function itself for showing output in tests and debugging.

Plottable

The first class to implement is the Plottable class, which represents any plottable point in our Cartesian coordinate system. Since a set of Cartesian coordinates consist of an x and a y position, the Plottable class will need properties to match. Additionally you can't have a plottable point on our coordinate system without both of these positions, so they need to be provided when the class is initialized.

class Coordinate
{
    private $xPosition;
    private $yPosition;
    
    public function __construct (float $x, float $y)
    {
    	$this->xPosition = $x;
        $this->yPosition = $y;
    }
}

Since the $xPosition and $yPosition variables are private to promote encapsulation, we also need get and set methods for them:

public function setX(float $x): void
{
    $this->xPosition = $x;
}

public function setY(float $y): void
{
    $this->yPosition = $y;
}

public function getX(): float
{
    return $this->xPosition;
}

public function getY(): float
{
    return $this->yPosition;
}

Leaving us with two functions left to define: we need to support moving the coordinate based on another Coordinate object (translate), and moving the coordinate based on a point of origin and a scale value (scale).

the translate function requires adding a new value to both the positionX and the positionY properties, from the passed Coordinate object. Since we have both set and get methods available, it's simple addition:

public function translate(Coordinate $translate): void
{
    $this->setX($this->xPosition + $translate->getX());
    $this->setY($this->yPosition + $translate->getY());
}

For example, if we have an instance of Coordinate at (2, 2) of our system:

$plot = new Coordinate(2, 2);

We can then move it 2 units to the right with:

$plot->translate(new Coordinate(2, 0));

For scaling, we know we're going to have 2 additional pieces of information available to us in additon to the properties of the Coordinate instance:

• The point of origin
• The % to scale by

Therefore to scale, we need to calculate the distance between the X and Y axis of the point of origin and our Coordinate object, multiply both distances by the scale value, and then move the Coordinate object to that new location (calculated value plus the offset of the point of origin). This looks like:

public function scale(Coordinate $pointOfOrigin, float $scale): void
{
    $this->setX((($this->xPosition - $pointOfOrigin->getX()) * $scale) + $pointOfOrigin->getX());
    $this->setY((($this->yPosition - $pointOfOrigin->getY()) * $scale) + $pointOfOrigin->getY());
}

Functionally, it's usage looks like:

$plot = new Coordinate(2, 2);
$plot->scale(new Coordinate(1, 1), 2);

// $plot is now at (3, 3)

Shapes

Recapping, we have 3 shapes to implement:

• Points
• Circles
• Polygons

All shapes are plottable on our system, so they all implement the Plottable interface we have already defined.

Point

The only data relevant to a point is its point of interest, as that is all it is, a single point. That value must be supplied when initialized in the form of a Coordinate:

Class Point implements Plottable
{
    private Coordinate $pointOfOrigin;
    
    public function __construct(Coordiante $point)
    {
        $this->pointOfOrigin = $point;
    }
}

With only have 1 point to keep track of, we can return it as our point of origin:

    public function getOrigin(): Coordinate
    {
        return $this->pointOfOrigin;
    }

Since our $pointOfOrigin is an instance of Coordinate, we can use the Coordinate implementation of translate to move our point:

    public function translate(Coordinate $translate): void
    {
        $this->pointOfOrigin->translate($translate);
    }

Scaling a single point isn't possible. By definition a point has no area to scale, and therefore any scale applied to it should have no effect. If this was a production environment I might consider raising a warning of some sort to let the user know they were doing something that had no effect, but that isn't in scope for this question. Instead, I chose to return a void value with no other side effects.

    public function scale(float $scale): void
    {
        return;
    }

This is also a good time to mention the __toString() function. For our purposes, all we care about is verifying the properties of the object. We could use var_dump() for this, but it outputs a multi-lined representation of the data. Instead, lets write our our JSON encoded output so we can compare easier at a glance:

    public function __toString(): string
    {
        return json_encode(array(
            "pointOfOrigin" => $this->pointOfOrigin->__toString()
        ));
    }

Circle

The circle class is going to be very similar to the Point class, except it has the additional property of a radius. Otherwise, as far as we are concerned so far, everything is going to be the same. Therefore with one modification to Point we can inherit from the Point class and only modify the functions that need change:

Line 3 of the Point class:

private Coordinate $pointOfOrigin;

Now becomes:

protected Coordinate $pointOfOrigin;

So that we can access it from a child object, such as our new Circle class:

class Circle extends Point
{
    private float $radius;
    public function __construct(Coordinate $point, float $radius)
    {
        $this->pointOfOrigin = $point;
        $this->radius = $radius;
    }

     public function __toString(): string
    {
        return json_encode(array(
            "pointOfOrigin" => $this->pointOfOrigin->__toString(),
            "radius" => $this->radius
        ));
    }
}

Unlike a Point, it is possible to scale a circle - the radius property controls the area of the circle. Therefore the scale value should modify the radius property:

public function scale(float $scale): void
{
    $this->radius = $this->radius * $scale;
}

Since we now have two properties that are set per object, we need to make sure we have access to both of them in the __toString() function.

public function __toString(): string
{ 
    return json_encode(array(
        "pointOfOrigin" => $this->pointOfOrigin->__toString(),
        "radius" => $this->radius
    ));
}

Polygon

Unlike Point or Circle, Polygon needs to handle an array of different Coordinate objects to make up its shape. To translate a Polygon instance, the translation then needs to be applied to each of the points that make up the shape. Additionally, a Polygon instance can be initialized in two possible ways that are invalid: The first being already mentioned where the first and last point of the array of Coordinates are not the same point in our system, and secondly PHP does not support type checking the internal contents of an array.  Therefore we need to perform both of those checks ourselves when initializing the object.

class Polygon implements Plottable
{
    private Coordinate $pointOfOrigin;
    private array $coordinates;

    public function __construct(array $coordinates)
    {
        $this->isValidCoordinates($coordinates);
        $this->isClosedShape($coordinates);

        $this->coordinates = $coordinates;
        $this->pointOfOrigin = $this->coordinates[0];
    }

Here we have our two conditions we need to check for, isValidCoordinates and isClosedShape. Both of these are simple checks that should throw an Exception if the data is not valid. Since proper exception handling and reporting is outside the scope of the assignment, we'll throw instances of the base Exception class.

In a different language like Python, there is built-in support for "typing" the contents of a list or set. for example, the following is valid in Python 3.5+:

from typing import List

def is_valid_coordinates(points: List[Coordinates]):
	...

Where the function is_valid_coordinates is expecting a list containing one or more of the Coordinate object as its argument.

In PHP, there is no support for this. It was proposed for PHP 5.6, but did not make it as a feature and has not been reintroduced in a new/updated RFC. So instead we have to check ourselves afterwards.

private function isValidCoordinates(array $coordinates): void
{
    foreach ($coordinates as $key => $point) {
        if (!$point instanceof Coordinate) {
            throw new \Exception("Polygon must be made up of an array of Coordinates, non-coordinate found at position {$key}");
        }
    }
}

For our isClosedShape call, we need to confirm that the first and last element of the array are the same position on our coordinate system. This could be done by comparing them using the comparison operator (==), but I elected not to use that method incase I tripped myself up needing to make future changes to the class. Instead, comparing the output of the __toString() method on both objects allows me to control which values are considered in the comparison.

private function isClosedShape(array $coordinates): void
{
    if ($coordinates[0]->__toString() !== $coordinates[count($coordinates) - 1]->__toString()) {
        throw new \Exception('Polygon must be an enclosed shape, but the first and last point are not equal.');
    }
}

As previously mentioned, the "big" difference this time around is that we need to apply a translation to each individual point that makes up our Polygon instead of just the point of origin. Thankfully that's an easy change.

public function translate(Coordinate $translate): void
{
    foreach ($this->coordinates as $coordinate) {
        $coordinate->translate($translate);
    }
}

One thing to note about this change is that despite not updating the pointOfOrigin property of the class, because we set it to the first point in the array in the constructor with

$this->pointOfOrigin = $this->coordinates[0];

and  $this->coordinates[0] is a object, $this->pointOfOrigin is a reference to the same object. This would not be true if we were not using an object to represent the points and we would have to also apply the translation to the pointOfOrigin property.

Finally, we need to add the scaling function. As we wrote in the Coordinate class, we need to provide the point of origin and the scale value for each point. Thanks to our overall design, this should properly scale any shape we can create with this Polygon class:

public function scale(float $scale): void
{
    foreach ($this->coordinates as $coordinate) {
        $coordinate->scale($this->pointOfOrigin, $scale);
    }
}

And once again, we now have potentially many more pieces of data that need to be displayed in our _toString() function.

public function __toString(): string
{
    $output = array(
        "pointOfOrigin" => $this->pointOfOrigin->__toString()
    );
    $output['points'] = array();
    foreach ($this->coordinates as $key => $coordinate) {
        $output['points'][$key] = $coordinate->__toString();
    }
    return json_encode($output);
}

Tests

The last section of the original question includes:

You do not need to output anything, but please include several usage examples and an analysis of your work and design.

To do this, I kept all of my debugging steps in a separate file while writing the library. It's not the most elegant example in the world but it serves its purpose. That file is included below.

Conclusion

Overall, I think this was a great technical interview question for a vanilla PHP deceloper position. It allowed the interviewee to show their understanding of many different concepts without forcing them to do so, which usually provides a more natural coding example like they would write in the work place.

Extensions

As always, I like including possible extensions or further work that could be done, hoping to highlight some of the design decisions that are present in the answer.

How would you go about allowing a custom point of origin to be provided for a Polygon? For example, some people like the center of a square to be the point of origin.

What are some additional shapes that you could build by inheriting from the Polygon class? What would the implementation of a Triangle, a Square, or a Rectangle look like?

What would be involved in modifying the library to allow scaling by the X or Y axis individually? Are there any other functions that would become trivial to implement as a result?

Source Code