Developing an Algorithm Case Study: Area encircled by multiple paths on a 2D plane
I generally don't consider myself a computer scientist. Throughout my career I've focused much more on engineering where the problems I encounter are primarily around app architecture/maintainability and much less so on designing new data structures or algorithms. However, recently I've been toying around with a new app idea and it felt like I hopped into a time machine back to my data structures and algorithms class in college. Not only that, I found myself really enjoying the challenge and flexing a mental muscle that I feared might have atrophied. In this post, I want to present the problem (slightly simplified) and give you a chance to tackle it yourself if you're interested. Then, I'll talk about my problem solving process as well as the solution I came up with.
The Problem
Given a 2D plane where the user has plotted out several different routes defined by a series of points on the plane, calculate the total area the routes encircle.
This is much better expressed in visual form through an example.
The plane above has 5 different routes A, B, C, D and E. Each route is defined by series of points A1, A2, etc. Together, the routes encircle the area highlighted in light blue.
Your job is to write an algorithm to calculate the total area represented by the encircled area (light blue) given an arbitrary list of routes. As a bonus, return the polygons that make up the encircled area. Note: The polygons would only be used to draw the encircled area so the arrangement is unimportant as long as it draws correctly.
Edge Cases
- A and B intersections show that it should be the union of all shapes
- B shows a path with segments that don't contribute to a filled shape
- C shows a shape completely enclosed by another shape
- D shows a completely independent shape
- E shows a line segment that exists inside an enclosed shape
If at this point, you want to try to solve this problem yourself, I highly encourage it. Otherwise, you can read through my process and then my solution.
My Process
The first thing I realized when I looked back at how I solved this problem is it was in no way linear. It was much more akin to a game of battleship where I took several educated guesses until the problem space became more clear to me and I could come up with the final solution. However, critically, those "guesses" didn't involve code; I tested my algorithm by mentally stepping through how it would work in my example above. I did this until I was confident my algorithm would work.
The first thing I did was post questions on the Computer Science Stack Exchange and r/AskComputerScience. I did this for two reasons: First, it forced me to formalize the problem because it had to go from an amorphous thing I wanted to achieve in my app to a well-defined problem a stranger on the internet could understand and offer advice on. Simply writing out the posts significantly helped me wrap my head around the problem. Importantly, this only worked because I put a lot of effort into the questions. Second, if there was a well-established algorithm to do this, I didn't want to waste my time designing one myself.
Dueling Considerations
After I posted the questions, I didn't twiddle my thumbs until answers came in. I immediately set to work on the algorithm. The biggest realization I made while writing up the questions was that the plane would be well represented as a Graph. I was familiar with the data structure from college. If you're not familiar with it, it is a collection of nodes connected by edges. I figured each node would contain the x and y coordinates of the route point they were representing but I didn't know the other details I would need.
From this point forward, I had dueling considerations: the data structure to represent the relevant data and the algorithm to process the data. I would think of a possible algorithm, try to walk through it, and realize the data structure didn't have enough information. At other times, I would come across existing data structures like a Doubly connected edge list as suggested by u/teraflop and that would inspire algorithm details.
Contrary to popular myth, I had no epiphany. I repeatedly tested out algorithms, discovered their problems, and reasoned ways to fix it. However, there were two critical ideas I had (before similar things were suggested to me on Stack Exchange).
1. The graph should update routes with any intersections that were added (highlighted in red below).
2. Exit paths can be chosen based on their angle ordering in a consistent direction (I chose clockwise). For example, the intersection highlighted in red below has 3 options to exit after coming in from A3: B5, A2, B6. The next edge in the clockwise direction is B5. If instead, we came in to the intersection from B5, the next edge in the clockwise direction would be A2.
This asymmetry seemed useful and it then lead me to realize that I would basically have inner and outer cycles if I made sure to always go both directions on all edges. (More on that in the solution section).
Also, here are a few random doodles I made while problem solving.
The meaning of the doodles will become clearer after seeing my solution.
My Solution
Just like my process, my solution can be separated into two parts: the data structure and the algorithm.
The Data Structure
The data structure is relatively simple. It is a collection of Nodes that are connected by Edges.
Each node stores the coordinates of where it lies in space and each segment is represented by two directional edges, one in each direction. Each intersection of line segments is broken up with a new Node. Note the coordinates of the intersections are left off the diagram but are included in the data structure.
The Algorithm
Find All Cycles
- 1. Pick any edge and choose the next edge that is closest to clockwise from the edge you entered the node on.
- 2. Record whether the angle between the connecting edges is a reflex angle (> 180 degrees) or not.
- 3. Record the series of nodes visited
- 4. Mark the edge as used
- 5. Follow that new edge to the next node and repeat until reaching the first node again.
At the end, the cycle will have the points that it is composed of and a count of reflex and non-reflex angles. If there are more reflex angles, it is considered to be an outside cycle and is thrown out. Otherwise, it is included in a preliminary list of polygons to include in the final result.
Repeat this cycle finding process until every edge has been used.
Filter Polygons
Filter out any resulting polygons that are entirely inside another. This can be done by testing only the first point of one polygon to see if it's inside another. That's because we know we will never have any intersecting polygons.
Calculate the Area of Each Remaining Polygon
At this point, we just need to calculate the area of each polygon and add them together for our solution.
Some Details
It's important to note that in the case where we get to a node and the only remaining edge is the returning edge, it counts as a 360 degree angle and therefore a reflex angle.
Also, it's important to note that each angle of each cycle must be counted towards the reflex and non-reflex count, including the first and last. Otherwise, a plus sign arrangement of simple paths (+) will result in a valid polygon.
Example
To illustrate the algorithm, let's go through my example.
We'll start with a random edge (marked green).
Following each first clockwise angle, we end up with this cycle.
Every angle is less than 180 degrees making it a valid polygon.
Next, we choose another random unused edge and complete its cycle.
This time, every angle was greater than 180 degrees making it an invalid polygon.
We continue this and create every possible cycle.
That leaves us with these valid polygons.
Note that the blue polygon has the line that insets from the edge and immediately returns. For the area calculation and even for drawing for my application this is fine, but it could be solved with a separate clean-up algorithm if necessary.
The last step filters out the yellow polygon because it is contained in the orange one.
My Implementation
To keep this post a reasonable length, I'm not going to go into the code itself. If you're interested in the code, feel free to reach out to me and I can send it over for you to take a look at.
Improvements
I've done nothing to prove that this is the most efficient algorithm possible, but it was relatively straightforward to code and efficient enough for my application for now. If I find it becomes a bottleneck, I'll go back to see if I can find refinements.
However, if you have any ideas on better ways to do this, I'd love you to tell me!
My first thought after writing this up is that it may make more sense to maintain the cycles in the data structure itself instead of or in addition to the individual edges. That would increase the complexity of the data structure but make repeat calculations faster. Of course I can cache the calculation results so it may not be worth it. Likely, it will come down to my desire to challenge myself and my restraint to focus on the more practical tasks I have in my app.
Lessons Learned
The biggest lessons I learned is that I find this aspect of my career surprisingly fun considering I don't do it that often. It's a lot of fun to put that much focus into a single algorithm. It was also fun to brush off some of my trigonometry and it was enormously satisfying to produce the final working code.
There's still a lot more to do in my app than just this algorithm, but we have to take each win as they come and use it as fuel to move on to the next task.
Subscribe
Follow Me
Follow Me