How accurate is your GPS?
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?...
How accurate is your GPS?
Fact - Beethoven wrote his first symphony in C
@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
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:
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.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; }
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:
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:/* 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 } };
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.)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); }
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.)
@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 07:35 PM. Reason: .... more info
@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.
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 08:55 PM.
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
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).
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 (x^{2} + y^{2} = distance^{2}, 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.
@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.
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?
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.
@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.