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

  1. #1
    Registered User
    Join Date
    Dec 2017
    Posts
    5

    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. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    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?
    Devoted my life to programming...

  4. #4
    Registered User
    Join Date
    Dec 2017
    Posts
    5
    Quote Originally Posted by Salem View Post
    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. #5
    Registered User
    Join Date
    Dec 2017
    Posts
    5
    Quote Originally Posted by GReaper View Post
    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. #6
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    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.
    Last edited by GReaper; 12-07-2017 at 05:51 AM.
    Devoted my life to programming...

  7. #7
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    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
    Last edited by Hodor; 12-07-2017 at 06:00 AM.

  8. #8
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    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.
    Devoted my life to programming...

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    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.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Quote Originally Posted by Grumps View Post
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  11. #11
    Registered User
    Join Date
    Dec 2017
    Posts
    5
    Quote Originally Posted by GReaper View Post
    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. #12
    Registered User
    Join Date
    Dec 2017
    Posts
    5
    Quote Originally Posted by Salem View Post
    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.
    Last edited by Grumps; 12-07-2017 at 06:58 AM.

  13. #13
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    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?
    Last edited by Hodor; 12-08-2017 at 03:30 AM.

  14. #14
    Banned
    Join Date
    Aug 2017
    Posts
    861
    Quote Originally Posted by Hodor View Post
    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. #15
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by userxbw View Post
    ..... 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 subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 05-02-2016, 08:47 PM
  2. Replies: 1
    Last Post: 11-04-2010, 10:23 AM
  3. Replies: 21
    Last Post: 11-03-2007, 02:56 PM
  4. FILE I/O. data written at wrong location.
    By epidemic in forum C++ Programming
    Replies: 5
    Last Post: 04-06-2007, 12:45 AM
  5. Tracking item location in inventory
    By Mario F. in forum Game Programming
    Replies: 6
    Last Post: 08-02-2006, 03:50 PM

Tags for this Thread