Counting Triangles
An example of a Non-TDD, overly engineered problem solving (yes, another one)
I was at the after work coding Dojo last Thursday in Munich. The plan was to work on a task with TDD approach as small teams. What matters was completely process. Teamwork and small TDD iterations. We did. We did good, actually.
And surely we could not come up with a solution which is totally fine. But it grew in me. I wanted to solve the problem!
Problem
Given a series of coordinates representing starting and ending points of lines, find the number of triangles formed. Clear, challenging and inviting problem.
Spoiler alert, I solved problem, check it here running live.
1. Visualizing the Problem
In order to solve any problem, one needs to understand the problem deeply first. Also I like to play with geometry and html canvas. So I decided to visualize the problem first.
What we had was only a list of line segments represented by starting and ending points. So, the first step was to draw lines on a canvas. I’m not going to show you how to draw lines on canvas but, i have a tip.
Inverted Y Axis
When I first drawed the lines on canvas, it turned out that clearly something is wrong, because the whole visual looked upside down. It’s obvious that canvas starts the Y axis at the top left corner of the drawing area, but in any other system, its common to use an upwards directed Y axis. So you can invert Y axis with a simple transform operation on canvas:
ctx.transform(1, 0, 0, -1, 0, canvas.height);Then i thought, maybe it’s a good idea to emphasize start and end points on the visual also.
2. Line Intersections
We have only starting and ending points of line segments, not intersection points. But they have vital importance, because they form triangles. To be able to compute intersection point locations, I needed to represent lines mathematically.
Attempt #1
When I first see the problem, i thought that the obvious way to represent those lines is linear equations, like,
y = ax + bAnd then I was going to find intersecting points easily by solving two linear equations with two unknowns. The X and Y coordinates satisfy both lines, are the intersection coordinates.
But
Attempt failed at the second line, the vertical one. Because a vertical line has undefined slope. So there are no a and b values for second line!
Then
After a little search on wikipedia, about line intersections, i realised that an intersection point can be defined using determinants. Smooth!
But
I don’t have infinite lines here, but just line segments. Any two lines which have different slopes have an intersection point anyway. Even it is on the moon.
For instance, take these two line segments: They have intersection, but outside both of them!
Attempt #1
I decided to write a simple function which takes a line, and a point and checks if the point is on the line. Then I was going to check if the point lies on the both line segments. Started typing and the function name I came up was isPointOnTheLine.
Something happened and I became AFK. Then i came back, looked at the screen, saw the empty function which is named isPointOnTheLine. As any reasonable programmed would do, I started thinking a solution to check if a given point lies on a given line represented by only starting and ending points.
Oh boy, I wish you could see me struggling with wild linear algebra approaches on the paper. Then at some point, i realised. At that point, I was illuminated. The point was already on the both lines, of course, it was an intersection point! The only problem I needed to solve was if the point is in the range of a line segment. I gazed upon the function name with anger. And deleted it.
All i’m trying to say is function names are important.
Attempt #2
I create a new function named isPointInRange, and it was as easy as pie to implement this time.
Finally, i was able to compute coordinates of actual intersection points between line segments.
3. Counting Triangles
Looked at the visualization I just created and thought about what possibly could form a triangle. From the image above, it’s obvious that the black dot at the top right corner, can not. This was a nice starting point. Only intersection points can create triangles, so there is no need to take end points into account.
My plan was simple. Inefficient but brute force: Create combinations of all intersection points of 3 point groups. Order of the points does not matter. And each group consisting of 3 points becomes a triangle candidate. Then, check if these three points are connected by lines. If so, we have a triangle!
First I decided to implement my own combinator algorithm implementation. But after some time, i gave up and started looking for a ready-to-go solution. Hopefully, found a solid one.
I had all point groups which potentially could form triangles. But all points in a group should be connected. Which means I needed to relate points and lines somehow.
Thought about creating a property for Line class named points. So, after finding an intersection point it was added to boths lines points property. Because this point is on the both lines. So, if you want to know if any two points are connected with a line, all you need to check if both of these points are member of the points property of any line we have!
But
To test my approach, I removed some lines until the answer was so obvious. As you can see in the next figure has only two triangles. But my triangle counter was saying that it had 4!
Yes, solution was a little shifted. Consider the three points on the vertical line at the left. They are in the potential triangle groups and they are connected. So, with my assumptions so far, they should have formed a triangle. Then I realised also these points should not lie on the same line.
So, I iterated over lines and if all the three points belong to one line, just ignored them!
The end result was smiling at me finally. I had found the answer 2 for the image above!
4. Visualizing Results
It was clear to see the answer for the simple case but when i switched back to original problem, too much effort required to verify the result I computed. This is where I decided to visualize results.
Attempt #1
First, tried to colorize each triangle I found with some semi transparent color.
It looks fancy at first blush, but, because of the overlaps, it’s not that useful.
Attempt #2
Decided to explode triangles away from original visual and draw them separately:
And this time, you can see the triangles separately but hard to relate with original problem. Not satisfied.
Attempt #3
Then suddenly realised that I could draw triangles with time intervals. What a surprise!
So the answer for the problem was 9 triangles.
See the triangle counter running here live.
You can check my solution on github.
Happy hacking.
