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; 162 = 256. In the blue area, the function will return values between 1 (just outside the green area) and 288 (on the very edge, 172 = 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(215 - 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.