Written by Pete Corey on Jul 20, 2016.

The goal of today’s
kata
is to implement a function called `pointInPoly`

. `pointInPoly`

is
called with a polygon represented as a series of points as the first
argument, and a single point at the second argument. Each point is
represented as a set of `[x, y]`

coordinates, where both `x`

and `y`

are
numbers. `pointInPoly`

should return `true`

if the point is within the
defined polygon, and `false`

if it is not.

The kata description points out several assumptions we can make about
the inputs: 1) The polygon will be a valid simple polygon. That is, it
will have at least three points, none of its edges will cross each
other, and exactly two edges will meet at each vertex. 2) In the tests,
the point will never fall exactly on an edge of the polygon.

And lastly, although the description never explicitly says so, we’re
assuming that the points in the polygon are given in order; each point
shares an edge with the next.

This initial commit sets up our initial project.

.babelrc

```
+{
+ "presets": ["es2015"]
+}
```

.gitignore

```
+node_modules/
```

package.json

```
+{
+ "main": "index.js",
+ "scripts": {
+ "test": "mocha ./test --compilers js:babel-register"
+ },
+ "dependencies": {
+ "babel-preset-es2015": "^6.9.0",
+ "babel-register": "^6.9.0",
+ "chai": "^3.5.0",
+ "lodash": "^4.12.0",
+ "mocha": "^2.4.5"
+ }
+}
```

test/index.js

```
+import { expect } from "chai";
+
+describe("index", function() {
+
+ it("works", function() {
+ expect(2+2).to.equal(4);
+ });
+
+});
```

The first thing we do when we’re solving a problem like this is to write
a test. Because we’re implementing a function given to us, we already
know what our final interface will look like (`pointInPoly`

), so we can
immediately write a test for it.

Our first test asserts that a point at the origin (`[0, 0]`

) is within a
simple triangle with points at `[-1, -1]`

, `[1, -1]`

, and `[0, 1]`

.

After writing this test, our test suite complains that ```
pointInPoly is
not defined
```

. This is quickly fixed by importing `pointInPoly`

into
our test file and then exporting it from `index.js`

.

After exporting the empty `pointInPoly`

function, the test suite shouts
that it `expected undefined to be true`

. To bring us back to green we
change our new `pointInPoly`

function to return `true`

.

index.js

```
+export function pointInPoly(poly, point) {
+ return true;
+}
```

test/index.js

```
import { expect } from "chai";
+import { pointInPoly } from "../";
-describe("index", function() {
+describe("pointInPoly", function() {
- it("works", function() {
- expect(2+2).to.equal(4);
+ it("detects a point in a triangle", function() {
+ let poly = [[-1, -1], [1, -1], [0, 1]];
+ expect(pointInPoly(poly, [0, 0])).to.be.true;
});
```

We knew that our initial `pointInPoly`

solution was incomplete.
Returning `true`

for all cases obviously wasn’t going to work.
But what do we do instead? How do we even begin to tackle this
problem?

Thankfully, from my days of video game programming I know that a simple
test
for checking if a point lies within a polygon is to send a ray outward
from that point. If the ray intersects with the lines of the polygon an
odd number of times, the point lies within the polygon. Otherwise, it’s
outside.

Since we’re in a green state, we can do a little refactoring and
implement a high level version of this solution. We want to count the
number of intersections between our imaginary ray and our polygon:

```
let intersections = countIntersections(poly, point);
```

And then return `true`

if that count is odd, or `false`

if it’s even:

```
return !!(intersections % 2);
```

After making these changes, our test suite complains that
`countIntersections`

does not exist, so let’s quickly define it and have
it return `1`

to bring us back to green.

index.js

```
+function countIntersections(poly, point) {
+ return 1;
+}
+
export function pointInPoly(poly, point) {
- return true;
+ let intersections = countIntersections(poly, point);
+ return !!(intersections % 2);
}
```

After some soul-searching, I decided I wasn’t happy with where we were
going with our previous solution. `countIntersections`

was really an
“internal method”. Outside of the context of our point-in-polygon
problem, a function called `countIntersections`

that takes in a `poly`

and a `point`

really just doesn’t make any sense.

Because it was an internal method, I was hesitant to write tests for it.
These tests would be too closely coupled with our implementation, and
would make refactoring difficult. Additionally, `countIntersections`

would most likely call other methods would be even more contextually
dependant and awkward to test.

We needed a cleaner solution.

After reconsidering the problem, it’s clear that we’re dealing with a
few really solid abstractions. The most apparent is a `polygon`

. If we
implement a generic `polygon`

, we’d be able to cleanly specify what we
want from our `pointInPoly`

method:

```
function pointInPoly(poly, point) {
return polygon(poly).surrounds(point);
}
```

Additionally, by breaking `polygon`

out into a new abstraction, we can
freely build and test its interface to our heart’s content.

With this in mind, we wrote a new set of tests that describe `polygon`

.
The first tests looks nearly identical to our `pointInPoly`

tests and
checks if a polygon surrounds a point.

Our dummy implementation of `polygon.surrounds`

simply returns `true`

.

polygon.js

```
+export function polygon(_points) {
+
+ let surrounds = (point) => true;
+
+ return {
+ surrounds
+ };
+}
```

test/polygon.js

```
+import { expect } from "chai";
+import { polygon } from "../polygon";
+
+describe("polygon", function() {
+
+ it("checks if a polygon surrounds a point", function() {
+ let poly = polygon([[-1, -1], [1, -1], [0, 1]]);
+ expect(poly.surrounds([0, 0])).to.be.true;
+ });
+
+});
```

Now that we’ve defined our `polygon`

, we can restate our
implementation of `surrounds`

. We want to `translate`

our polygon so
that the `point`

we’ve been given can be treated as the origin. Next
we want to count the number of intersections that an arbitrary ray
(`[0, 1]`

) makes with the newly translated polygon:

```
let intersections = translate([-x, -y]).intersections([0, 1]);
```

Lastly we want to return `true`

from `surrounds`

if `intersections`

is
odd:

```
return !!(intersections % 2);
```

After making these changes, our test suite complains about `translate`

and `intersections`

not being defined.

The fastest way to get us back to green is to have `translate`

return a
new `polygon`

, and have `intersections`

return `1`

.

polygon.js

```
...
- let surrounds = (point) => true;
+ let surrounds = ([x, y]) => {
+ let intersections = translate([-x, -y]).intersections([0, 1]);
+ return !!(intersections % 2);
+ };
+
+ let translate = ([x, y]) => {
+ return polygon(_points);
+ };
+
+ let intersections = (ray) => 1;
return {
- surrounds
+ surrounds,
+ translate,
+ intersections
};
```

Now we can start testing the component pieces of our `surrounds`

function.

First up, let’s write a test for `translate`

. A straight-forward base
case for `translate`

asserts that calling `translate`

on an empty
polygon (`[[]]`

) should return an empty polygon.

After writing this test, I realized that I needed a function to return
the points from a polygon. Thus, `points`

was born.

```
let points = () => _points;
```

Suprisingly, our naive solution also works for all calls to translate
where `x`

and `y`

are zero.

polygon.js

```
...
+ let points = () => _points;
+
return {
...
translate,
- intersections
+ intersections,
+ points
};
```

test/polygon.js

```
...
+ it("translates a polygon", function() {
+ expect(polygon([]).translate([0, 0]).points()).to.deep.equal([]);
+ });
+
});
```

Adding a more complicated test of `translate`

shows that we need a
better solution. Thankfully, it isn’t a huge leap to come up with the
final form of the function.

The `translate`

function returns a new `polygon`

where every point in
the polygon has been incremented by the provided `x`

and `y`

values.

polygon.js

```
...
let translate = ([x, y]) => {
- return polygon(_points);
+ return polygon(_points.map(p => [p[0] + x, p[1] + y]));
};
```

test/polygon.js

```
...
expect(polygon([]).translate([0, 0]).points()).to.deep.equal([]);
+ expect(polygon([
+ [0, 0], [5, -5]
+ ]).translate([1, 1]).points()).to.deep.equal([
+ [1, 1], [6, -4]
+ ]);
});
```

Now we turn out attention to the `intersections`

function. This still
seems like a daunting piece of functionality, and we should break it
down into simpler pieces, if possible.

If we’re not afraid of making use of another abstraction (`line`

), a
simple implementation of `intersections`

could be written like this:

```
return lines().filter(line => line.intersects(ray)).length;
```

In plain english, this reads as “return the number of lines in this
polygon that intersect the given ray”.

This is a nice solution. To make it a reality, let’s create a new set
of tests for our new `line`

abstraction and a dummy implementation of
`line`

and `line.intersects`

.

line.js

```
+export function line(a, b) {
+
+ let intersects = (ray) => true;
+
+ return {
+ intersects
+ };
+}
```

test/line.js

```
+import { expect } from "chai";
+import { line } from "../line";
+
+describe("line", function() {
+
+ it("checks if the line intersects a ray", function() {
+ expect(line([0, 1], [1, 0]).intersects([1, 1])).to.be.true;
+ });
+
+});
```

Adding another test against `line.intersects`

shows that we need a
better solution.

Determining if a line intersects with a ray is a well-documented
problem. I used this blog
post
as a guide for implementing my solution. Be sure to check it out for
details on the math being used here.

line.js

```
...
- let intersects = (ray) => true;
+ function cross(v1, v2) {
+ return (v1[0] * v2[1]) - (v1[1]*v2[0]);
+ }
+
+ function dot(v1, v2) {
+ return v1[0] * v2[0] + v1[1] + v2[1];
+ }
+
+ let intersects = (ray) => {
+ let v1 = [-a[0], -a[1]];
+ let v2 = [b[0] - a[0], b[1] - a[1]];
+ let v3 = [-ray[1], ray[0]];
+
+ let t1 = cross(v2, v1) / (dot(v2, v3));
+ let t2 = (dot(v1, v3)) / (dot(v2, v3));
+
+ return t1 >= 0 && (t2 >= 0 && t2 <= 1);
+ };
```

test/line.js

```
...
expect(line([0, 1], [1, 0]).intersects([1, 1])).to.be.true;
+ expect(line([0, 1], [1, 0]).intersects([-1, -1])).to.be.false;
});
```

Now that `line`

and `line.intersects`

exist, we can implement our
`polygon.intersections`

method.

As usual, we start by adding a test for `intersections`

, and then
we make our test suite happy by importing `line`

, and creating the
`polygon.lines`

function.

polygon.js

```
+import { line } from "./line";
+
export function polygon(_points) {
...
- let intersections = (ray) => 1;
+ let intersections = (ray) => {
+ return lines().filter(line => line.intersects(ray)).length;
+ };
...
+ let lines = () => {
+ return [line([-1, 1], [1, 1])];
+ }
+
return {
...
intersections,
- points
+ points,
+ lines
};
```

test/polygon.js

```
...
+ it("counts intersections with a ray", function() {
+ let poly = polygon([[-1, -1], [1, -1], [0, 1]]);
+ expect(polygon([
+ [-1, -1], [1, -1], [0, 1]
+ ]).intersections([0, 1])).to.equal(1);
+ });
+
});
```

Finally, all we need to do to complete our solution is to build our
`polygon.lines`

function. This function should transform the set of
`_points`

that were used to define our `polygon`

into a set of `line`

objects.

We implement a test for `polygon.lines`

and use it to drive the
creation of our solution. Don’t forget that the last point in the
polygon must connect back to the first!

line.js

```
...
+ let points = () => [a, b];
+
return {
- intersects
+ intersects,
+ points
};
```

polygon.js

```
...
let lines = () => {
- return [line([-1, 1], [1, 1])];
+ if ((!_points) || !_points.length) {
+ return [];
+ }
+
+ let last = _points[0];
+ let pairs = _points.slice(1).map((point) => {
+ let segment = line(last, point);
+ last = point;
+ return segment;
+ });
+ pairs.push(line(_points[_points.length - 1], _points[0]));
+
+ return pairs;
}
```

test/polygon.js

```
...
+ it("creates lines for a polygon", function() {
+ let lines = polygon([
+ [-1, -1], [1, -1], [0, 1]
+ ]).lines();
+ expect(lines.map((line) => line.points())).to.deep.equal([
+ [[-1, -1], [1, -1]],
+ [[1, -1], [0, 1]],
+ [[0, 1], [-1, -1]]
+ ]);
+ });
+
});
```

Now that all of our building blocks are finalized, we can come back to
our original `pointInPoly`

method and rewrite it exactly how we had
imagined:

```
return polygon(poly).surrounds(point);
```

After making this change, our test suite is still green. Everything is
working as expected.

index.js

```
-function countIntersections(poly, point) {
- return 1;
-}
+import { polygon } from "./polygon";
export function pointInPoly(poly, point) {
- let intersections = countIntersections(poly, point);
- return !!(intersections % 2);
+ return polygon(poly).surrounds(point);
}
```

At this point, our solution should be finished. However, when we feed in
the tests provided by the kata, we notice a failure.

After digging into what’s happening, we notice that the system was
claiming that a line, `line([4, -6], [4, 4])`

, was intersecting with a
ray, `[0, 1]`

. Clearly, this is incorrect.

To find out what was causing this, we write a new test against the
`line.intersects`

function:

```
expect(line([4, -6], [4, 4]).intersects([0, 1])).to.be.false;
```

As expected, this test fails.

After some poking, prodding, and comparing against reference equations,
we notice a typo in the `dot`

function. After fixing the dot production
calculation, our entire test suite shifts back to a passing state.

Success!

line.js

```
...
function dot(v1, v2) {
- return v1[0] * v2[0] + v1[1] + v2[1];
+ return v1[0] * v2[0] + v1[1] * v2[1];
}
```

test/index.js

```
...
+ it("detects a point in a square", function() {
+ var poly = [
+ [-5, -5], [5, -5],
+ [5, 5], [-5, 5]
+ ];
+
+ expect(pointInPoly(poly, [-6, 0])).to.be.false;
+ expect(pointInPoly(poly, [1, 1])).to.be.true;
+ });
+
});
```

test/line.js

```
...
expect(line([0, 1], [1, 0]).intersects([-1, -1])).to.be.false;
+ expect(line([4, -6], [4, 4]).intersects([0, 1])).to.be.false;
});
```

# Wrap-up

When you compare our solution with other submitted solutions, you’ll notice that ours is longer. Our solution probably took much longer to write as well. However, our solution was a fantastic exercise in deliberate practice.

By consciously focusing on writing robust and maintainable code, we had a few introspective moments about our process and our technique.

The first major insight that we had came when we realized we were going down a bad road with the `countIntersections`

method. By creating additional abstractions, we ended up with more testable, maintainable and re-usable code.

At the very end of the process we found a bug in the solution. Thanks to our test suite we were able to almost immediately find the source of the bug and fix it.

Be sure to check out the full project, complete with detail commit messages on GitHub.