# Thread: Read geographic item location data from file and calculate neighbors

1. ## Read geographic item location data from file and calculate neighbors

Hi
Yes, this is a homework question, but not my homework. I'm trying to help a friend.

The problem is complicated to describe.
There is a file which contains geographic location data (longitude, latitude) for objects (trees).
Some trees have multiple entries in the file with slightly different locations. This is due to accuracy of recording the positions from different people.

The task is to examine the input file and if a tree is close (within 40m) to another, then consider that as one item with a new location as the average of the two readings. The new locations are then stored on another file.

The problem is when you have 3 or more trees close together and you have to consider this as one group and return the average of all 3 (or more).

The average of a&b&c is not the same as the average of a&b averaged with c.

So, a could be close to b, but not to c. But if b is close to c, then all three a,b,c are said to be close and the average position needs to be given.

How? Any creative approach you can think of?
Thanks for ANY suggestions. 2. Yes, your friend should join the forum and ask their own questions directly.

This is hard enough as it is without someone playing piggy in the middle. 3. If you can find all the trees that are close enough to a particular tree, you can solve this quite easily.

The implementation depends on many things. Is the data sorted? Would a quad or oct-tree implementation for O(log N) searching be feasible, or is a linear O(N) adequate? 4. Originally Posted by Salem Yes, your friend should join the forum and ask their own questions directly.

This is hard enough as it is without someone playing piggy in the middle.
Well obviously I can't help her which is why I asked here, and I'm not a threat to her independent problem solving. But if I could just drop a hint or two to get her on the right track, she'd still have the feeling that she cracked the problem alone and not gone running off for help. 5. Originally Posted by GReaper If you can find all the trees that are close enough to a particular tree, you can solve this quite easily.

The implementation depends on many things. Is the data sorted? Would a quad or oct-tree implementation for O(log N) searching be feasible, or is a linear O(N) adequate?
Thanks very much for your reply. That sounds complicated to me, and sounds like it's above the level she's expected to be at.
I wonder if we're overthinking this problem, as I'm thinking it should be simpler.
The data is not sorted btw. 6. Yes, efficient algorithms for spacial placement or grouping can be quite complicated. You can do without them though.

You can solve it by continuously iterating through the list of trees in order to find the ones that are close enough together. Then you compute the average of those, save it in another list and remove the processed trees from the examined list. Repeat until the list is empty and your new list will be full with unique, error-corrected trees. This process can be slow though, O(N²) to be exact, but it may be fast enough. 7. Surely there needs to be some kind of restraint. Say you had a square area with a whole bunch of trees in it (we'll say 100000) and the trees are all about 20m away from at least one of their neighbours then without any kind of restraint then the problem description as it stands now will want us to regard all 100000 trees as a single tree! because as you iterate through those close to each other at the "start" migrate towards others nearby until they all march to stand in the same location. Weird.

Edit: Maybe that's the answer. Just choose a single tree from the set at random and group all 100000 trees together and say it's at lat/long of the randomly chosen one 8. Hmm, that would be the case if you were to recycle every single tree. I'm suggesting a way to circumvent that problem, by discarding all the trees similar to a particular tree, after averaging them of course. 9. The OP seems to need to ask the student what Big O type answer is needed. Big O notation - Wikipedia
O(N²), O(N), or O(log N)

Tim S. 10. Originally Posted by Grumps Thanks very much for your reply. That sounds complicated to me, and sounds like it's above the level she's expected to be at.
I wonder if we're overthinking this problem, as I'm thinking it should be simpler.
The data is not sorted btw.
And so the Chinese whispering begins.
You don't understand the suggestions, and you're second guessing what your friend knows or needs. 11. Originally Posted by GReaper Yes, efficient algorithms for spacial placement or grouping can be quite complicated. You can do without them though.

You can solve it by continuously iterating through the list of trees in order to find the ones that are close enough together. Then you compute the average of those, save it in another list and remove the processed trees from the examined list. Repeat until the list is empty and your new list will be full with unique, error-corrected trees. This process can be slow though, O(N²) to be exact, but it may be fast enough.
Thanks GReaper. That'll work. 12. Originally Posted by Salem And so the Chinese whispering begins.
You don't understand the suggestions, and you're second guessing what your friend knows or needs.
Hang on mate!
From the suggestions given, they are ALL understandable - even by me - who you know nothing about (except I'm not a c++ programmer).
And if you want to replace your "clever" tag, try the one from Bambi where Thumper's mother asks Thumper what his father said. 13. I started but didn't realise it was supposed to be C++. Oops, oh well. I didn't finish anyway, it seems like there is information missing from the problem description and I ended up in a big mess :/

But here's the start anyway
Code:
```#include <stdio.h>
#include <math.h>

#define PI_DIV_180 0.01745329251994329576923690768489
#define DEG_TO_RAD(a) ((a) * PI_DIV_180)

#define EARTH_RADIUS 6371   /* Approximate radius of the earth in km */

struct GeoCoord {
double lat, lon;
};

/* Convert latitude and longitude supplied in decimal degrees to radians
*/
struct GeoCoord *geo_toRadians(struct GeoCoord *p)
{
p->lat = DEG_TO_RAD(p->lat);
p->lon = DEG_TO_RAD(p->lon);
return p;
}

/* Calculate the great circle distance between two lat/long coords.
* Latitude and longitude for each point must be in radians.
* No error checking is performed.
*/
double geo_distance(const struct GeoCoord *p1, const struct GeoCoord *p2)
{
/* https://en.wikipedia.org/wiki/Haversine_formula
* https://en.wikipedia.org/wiki/Great-circle_distance
*/
double delta_lat, delta_lon,
a, b, c;

delta_lat = p2->lat - p1->lat;
delta_lon = p2->lon - p1->lon;

a = sin(delta_lat / 2); a *= a;
b = sin(delta_lon / 2); b *= b;
c = a + b * cos(p1->lat) * cos(p2->lat);
c = 2 * atan2(sqrt(c), sqrt(1 - c));

return c * EARTH_RADIUS;
}

int main(void)
{
struct GeoCoord tree1 = { 51.5074, -0.1278 };
struct GeoCoord tree2 = { 52.5200, 13.4050 };

printf("Distance %.2f metres\n", geo_distance(geo_toRadians(&tree1), geo_toRadians(&tree2))*1000);

return 0;
}```

EDIT: I guess I should ask. Is this assignment meant for a beginner? 14. Originally Posted by Hodor I started but didn't realise it was supposed to be C++. Oops, oh well. I didn't finish anyway, it seems like there is information missing from the problem description and I ended up in a big mess :/

But here's the start anyway

EDIT: I guess I should ask. Is this assignment meant for a beginner?
..... Point in case...  15. Originally Posted by userxbw ..... Point in case... I look forward to seeing your solution. You may use my distance function supplied above so you don't have to do that part Popular pages Recent additions #### Tags for this Thread

average, close, file, location, trees 