C++

Forum

 
Pathfinding from a text file

Pages: 12
SteveGarrot (16)
I'm working on a program that reads coordinates from a textfile that contains several coordinates. Starting from the first coordinate, the program then outputs the closest coordinate, and so on. For example, if a textfile contains the coordinates (1,3) then (5,7) and (2,4), the program outputs 1,3 and then 2,4 and finally 5,7.

My situation is that I'm not entirely sure where to start. I currently have the very basics of the program. Though I'm not entirely sure how to get the program to output the closest coordinate after it outputs the first one. While I'm certainly not asking anyone to do the entire program for me, some help to put me in the right direction would be greatly appreciated.
wizebin (148)
The algorithm you use to find the nearest neighbor depends entirely on the dynamism of your data. If your data changes a lot you will want to use a different algorithm than if your data never changes.

How did YOU figure out it should go 1,3 2,4 5,7? Tell your program the same thing.

This sort of functionality can be implemented in quite a lot of ways- the slowest possible (and most naive) implementation would be to go through the list of objects for each object and find the nearest object using the Pythagorean theorum distance = sqrt(pow(x2-x1,2)+pow(y2-y1,2));

Two things to keep in mind.

1. Don't return the same object your searching for the nearest neighbor of.
2. Don't return any previous neighbors (probably) otherwise you'll get a cyclical list.


SteveGarrot (16)
The data only changes if the user goes into the textfile and manually changes it. It is not dynamic within the program itself.

I just started considering this: assign an int variable with the value of the first coordinate. Then a while loop reads through the x and y value, and searches for the next closest set of coordinates with an if statement and so on and then outputs them at the end. However, thinking about it now, I can't see it working properly when I have to compare it with the if statement.

I hadn't thought about using the Pythagorean theorum though. I'm going to toy with that now.
SteveGarrot (16)
To use the Pythagorean theorem, how would I go about assigning each coordinate at x1 and y1 and then x2 and y2? I was thinking about using a while loop that reads through the text file and assigns the coordinates of the first set to x1 and y1, but is there a way where I can have a while loop do that for every set of coordinates while comparing the distance between them?
closed account (48T7M4Gy)
The term 'closest' is relative so the question is closest to where. If you have 3 points and a vantage point from where distances are measured then that is where you start to analyze your date by reading it into some form of array of points, calculating the distance to each by pythagoras and determining the minimum of those distances.

So if you have 3 points on file you have a couple of choices to make whether the vantage point is a fourth (reference) point ( maybe the origin (0,0) or somewhere else ) or is it one of the 3 points in which case the closest is the point with the lesser of the two distances?
Last edited on
cire (8284)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
#include <algorithm>
#include <fstream>
#include <iostream>
#include <utility>
#include <vector>

struct point {
    int x, y;
};

std::ostream& operator<<(std::ostream& os, point p)
{
    return os << "(" << p.x << ", " << p.y << ")";
}

std::istream& operator>>(std::istream& is, point& p)
{
    (is >> std::ws).ignore();               // '('
    (is >> p.x >> std::ws).ignore();        // ','
    (is >> p.y >> std::ws).ignore();        // ')'
    return is;
}

// Since we only need the relative distance, don't bother
// with the square root.
int distance_squared(const point&a, const point& b)
{
    int x_diff = a.x - b.x;
    int y_diff = a.y - b.y;

    return x_diff*x_diff + y_diff* y_diff;
}

int main()
{
    std::ifstream in("data.txt");
    using pair_type = std::pair<int, point>;
    std::vector<pair_type> points;

    point origin;
    if (in >> origin)
    {
        point pt = origin;
        do
        {
            points.push_back(std::make_pair(distance_squared(origin, pt), pt));
        } while (in >> pt);
    }

    std::sort(points.begin(), points.end(), 
        [](pair_type& a, pair_type& b) { return a.first < b.first; });

    for (auto pair : points)
        std::cout << pair.second << '\n';
}


Note that if you only need to find the nearest point (or k nearest points) there are more efficient ways to do this. See:
https://en.wikipedia.org/wiki/Nearest_neighbor_search

SteveGarrot (16)
Ok, this mostly makes sense to me, but I'm kind of confused as to what is happening at the end there.
closed account (48T7M4Gy)
is there a way where I can have a while loop do that for every set of coordinates while comparing the distance between them?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
struct/class point
   x , y coordinates  (  z?? :] )

struct/class line
   point a to/from point b

list of point
list of distances

read in first point 

loop until finished:
   read in next point
   calculate and record distances to all existing points

analyse and sort list of distances
output results
SteveGarrot (16)
Ok, so I'm messing around with the code above but now the program only outputs the first set of coordinates. Does anyone know what is a good way to output the rest of the coordinates? Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
#include <algorithm>
#include <fstream>
#include <iostream>
#include <utility>
#include <vector>

struct point
{
	int x;
	int y;
};

std::ostream& operator << (std::ostream& os, point p)
{
	return os << "(" << p.x << ", " << p.y << ") --- ";
}

std::istream& operator >> (std::istream& is, point& p)
{
	(is >> p.x >> std::ws).ignore();
	(is >> p.y >> std::ws).ignore();

	return is;
}

int distance (const point& a, const point& b)
{
	int diffOfX = a.x - b.x;
	int diffOfY = a.y - b.y;

	return (diffOfX * diffOfX) + (diffOfY * diffOfY);
}

int main()
{
	std::ifstream myfile("pathf.txt");

	using pair_type = std::pair<int, point>;
	std::vector<pair_type> points;

	point origin;

	if (myfile >> origin)
	{
		point pt = origin;

		do
		{
			points.push_back(std::make_pair(distance(origin, pt), pt));
		}

		while (myfile >> pt);
	}

	std::sort(points.begin(), points.end(), 
                [](pair_type& a, pair_type& b) { return a.first < b.first; });

	for (auto pair : points)
	{
		std::cout << pair.second << std::endl;
	}
}
closed account (48T7M4Gy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
#include <iostream>
#include <fstream>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

using std::vector;

using std::ostream;
using std::istream;
using std::ifstream;

using std::operator>>;
using std::operator<<;

struct point
{
	int x = 0;
	int y = 0;
};

ostream& operator<< (ostream& out, const point &p)
{
	out << "(" << p.x << "," << p.y << ")";
	return out;
}

istream& operator>> (istream& in, point& point)
{
	in >> point.x >> point.y;
	return in;
}

struct line
{
	point start;
	point finish;
	int sqDistance()
	{
		int dx = start.x - finish.x;
		int dy = start.y - finish.y;
		return dx * dx + dy * dy;
	}
};

ostream& operator<< (ostream& out, const line &ln)
{
	out << "From " << ln.start << " to " << ln.finish;
	return out;
}

istream& operator>> (istream& in, line ln)
{
	cout << "Enter x y start then x y finish: ";
	in >> ln.start.x >> ln.start.y >> ln.finish.x >> ln.finish.y;
	return in;
}

int main()
{
	point origin, input;
	line ray;
	vector<line> side;

	// READ POINTS FROM FILE
	ifstream pointfile("paths.txt");
	if (pointfile.is_open())
	{
		pointfile >> origin.x >> origin.y;
		cout << "Origin: " << origin << endl;
		ray.start = origin;

		while (pointfile >> ray.finish)
		{
			cout
				<< "Point entered " << ray.finish 
				<< " and distance squared to start: "
				<< ray.sqDistance() << endl;

			side.push_back(ray);
		}
	}
	else
		cout << "Unable to open file";
	pointfile.close();

	/*
		cout << "Start: ";
		cin >> origin;
		cout << origin << endl;
		cout << "Press any alpha to end" << endl;
		while (cin >> input)
		{
			cout << input;

			ray.start = origin;
			ray.finish = input;
			cout << " and distance squared to start: " 
<< ray.sqDistance() << endl << endl;

			side.push_back(ray);
		}
	*/

	vector<line>::iterator iter = side.begin();
	line temp, closest = *iter;
	int minimumDistance = closest.sqDistance(), distance = 0;

	for (iter = side.begin(); iter != side.end(); ++iter)
	{
		temp = *iter;
		distance = temp.sqDistance();
		cout
			<< "Distance "
			<< temp << " is " << distance << endl;

		if (distance < minimumDistance)
			closest = temp;
	}
	cout << endl;
	cout << "Point closest to origin is " << closest.finish << endl;

	return 0;
}
Origin: (1,-2)
(3,4) and distance squared to start: 40
(5,-1) and distance squared to start: 17
(-9,6) and distance squared to start: 164
(-3,-3) and distance squared to start: 17
Distance From (1,-2) to (3,4) is 40
Distance From (1,-2) to (5,-1) is 17
Distance From (1,-2) to (-9,6) is 164
Distance From (1,-2) to (-3,-3) is 17

Point closest to origin is (-3,-3)
Press any key to continue . . .


paths.txt
1 -2
3 4
5 -1
-9 6
-3 -3
Last edited on
SteveGarrot (16)
Interesting. While your way is way more useful, could you use this version to read from a textfile rather than user input?
closed account (48T7M4Gy)
I'm going to do it soon, but the short answer is 'yes'. I just got carried away with the technology and tried out a few things. (The square distance is not a bad time-saving idea I thought) :)
SteveGarrot (16)
Cool, I really appreciate the help! And, yeah I have tried the square distance before and it is very useful!
SteveGarrot (16)
Code looks good! I get a "Vector Iterator Not dereferencable at Line 72" though when I try running it. As I'm still somewhat rusty/new to C++, I'm not really sure what that means.

Edit: Oh, I see. My text file has commas between the x- and y-values, while your's has spaces. That is what was causing my problems.
Last edited on
closed account (48T7M4Gy)
Oh, I see. My text file has commas between the x- and y-values, while your's has spaces. That is what was causing my problems.

Yeah spaces are the only delimiter we need and I hate data that's riddled with commas.
I'm glad it was so easily fixed.

One trick with the preparation of the data file is to only save data via the program rather than manually because it can get out of sync very easily and difficult to debug.

:)
SteveGarrot (16)
Yeah, I could see why. I typically prefer getting data from the program, but I'm messing around with reading from textfile questions from my textbook. Since it's a beginners textbook, I'd figure reading coordinates with the commas would be easy (as the textbook does), but I'm starting to see it is difficult.

Thanks for the help!
closed account (48T7M4Gy)
You can have commas but you need to write the input routines so that commas are recognised as delimiters. Check out this thread http://www.cplusplus.com/forum/beginner/8045/
SteveGarrot (16)
Interesting, so I could just add:

1
2
3
4
 
	in >> point.x;
	in.ignore(1, ',');
	in >> point.y;
	return in;
closed account (48T7M4Gy)
Interesting, so I could just add:

No I was wrong because I very rarely if ever have commas. However if you are hell-bent on it do this:

1
2
3
4
5
6
 
istream& operator>> (istream& in, point& point)
{
	char dummy = ' ';////	
	in >> point.x >> dummy >> point.y;////
	return in;
}


and
1
2
3
4
5
6
7
 
istream& operator>> (istream& in, line ln)
{
	char dummy;
	cout << "Enter x y start then x y finish: ";
	in >> ln.start.x >> dummy >> ln.start.y  >> dummy>> ln.finish.x  >> dummy>> ln.finish.y;
	return in;
}


Which means that you need to swap to:
1
2
3
4
5
6
7
 
// READ POINTS FROM FILE
	ifstream pointfile("paths.txt");
	if (pointfile.is_open())
	{
		pointfile >> origin;
		cout << "Origin: " << origin << endl;
		ray.start = origin;


And famous last words, that adjustment allows comma or space (and probably any alpha character as a delimiter which makes sense (subject to testing properly to find out possible limitations like " ," .
Last edited on
SteveGarrot (16)
Ok, cool. That makes sense. Thanks for the help, again!
Pages: 12