Like Tree1Likes

8 points in a circle around target point

This is a discussion on 8 points in a circle around target point within the C Programming forums, part of the General Programming Boards category; How accurate is your GPS?...

  1. #16
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,344
    How accurate is your GPS?
    Fact - Beethoven wrote his first symphony in C

  2. #17
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    Quote Originally Posted by oogabooga View Post
    So the dog is confined to an octagon?
    And the warning zone is also an octagon (not a circle)?

    Exactly how is the dog moving?

    Another point:
    For the following variables, if only one at a time is ever supposed to be 1, then you can replace them by an enumeration:
    Code:
    int status_a = 0;
    int status_b = 0;
    int status_c = 0;
    
    // replace them with:
    enum {STATUS_INSIDE, STATUS_WARNING, STATUS_OUTSIDE} status = STATUS_INSIDE;

    NO! ... they are, at any give time, 0 or 1 independently.


    This is needed because if dog gets out of yard .... he is allowed self "re-entry without again getting BEEPED or ZAPPED!
    Last edited by Rick19468; 10-11-2012 at 06:06 PM. Reason: ....more info

  3. #18
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    @Rick: OK!!! I GET IT!!! It's just that you kept using the word CIRCLE!!!
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  4. #19
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    Quote Originally Posted by Click_here View Post
    How accurate is your GPS?
    <3ft @ (hot start) <1ft after 10min

  5. #20
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    Quote Originally Posted by oogabooga View Post
    @Rick: OK!!! I GET IT!!! It's just that you kept using the word CIRCLE!!!

    .....sorry! : ( .... 8 points evenly distributed around my center point : ) Why 8? .... app does not need any more resolution than this to do it's job adequately.

  6. #21
    Registered User
    Join Date
    Oct 2011
    Posts
    838
    I'm with Oogabooga on this.

    It is much more efficient to map the yard using circles; just make sure they overlap. Consider the following:
    Code:
    struct point {
        float  x;
        float  y;
    };
    
    struct circle {
        struct point  center;
        float         radius;
    };
    
    int within(const struct point dog, const struct circle circle[], const int circles)
    {
        int    i = circles;
    
        while (i-- > 0)
            if (dog.x - circle[i].center.x) * (dog.x - circle[I].center.x) + (dog.y - circle[i].center.y) * (dog.y - circle[i].center.y) < circle[i].radius * circle[i].radius)
                return 1;
    
        return 0;
    }
    You can map your "safe area" using one set of circles, and the warning area using another. If you save also the square of the radius of each circle, then the check is just three substractions or additions and two multiplications per circle.

    If your GPS also provides direction information, you can also tell whether the dog is looking outwards of the safe area or not. First, you'll need a table which maps the direction into a vector. You don't need that many directions, maybe thirty or so:
    Code:
    /* 36 direction vectors. 0 = (+1, 0), 9 = (0, +1), and so on. Length is 1. */
    static const struct point  direction_vector[36] = {
        { .x =  1.0000000, .y =  0.0000000 },
        { .x =  0.9848078, .y =  0.1736482 },
        { .x =  0.9396926, .y =  0.3420201 },
        { .x =  0.8660254, .y =  0.5000000 },
        { .x =  0.7660444, .y =  0.6427876 },
        { .x =  0.6427876, .y =  0.7660444 },
        { .x =  0.5000000, .y =  0.8660254 },
        { .x =  0.3420201, .y =  0.9396926 },
        { .x =  0.1736482, .y =  0.9848078 },
        { .x =  0.0000000, .y =  1.0000000 },
        { .x = -0.1736482, .y =  0.9848078 },
        { .x = -0.3420201, .y =  0.9396926 },
        { .x = -0.5000000, .y =  0.8660254 },
        { .x = -0.6427876, .y =  0.7660444 },
        { .x = -0.7660444, .y =  0.6427876 },
        { .x = -0.8660254, .y =  0.5000000 },
        { .x = -0.9396926, .y =  0.3420201 },
        { .x = -0.9848078, .y =  0.1736482 },
        { .x = -1.0000000, .y =  0.0000000 },
        { .x = -0.9848078, .y = -0.1736482 },
        { .x = -0.9396926, .y = -0.3420201 },
        { .x = -0.8660254, .y = -0.5000000 },
        { .x = -0.7660444, .y = -0.6427876 },
        { .x = -0.6427876, .y = -0.7660444 },
        { .x = -0.5000000, .y = -0.8660254 },
        { .x = -0.3420201, .y = -0.9396926 },
        { .x = -0.1736482, .y = -0.9848078 },
        { .x = -0.0000000, .y = -1.0000000 },
        { .x =  0.1736482, .y = -0.9848078 },
        { .x =  0.3420201, .y = -0.9396926 },
        { .x =  0.5000000, .y = -0.8660254 },
        { .x =  0.6427876, .y = -0.7660444 },
        { .x =  0.7660444, .y = -0.6427876 },
        { .x =  0.8660254, .y = -0.5000000 },
        { .x =  0.9396926, .y = -0.3420201 },
        { .x =  0.9848078, .y = -0.1736482 }
    };
    Dot product (p1.x * p2.x + p1.y * p2.y) between the direction vector and the position of the dog relative to the center of a circle, will be positive when the dog is facing outward, 0 when the dog is parallel to the perimeter, and negative when dog is facing toward the center of the area. In other words, given the yard centerpoint,
    Code:
    float outwards(struct point dog, const int direction, struct point center)
    {
        struct point  relative;
    
        relative.x = dog.x - center.x;
        relative.y = dog.y - center.y;
    
        return (direction_vector[direction].x * relative.x + direction_vector[direction].y * relative.y);
    }
    will tell you if the dog is facing outwards (positive), parallel to the yard perimeter (about zero) or towards the center of the yard (negative). If the direction vector length is one, as it is here, then the value is scaled by the dog's distance from the centerpoint. (Thus, the dog looking parallel to the perimeter, at any distance, will return zero. The dog looking outwards, will return the dogs distance from the center. The dog looking directly at the centerpoint, will return the dogs distance from the center negative.)

    On a microcontroller you cannot usually use the float type, or it will be excruciatingly slow because it is emulated. Fortunately, fixed-point integers work very well in that case. On 32-bit, you can use normal ints, just multiplying everything by 65536 (16-bit fractional part) to get -32768.00000 .. 32767.99999. On 8-bit ones, I'd use one byte fractional part and one or two bytes integral, yielding -128.00 .. 127.99 or -32768.0 .. 32767.99 respectively. Summation is trivial, but for multiplication you use high multiply, an operation these devices have where they return only the high part of the result (essentially dividing the result by maximum unsigned value + 1).

    For a one-off piece of hardware, I'd use one of the STM32 Discovery kits. They're extremely cheap (< $20), but you cannot use them in a product; they're only for development. They might be a bit large for a doggie to wear, though.

    If you want, I can show exactly what such a fixed-point code would look like. Usually these devices also have more read-only-memory (ROM or flash) than RAM; I can also show how to minimize RAM usage, while putting all the yard data in static constants, and making the calculations fast. (I'm itching for my Teensy 3.0 to arrive; I love the earlier one, but I feel limited by its 8-bit AVR core.)
    oogabooga likes this.

  7. #22
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @Nominal Animal: Hi! Thanks for this concept idea! .... I just wish I knew what the hell your saying! : ) (I'm about 1 week into programming)

    Why would I care to know the direction of the dog? I am simply testing if he is "in" or "out" of the yard.

    Even if I have a protected area within the yard (ie: flower garden, pool, etc) ... the code can resolve this as well.

    The safe "self re-entry" back into the yard is also afforded in this code.

    I agree ... I'm sure I don't need "float" precision for this app. I will change that.
    Last edited by Rick19468; 10-11-2012 at 06:35 PM. Reason: .... more info

  8. #23
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @Nominal Animal: You can map your "safe area" using one set of circles, and the warning area using another.

    In my code, instead of surrounding the dog with "8 points" for the warning detection .... I could just shrink the yard boundary (lets say 3 ft) when I testing for entry into the warning zone. Then I can just use the one (real location of dog) point .... but shrinking a polygon is not so easy to do and must be expanded if in protected area is inside the yard.

  9. #24
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    Can anyone show me how to shrink or expand a complex non-symmetrical polygon (w/convex and concave vertices)?
    My 8 point polygon XY[8] shown in my code would be great.

    I could then do away with the 8 points around the dog. Loop iteration would go from 9 down to just two!

    Also ... code to shrink or expand the polygon is done only one time at initial set up .... and never used again during normal operation.
    Last edited by Rick19468; 10-11-2012 at 07:55 PM.

  10. #25
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by Rick19468 View Post
    I agree ... I'm sure I don't need "float" precision for this app. I will change that.
    It's not a matter of precision but one of performance. A 32-bit float will actually have LESS precision than a 32-bit int used as a fixed-point value, since the fixed-point representation doesn't have an exponent. "Floating-point" does not actually refer to the possibility of having a fractional part, but to the fact that the position of the binary-point is not fixed but "floats".

    As for direction information, I think nominal was just pointing out the feasibility of it, if you were interested.

    I had no idea that this is something you actually want to create in the real world! I thought it was just a simulation. Interesting.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  11. #26
    Registered User
    Join Date
    Oct 2011
    Posts
    838
    Quote Originally Posted by Rick19468 View Post
    Why would I care to know the direction of the dog? I am simply testing if he is "in" or "out" of the yard.
    Doggie psychology. When the dog stops doing the unwanted thing, you want to immediately remove the "bad dog" signal.

    Assume the dog is at the boundary. If the dog is facing outwards, you could now and then give a gentle "get away from the boundary" warning. If the dog is facing inwards, there is no need for the warning.

    As social animals, dogs are quite good at catching that sort of things. (Most people don't realize how contradicting signals they're giving their dogs; I believe that is the single major cause of problems.)

    The same direction logic works for movement, too. For example, the ultra-cheap (< $20) STM32F4Discovery boards have 3-axis accelerometers, which would tell you which direction (relative to the board) the dog is moving. You could add a digital gyroscope, or perhaps a digital compass, to determine the orientation of the board; then you'd get pretty reliable data on which direction the dog is going/facing (albeit probably at quite poor directional resolution).

    Quote Originally Posted by Rick19468 View Post
    I just wish I knew what the hell your saying! : ) (I'm about 1 week into programming)
    I'd be happy to clarify it, and/or to try and answer any questions you might have about the vector/circle logic I described. I just don't know where to begin, because I don't know your background.

    All of it does boil down to Pythagorean theorem (x2 + y2 = distance2, because x and y axes are perpendicular), and the Geometric interpretation of the dot product, as x and y are Cartesian coordinates. The basic 2-dimensional vector geometry is very, very useful in real life; you eventually notice you basically never need sin() and cos() anymore. When you do, CORDIC will get you there on a microcontroller.

  12. #27
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @Nominal Animal I hear ya! Thanks! ..... but my dog can easily side step or walk backwards over the boundary. So direction is not definitive for a different recourse.

  13. #28
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    Question: To shrink a complex polygon, cant I simply calculate the line length between each vertices, then subtract lets say 3ft from each line to form the new polygon?

    ..... and still preserve the original shape?

  14. #29
    Registered User
    Join Date
    Oct 2011
    Posts
    838
    Quote Originally Posted by Rick19468 View Post
    Question: To shrink a complex polygon, cant I simply calculate the line length between each vertices, then subtract lets say 3ft from each line to form the new polygon?
    No, not substract. Multiply.

    You can shrink any polygon by multiplying the coordinates by a constant. To reduce the size by 25%, you'd multiply by 75% or 0.75.

    Note that that will cause the polygon to be moved towards the origin (0,0). You can counteract that by calculating the center -- in this case the center is an average of the coordinates --, and subtracting the center coordinates before the multiplication, and adding them back.

    However, the shape you get is not really what you need, especially for convex polygons, because the "safe area" polygon is not just a smaller version of the original polygon; it has a different shape.

  15. #30
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @Nominal Animal: "However, the shape you get is not really what you need" ..... so, I'll take that as a NO! : ( ..... I know the are libraries that can do this (ie: "clipper")
    This is why I came up with the idea of just surrounding the dog with a ring of points, distant from the dog's real location, to afford an early warning indication.

Page 2 of 5 FirstFirst 12345 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Plot Simple Points / Graph, X & Y array points
    By Khadafi in forum C++ Programming
    Replies: 9
    Last Post: 11-11-2011, 02:47 AM
  2. Point to lie on a circle. Help!
    By plus.c.plus in forum C++ Programming
    Replies: 8
    Last Post: 08-08-2011, 01:34 AM
  3. Points on circle
    By Suchy in forum C++ Programming
    Replies: 2
    Last Post: 11-16-2008, 02:08 PM
  4. point lies in circle?
    By cozman in forum Game Programming
    Replies: 3
    Last Post: 12-20-2001, 03:39 PM
  5. Finding a point within a circle
    By Unregistered in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2001, 08:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21