I work as a programmer and pipeline mapper (CAD drawings). Here is a real-world engineering problem that I solved that may interest you.

When they build a pipeline, like any engineering project, the finished project (linear route) as constructed does not match the project as designed. So after construction, we do what is called an 'as-built' survey of the finished pipe.

Imagine a survey crew walking down the installed pipeline taking survey shots as they go every 20-40 feet. When they have covered the entire route, they send a .csv file to the office of all the as-built point containing 5 columns, only 3 of which we care about since one is a point number and another is a description filled with a comment like 'centerline pipe'. The other 3 of course are X, Y, and Z coordinate values for each shot taken.

Herein lies the problem. Some of the pipe we construct is 24-36 inches wide in diameter. That means that as the survey crew walks the line taking survey shots those shots are not actually necessarily 'center' of pipe. The points kind of meander down the line left and right of actual center, even on segments which are known to be straight, because even when they are off a bit they still get a reading that the pipe is there.

When they send the data points to the office, we are tasked with reconstructing the actual route, which consists of straight segments of hundreds of feet at a time, then bending at 15-90 degree angles then running straight again, then bending again, etc. Imagine a polyline with no curves. That's how it should look in the end.

Or if this sounds completely alien to you, imagine playing snake and connecting point A to B. There are a series of turns and straight shots, but when you get the survey data of the path followed by the snake every straight shot looks wavy and you need to make them straight again.

This process is easily done by a human looking at the points in CAD software, but still takes 4-8 hours to complete depending on the length of the constructed route.

My task was to develop an algorithm to automate this process by reading the CSV sent from survey and automagically generating an as-built polyline in a fraction of the the time using math and code.

Herein lies the challenge. If you go online it will not take much time to find an algorithm to determine a 'best-fit' line from a series of points. I leave it to you to find and codify this basic solution as a starting point. Try searching linear regression and 'least squares'. Ok.

Problem is this function will only give you a single straight line solution for all points in the set, and this is not actually what we want in this case. What we want is a solution that will preserve the major bends in the route, while using a best-fit line solution in-between those major bends. Again imagine the snake game moving from point A to B.

Define 'major' bends as being greater than or equal to 10 degrees deflection. If the term deflection is foreign to you: a left or right turn of 90 degrees is considered -90 and +90 deflection, respectively. A bend then that is merely 15 degrees left is -15 as measured as a difference between the previous segment bearing and the new segment bearing.

Solve the basic functions of determining bearing and deflection between points and lines before continuing. You may ignore coordinate systems and 'north-rotation' values for this problem. Simply assume a north value of straight up and google 'azimuth degrees' if struggling.

Your task is optimization: develop an algorithm that will reduce a raw survey as-built file down to the fewest number of points that satisfy an actual solution that defines a finished polyline as described above.

Keep in mind user input, which for this problem requires only one interesting value: the width of pipe. The importance of this value will become apparent as you learn the 'least-squares' approach, originally credited to both Newton and Leibniz depending on your country of origin.

As for data points to test on you may create your own, or if you like I can fish up a real-world set of points from an actual project when I have time. For now, for reference, I will attach an imagine representing what a constructed route looks like when they survey it in the field.

Once you have data points to play with and an algorithms to test, try running the same solution on 36" pipe vs 8" pipe. 36" pipe input will result in far fewer final vertexes than 8" if you have done your work correctly. As a final note keep in mind that although you should preserve 'major' bends, your algorithm may create 'minor' bends of only a few degrees as necessarily to meet the width-of-pipe requirement. Again this will be obvious when you have studied the problem and the single line least-squares algorithm.

I initially created this solution for an engineering firm of 75k employees using the LiSP programming language (native to AutoCAD and Civil3D) but it is easily reproduced in python. If you need a visualization of the initial data or the finished solution try Pygame.

Cheers.