Shortest path from a starting point to ending point in cartesian space

Hi everybody!

For an interactive installation in which I’m using a custom built cnc machine I have the need to optimise the path that the head of the machine travels along a set of points (~250) in order to minimise the travelled distance (and so, time).

TLDR: given the points that you see what’s the shortest computable path?

I know that this is basically the TSP problem, so not really solvable, but I don’t need the best solution, but just one that it’s better than default one that I’m using (which goes in the way that points are added in my vector, so basically left to right and top to bottom)

I tried looking into A star (a*) and Dijkstra’s algorithm, but none of them seem to be good for my problem, since in my graph every node can possibly be connected to every other node, and I also want to find my start and end point.

I found this answer on math.stackexchange, which is not very helpful but at least it’s a start:

https://math.stackexchange.com/questions/581831/calculating-the-shortest-distance-between-n-number-of-points-on-a-scatter-graph

Does any of you have a hint on the approaches to take?
I need to compute this calculation only once and it should take max 5 seconds, since the app is realtime.
(that’s why I’m currently avoiding genetic algorithms)

Namasté

In my laser rendering code I used a super dumb and simple way and it seems to be quite good and very fast in practice. The algorithm is as follows :

Start at the first point.
Find the nearest point to that.
Move to that point.
Find the nearest point we haven’t already visited…

… and so on.

I guess you could call it a “nearest neighbour” solution although that usually means something else in graphics :slight_smile:

It so easy to implement and fast to run that you may as well try it?

Seb

1 Like

Thanks @seb_ly, I was already trying a nn approach but I had some bugs so I’ll go back to it.
Also, I found some old addons already tackling this problem, I’ll test them and update this post if they work ok.

I’m pretty sure I checked both of these out, ofxTSP is brute force so can get VERY slow, I don’t quite remember what I discovered with ofxLaserTSP but I’m not sure it does anything more than NN - I could be wrong though, let me know if you figure it out.

1 Like

Yes, after giving them a try I can say that you’re definitely right, @seb_ly!
I made a quick search on GitHub and I found this C++ implementation of a genetic algorithm optimised to solve tsp.
Seems pretty fast so for the moment I’m using this one.
I’ll compare the results with a nn approach and post back if there is any substantial difference.

I’m right about ofxTSP being slow or that ofxLaserTSP is just NN? Just curious :slight_smile:

Would love to take a GA approach to this problem, please let me know how this one works!

1 Like

To be honest, I glanced through the code of ofxTSP and I saw it was doing some brute force stuff so I quickly tried to compile it but since it didn’t (I’m using 0.10) I basically gave up and started looking for something more optimised.
I’ll try to do a benchmark using genetic algorithms versus nn as soon as possible, currently my brain is fried and can’t seem to properly code the nn version, but you can find my current code here: https://github.com/vvzen/maca-final/tree/master/shortest-path-test

Ok, I think I’ve managed to write a first rough nn approach.
Given for granted that I’m doing everything right (which may not be) these are the results so far (distance is expressed in mm):

So it seems that either nn or a ga are pretty similar. Of course the genetic algorithm approach heavily depends on the population size, number of generations and mutation rate, so tweaking these values can produce quite different results.

Just by eye, I’m not sure that your nearest neighbour solution looks quite right… I would expect to see far fewer long lines… wanna share your code?

1 Like

Of course! Here’s my current code:

I basically load the points from a csv, the nn stuff starts at line 81 of ofApp.cpp.

I’m also posting the nn extract here:

    // 1. Start on an arbitrary vertex as current vertex
    int closest_p_index = 0;

    glm::vec2 p = points.at(closest_p_index);

    // continue while there are still points to visit
    while (points_nn_path.size() < points.size()-1){

        glm::vec2 p = points.at(closest_p_index);

        ofLogNotice() << " points_nn_path: " << points_nn_path.size() << ", points: " << points.size();

        float min_distance = 20000.0f;

        for (int j = 0; j < points.size(); j++){

            glm::vec2 other_p = points.at(j);

            // check if we already have visited the other p, if so, just skip it
            if(std::find(points_nn_path.begin(), points_nn_path.end(), other_p) == points_nn_path.end()) {
                
                // 2. Find out the shortest edge connecting current vertex and an unvisited vertex V
                float current_distance = ofDist(p.x, p.y, other_p.x, other_p.y);
                if (current_distance < min_distance && current_distance > 0){

                    min_distance = current_distance;
                    // 3. make this point the next point
                    closest_p_index = j;
                    // 4. add it to the visited points
                    points_nn_path.push_back(other_p);
                }
            }
        }
    }

    // compute distance of nn
    for (int i = 0; i < points_nn_path.size()-1; i++){
        auto p = points_nn_path.at(i);
        auto next_p = points_nn_path.at(i+1);
        nn_distance += ofDist(p.x, p.y, next_p.x, next_p.y);
    }

I think I might have found something in your code… can I get the dots.csv to test it out please?

Thanks man! It’s on the github repo here: https://github.com/vvzen/maca-final/blob/master/shortest-path-test/bin/data/dots.csv

Ah yes, there were a couple of flaws in your implementation, I think I’ve fixed them… let me double check and get back to you… but here are the results.

1 Like

Wow @seb_ly that’s awesome! Way better than any genetic algorithm! If you want, feel free to make a pull request or just post the code here. Thank you so much!

thanks! I’ve made a pull request but the code is here for anyone else following along :

    // 1. Start on an arbitrary vertex as current vertex
    int closest_p_index = 0;

    glm::vec2 p = points.at(closest_p_index);

    // continue while there are still points to visit
    while (points_nn_path.size() < points.size()-1){

        glm::vec2 p = points.at(closest_p_index);

        ofLogNotice() << " points_nn_path: " << points_nn_path.size() << ", points: " << points.size();

        float min_distance = 20000.0f;

        for (int j = 0; j < points.size(); j++){

            glm::vec2 other_p = points.at(j);

            // check if we already have visited the other p, if so, just skip it
			// NB using this technique, duplicate points will be removed.
            if(std::find(points_nn_path.begin(), points_nn_path.end(), other_p) == points_nn_path.end()) {
                
                // 2. Find out the shortest edge connecting current vertex and an unvisited vertex V
                float current_distance = ofDist(p.x, p.y, other_p.x, other_p.y);
                if (current_distance < min_distance && current_distance > 0){

                    min_distance = current_distance;
                    // 3. make this point the next point
                    closest_p_index = j;
					// but don't add it to the list until we've checked all the points against the first!
                }
            }
        }
		// now we can add it to the list of added points:
		glm::vec2 other_p = points.at(closest_p_index);
		points_nn_path.push_back(other_p);

    }

The issue was that you didn’t finish iterating through the nested loop before adding the point to the list.

(sorry I just realised that Xcode used tabs instead of spaces which the rest of your code seems to use…)

Oh another suggestion is that you replace this line with :

		float min_distance = MAXFLOAT;

That way you can be sure that this algorithm will work, no matter what scale it’s at.

1 Like

@seb_ly Still thanks! Made my day. Long live to the greedy nearest neighbour! :smile:

glad to help!

Hi,
I know nothing about TSP, but I was curious to see if there is a simple way, during the path construction, to not ignore some close points at the cost to travel back to them later. Here’s what I mean:

Ignored points that require to travel a long distance to reach them:
png%5D

A better result:
png%5D

So I tried to modify a little bit the NN approch: the new point to add to the path is not the closest to the latest added one, but the closest to the mean of the 5 (for example) latest points already added.

Most of the time, this new approach doesn’t give better results: the generated path is longer than with the simple NN construction. But I share my experiments with you, because depending on the goal it can still be interesting sometimes, for aesthetic reasons. And also because I feel nice to play with :slight_smile:

Special case, the second path is shorter:

General case, the second path is longer:

But it can be graphycally interesting:



Here’s the source of the app that I made, based on yours, it now allow to edit the points:
src.zip (3,3 Ko)

and my new solver:

void ofApp::solve_mean_nn( const vector< glm::vec2 > & in_points, vector< glm::vec2 > & out_points, size_t startIdx )
{
	out_points.clear() ;
	out_points.reserve( in_points.size() ) ;

	if( in_points.size() < 2 ) return ;

	// Add the first point to the path
	out_points.push_back( in_points.at( startIdx ) ) ;

	// Build a list of all the points that aren't included in the path yet
	deque< glm::vec2 * > rest ;
	size_t i = 0 ;
	for( auto & p : in_points )
	{
		if( i++ != startIdx ) rest.push_back( const_cast< glm::vec2 * >( &p ) ) ;
	}

	// This is the mean of the last num_points_for_mean added to the path
	// At the beginning we have only one point in the path
	glm::vec2 mean = out_points.back() ;
	size_t meanSize = 1 ;

	// An iterator to the oldest point to consider for the mean
	auto meanTailIt = out_points.rend() ;

	// Loop while there are points not yet included in the path
	while( ! rest.empty() )
	{

		auto end = rest.end() ;
		auto best = rest.begin() ;
		float min_distance = numeric_limits< float >::max() ;

		// Loop over the points that are not included in the path to find the closest one
		for( auto it = rest.begin() ; it != end ; it++ )
		{
			float distance = ofDistSquared( ( *it )->x, ( *it )->y, mean.x, mean.y ) ;
			if( distance < min_distance )
			{
				min_distance = distance ;
				best = it ;
			}
		}

		// Add the closest point to the path
		out_points.push_back( **best ) ;

		if( meanSize < num_points_for_mean ) ++meanSize ;
		// Advance the oldest point to consider for the mean
		else meanTailIt-- ;

		// Compute the mean of the lastest points in the path
		mean.x = 0 ;
		mean.y = 0 ;
		for( auto it = out_points.rbegin() ; it != meanTailIt ; it++ ) mean += *it ;
		mean /= float( meanSize ) ;

		// Remove the closest point from the list of the points not yet used
		rest.erase( best ) ;
	}
}
2 Likes

Thanks for all of these tests, @lilive!
Interesting twist to the good old nn approach. It seems to work better with less points taken into account for the average. I think there’s a very good potential for many creative discoveries!