Thread: 8 points in a circle around target point

@Nominal Animal: "Why not do a separate polygon for the warning area?"
Yes! .... thats what i've wanted from the start. But didnt know how to "shrink" or "expand" the complex Polygon .... Matrix scaling looks like what I need?

@Nominal Animal:"You could walk the perimeter to get the safe area polygon first, then visually edit it to add the warning area."
The 8 points around the dog method works just fine as is without any user set-up intervention or knowlage. But If I can simply "shrink" the initial yard boundary down 3 ft by scaling down, I can do away with the 8 points around the dog and the loop iterations go from 9 to 2!

@Nominal Animal:"....you could calculate the distance to the nearest edge or vertex"
Yes ... lets say you measure up,down,left and right for the nearest boundary. That would work fine .... til the dog comes up on a 90 degree inside corner! Here the measuring lines wound miss the "closest boundary" , the 90 degree corner right next to him! The dog would be ZAPPED without warning. The only way around this is to measure not only L,R,U and D ..... but also at 45 degrees from these points ... total of 8 lines! ..... my "8 fixed points" around the dog, and follows the dog, already does this job for me as is.

I found this:
Polygon TransformationPerforms basic transformations like translation, scaling and rotation on a polygon of your choice.Download (47KB)http://vineetv.tripod.com/turboc.htm

It looks like what I need! ..... but the c code demo will not run correctly on my pc for some reason. Can you look at this demo (inside the zipped folder) and see if this will do the down and up scaling for me? Thanks!

A few hours of research later, here's what I came up with:

Code:

/* Return 0 if point is inside polygon.
 * Otherwise, return the minimum distance squared to the polygon.
 * The result is never negative (unless integer overflow occurs).
*/
static int polygon_distance(const int point_x, const int point_y, const int poly_x[], const int poly_y[], const int n)
{
    /* Check if inside the polygon. */
    {

        int  curr_x = poly_x[0] - point_x;
        int  curr_y = poly_y[0] - point_y;

        char  cross = 0;
        int   i = n;

        while (i-- > 0) {
            const int next_x = curr_x;
            const int next_y = curr_y;

            curr_x = poly_x[i] - point_x;
            curr_y = poly_y[i] - point_y;

            if ((next_y > 0) != (curr_y > 0)) {
                const int delta_x = next_x - curr_x;
                const int delta_y = next_y - curr_y;

                if (curr_y > next_y)
                    cross ^= ((next_x * delta_y) < (delta_x * next_y));
                else
                    cross ^= ((next_x * delta_y) > (delta_x * next_y));
            }
        }

        if (cross)
            return 0;
    }

    /* Outside the polygon.
     * Calculate the shortest distance to a vertex or an edge. */
    {
        int  minimum = (poly_x[0] - point_x) * (poly_x[0] - point_x)
                     + (poly_y[0] - point_y) * (poly_y[0] - point_y);
        int  curr_x = poly_x[0] - point_x;
        int  curr_y = poly_y[0] - point_y;
        int  i = n;

        while (i-- > 0) {
            const int  next_x = curr_x;
            const int  next_y = curr_y;

            curr_x = poly_x[i] - point_x;
            curr_y = poly_y[i] - point_y;

            /* New closest vertex? */
            {
                const int dd = curr_x * curr_x + curr_y * curr_y;
                if (dd < minimum)
                    minimum = dd;
            }

            /* Distance to edge? */
            {
                const int delta_x = next_x - curr_x;
                const int delta_y = next_y - curr_y;
                const int delta_sqr = delta_x * delta_x + delta_y * delta_y;
                const int along = next_x * delta_x + next_y * delta_y;

                /* Is the point perpendicular to the edge?
                   Don't bother for very short segments. */
                if (delta_sqr >= 4 && along >= 0 && along <= delta_sqr) {

                    /* Compute the distance to the edge. */
                    const int cross = curr_x * next_y - curr_y * next_x;
                    const int dsqr = cross * cross;
                    if (dsqr >= 0 && dsqr < delta_sqr * minimum)
                        minimum = dsqr / delta_sqr;
                }
            }

        }

        return minimum;
    }
}

I tried to write it in a form easy to adapt to a microcontroller. In particular, there is just one division, and it is only done when necessary. As a result, it should be possible to implement the above algorithm even on a slow 8-bit microcontroller, using 16-bit coordinates (although you'll need 32-bit integer addition, subtraction, and multiplication, plus the 32-bit division if you want the minimum distance to the polygon.)

If you only need the point-in-polygon test, you can simply omit the second part of the function altogether.

The first part I cooked up using the best bits of a couple of variants I found. I must admit I'm pretty happy with it, as it does just two multiplications and four subtractions per polygon point, plus two subtractions for overhead. The second part is pretty much unoptimized, as it is only used when the point is outside the polygon. It just computes the squared distances to each vertex, and for each edge where the point is between the endpoints, it computes the squared distance from the point to the line; and picks the minimum of these.

(I consider the above code either trivial (non-copyrightable), or if copyrightable, then either Public Domain or licensed under Creative Commons CC0. In other words: feel free to use it in any way you like, but don't blame me if something goes wrong.)

The way to use this function is simple: Set up an extra value for each polygon; the warning area thickness squared. If the function returns 0 for the polygon, then the point is inside the polygon. Otherwise, if the function result is smaller than the warning area thickness squared, then the point is in the warning area. Otherwise, the point is outside the warning area (ZAP! time).

This way you can have different warning area thicknesses for each polygon. Also, your exclusion zones can, but do not have to, have a warning area. (Exclusion zone warning area only extends into the safe area, so you need to be careful in which order you check the zones.)

In practice, I would check all exclusion zones first. If inside one, ZAP!. If inside the warning zone, then BEEP!. Otherwise, check the safe zones. If inside one, GOOD DOG. If in the warning area, BEEP!. Otherwise, ZAP.

If you want an editor for the polygons, I think I could cook one up using Python and PyQt4.

I hope you find this useful!

@Nominal Animal:"Set up an extra value for each polygon?" ..... explain please! (at a novice level)

(I assume your referring to the depth of the warning zone before the dog exceeds the yard boundary line here)

Originally Posted by Rick19468

(I assume your referring to the depth of the warning zone before the dog exceeds the yard boundary line here)

Yes, except it is constant for the entire polygon.

Consider the following image:
Attachment 12060
The green area is defined by 17 points, and is the actual polygon. In this region, polygon_distance() will return 0.

The blue area is 16 pixels wide; 16² = 256. In the blue area, the function will return values between 1 (just outside the green area) and 288 (on the very edge, 17² = 289). Outside, the function will return > 288.

The polygon_distance() function does not care about what the boundary thickness is, as it just returns the (squared) minimum distance to the polygon. Thus, each polygon you have, can have their own boundary thickness.

In practice, for each polygon you will need to store:
- N, the number of points in the polygon
- the x and y coordinates, 2 × N numbers
- the boundary thickness, a single number

Because the boundary thickness is always positive, you can save memory by using a negative boundary thickness for exclusion polygons -- say flower beds. The procedure I mentioned earlier, where you check the exclusion polygons and their boundaries first, and only if outside, check the safe polygons and their boundaries, avoids any ambiquities, and is easy to set up -- you walk the safe areas first, then the exclusion polygon, and it works just like you'd expect it to. If you do it some other way, you might have strangeness if an exclusion polygon is not entirely within a safe polygon; possibly allowing the doggie where it's not supposed to be allowed to.

As a result, I'd expect your polygon data to be arranged something like the following on an MSP430 (but note, I'm using stdint.h types; not familiar with MSP430):

Code:

#define  POLYGONS    6
#define  POINTS_MAX  9

static uint8_t  polygon_points[POLYGONS] = { 0 }
static int16_t  polygon_x[POLYGONS][POINTS_MAX];
static int16_t  polygon_y[POLYGONS][POINTS_MAX];
static int16_t  polygon_boundary[POLYGONS] = { 0 };

/* Memory use: 3*POLYGONS + 4*POLYGONS*POINTS_MAX = 234 bytes */

If your MSP430 has 256 bytes of data flash, and you can use 234 bytes of it for the polygons, then you can have up to 6 polygons with up to 9 points each, using this scheme.

Note that since the boundary is only 16-bit, you're limited to sqrt(2¹⁵ - 1) - 1 = 126 units for the boundary thickness (three or four yards using one-inch units).

Assuming the above data structures, your doggie location test could be:

Code:

#define  DOG_SAFE 0
#define  DOG_NEAR 1
#define  DOG_GONE 2

#define  NEAR_EXCLUSION 1
#define  NEAR_SAFE 2

uint8_t check_location(const int16_t x, const int16_t y)
{
    int8_t near = 0;
    int16_t p;

    /* Check exclusion polygons, with negative boundary. */
    for (p = 0; p < POLYGONS; p++)
        if (polygon_points[p] > 2 && polygon_boundary[p] < 0) {
            const uint16  distance_squared = polygon_distance(x, y, polygon_x[p], polygon_y[p], polygon_points[p]);
            if (!distance_squared)
                return DOG_GONE;
            else
            if (distance_squared < (uint16_t)(-polygon_boundary[p])
                near |= NEAR_EXCLUSION;
        }

    /* Check for allowed polygons, with positive boundary. */
    for (p = 0; p < POLYGONS; p++)
        if (polygon_points[p] > 2 && polygon_boundary[p] > 0) {
            const uint16  distance_squared = polygon_distance(x, y, polygon_x[p], polygon_y[p], polygon_points[p]);
            if (!distance_squared) {
                /* Dog is in a safe polygon, but possibly near an exclusion polygon. Warn if so. */
                return (near & NEAR_EXCLUSION) ? DOG_NEAR : DOG_SAFE;
            } else
            if (distance_squared < (uint16_t)(-polygon_boundary[p])
                near |= NEAR_SAFE;
        }

    /* In the warning zone? */
    if (near & NEAR_SAFE)
        return DOG_NEAR;

    /* Dog is either outside, or outside in the warning boundary for an exclusion zone. */
    return DOG_GONE;
}

I very warmly recommend writing some test cases to see how it really works in practice. I use either Python and PyGTK+ or PyQt4, or C with output to PPM images. Using a color based on the result value makes it easier to understand how it all works.

....... of course you could include the house itself in the front yard only poly by plotting all the corners of the house as well and making choking off points to any side yard paths out of the front yard.

Do able .... but not desirable for the end user.

My coding allows for "masking out" line vertices between two points (hole in fence) very easily (ie: front door) . In the rare occasion that my "Y" checking "ray" be in very close and parallel to real earth longitude (front door of house in parallel with earth longitude) .... I can easily check for this at set-up and polar rotate my poly. This need be done only one time and handled automatically in code.

..... In a premium version, I could attach a wifi module that would assist in the fence boundary set-up .... eliminating any physical external programming buttons needed on the unit itself (think of water and sweat entry protection in this harsh environment).

Then, params could be wirelessly set or changed (ie: set XY points, flag masked areas, adjust buffer zone, adjust ZAP strength and duration, etc.)

..... email or text to cell when dog escapes out of yard

...... dog geo linked to Google maps to find lost dog, etc.

"Not for those large properties." ......... ??????? you lost me here! : (

COST?? .... well .... in my RFID version of this system, the cost and size have dropped low enough to make entry into the general consumer market. The entire reader (mounted on dogs collar) in now the size of a postage stamp with the MCU now built right into the IC! I designed the wireless ZAP module the same size and linked them both together wirelessly with a bi-directional RF link the size of 1mm x 1.5 mm!

When things get this small ... they can be made very affordable.

If this is for an actual dog enclosure, then you need to address the problems inherent to them:

1) The power goes off, and now the dog is running free
2) The dog spies the neighbors cat, squirrel, or another dog, and charges right through the perimeter - zap, what zap?.
3) The rogue pit bull of the neighborhood, who has no zapper collar on, walks right through the perimeter, and kills your dog
4) The neighbors kid wanders inside the perimeter, and your dog bites him/her. There is no physical barrier, so your dog could be legally construed as an "attractive nuisance".

You can get an earful on the subject in the Craigs List Pet Discussion forum (global, not local).

"1) The power goes off, and now the dog is running free"

... you mean battery in this case I think, ....no! , most dogs after a few learning ZAP's never challenge the fence again. Its all in the initial training. I don't even have a battery in my dogs collar for the last 3 months! ... yet he stays in the yard!

"2) The dog spies the neighbors cat, squirrel, or another dog, and charges right through the perimeter - zap, what zap?."

.... that will be the last time he does it! : )