How accurate is your GPS?

Printable View

- 10-11-2012Click_here
How accurate is your GPS?

- 10-11-2012Rick19468
- 10-11-2012oogabooga
@Rick

**: OK!!! I GET IT!!! It's just that you kept using the word CIRCLE!!!** - 10-11-2012Rick19468
- 10-11-2012Rick19468
- 10-11-2012Nominal Animal
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;

}

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 }

};

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);

}

*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.) - 10-11-2012Rick19468
**@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. - 10-11-2012Rick19468
**@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. - 10-11-2012Rick19468
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. - 10-11-2012oogabooga
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. :) - 10-11-2012Nominal Animal
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. - 10-11-2012Rick19468
@

**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. - 10-11-2012Rick19468
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? - 10-11-2012Nominal Animal
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. - 10-11-2012Rick19468
**@**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**.**