"3) The rogue pit bull of the neighborhood, who has no zapper collar on, walks right through the perimeter, and kills your dog"
...... yea?? ...... whats your point here?
"3) The rogue pit bull of the neighborhood, who has no zapper collar on, walks right through the perimeter, and kills your dog"
...... yea?? ...... whats your point here?
"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".
OK!
Of course. My example code does not do that, as it's just an example of an one-off test.Originally Posted by Rick19468
To achieve something like that, you need a state machine.
You need to store the dog's status, and a timer or a counter for how long the dog has remained in that status, and then decide what to do based on the three (old status, duration, new status):
Note that the duration variable indicates the number of cycles spent in that state, so initializing it to say zap_interval means the ZAP() condition will occur in the same cycle, re-setting the duration to zero. Think of it like a capacitor, charging. If the dog does not return, it will re-ZAP after zap_interval cycles.Code:static int8_t state; /* DOG_GONE, DOG_WARN, DOG_SAFE */ static uint16_t duration; /* since last ZAP or WARN */ static uint16_t warning_interval; static uint16_t zap_interval; /* The normal operation infinite loop: */ while (1) { int8_t new_state; new_state = check_location(...); if (new_state == DOG_SAFE) { /* We don't care how long the dog is in the yard, just that it is. */ state = DOG_SAFE; duration = 0; } else if (new_state == DOG_WARN) { if (state == DOG_SAFE) { /* Dog moved from safe to warning zone. Beep immediately. */ state = DOG_WARN; duration = warning_interval; } else if (state == DOG_GONE) { /* Dog returned, has one beep interval to get safe. */ state = DOG_WARN; duration = 0; } else { /* Dog remains in warning zone. */ duration++; } /* Time to beep? */ if (duration >= warning_interval) { duration = 0; BEEP(); } } else { /* DOG_GONE */ if (state != DOG_GONE) { /* Dog just got away. Zap immediately. */ state = DOG_GONE; duration = zap_interval; } else { /* Dog remains out. */ duration++; } if (duration >= zap_interval) { duration = 0; ZAP(); } } /* Fixed-length sleep here, so the counters don't advance too fast. */ }
The above code is just one example. I'd expect you to design and test the state machine throughly (even using just pen and paper, but checking all possible situations) before implementing it.
Sure. You'd need to create a polygon, say a small rectangle, where the dog is allowed to exit.
This requires a more complex dog state list. Perhaps
- Dog is safe
- Dog is in the warning zone (from safe)
- Dog is in the warning zone (returning from outside)
- Dog is in the exit zone
- Dog is outside without passing exit zone
- Dog is outside but has passed exit zone
Actually, here the circle method might come in very handy -- there is no reason why one could not merge the two approaches. The exit zones could be circular, so the owner just need to "mark" them with one click. (You can set the radius with another click.)
It is also possible to modify the function, of course. Each edge and each vertex can have their own warning distances, for example.
I did that intentionally: I'd rather have the warning buffer outside the safe area, rather than inside.
To me, the warning means "dog, you're not where you are supposed to be", not "don't go there, dog". Canines live in the moment, and seem to respond better to that sort of warnings.
But no, it is not inherent in my method. It is just an implementation detail I chose.
If you want the warning zone inside the polygon, the function can be adjusted to return 0 outside the polygon. Inside the polygon, considering your new requirements, you could compare the distance to each vertex and edge to a per-vertex or per-edge limit. It's not that big of a change to the function, actually.
(Your requirements do seem to change, as the discussion progresses. If I sound a bit negative, it is because it is a very common problem in software development, which I personally find excruciatingly frustrating. It is one of my many character flaws, sorry. If you can tell me exactly what you'd like to get from the polygon checking function, I think I could edit it to match.. but right now this feels like scattershot guesswork, where my efforts are unlikely to prove useful to anyone in the end.)
The way I thought about the situation is that the owner should walk the area where the dog may stay in peace, without warnings. Then the owner may mark areas that are expressly forbidden, by walking their exact boundaries.
If you have enough memory, you could even store different zones (yard, house), where transitioning is only allowed via certain points.
Have you done any real-life simulations? I mean, talk with other dog owners to see how they'd like to define the zones? How many zones are they likely to need? How accurate are the GPS units you'll use for local measurements?
I believe you're going to find that you'll need to add an EEPROM or flash chip to your device, to give it at least a few kilobytes of data memory to manage all the zone information. Even then you must think of how the state machine will behave if a brown-out occurs (battery power runs out), or a glitch causes the device to reset (clearing the state machine, or jumping it to an invalid state). There are a lot of details to consider and design for. You really should consider the big picture and real-world use cases before delving into the details like point-in-polygon testing, in my opinion.
@Nominal Animal:
I'm sorry for your frustration! : ( ... this was not my intent. Your very creative ideas have been most helpful. I never expected that you would have
proposed an entirely new method than mine ..... complete with the major core code!! : ) I do sincerely appreciate all your fine work and interest!
.... you should have asked me then of the projects requirements!
"Sure. You'd need to create a polygon, say a small rectangle, where the dog is allowed to exit." .....I take it that to add this new polygon, you would require the homeowner to manually edit the c code via a pc.
In my method I don't need to create a new polygon. As the homeowner "clicks" out his XY points in during his walk around the yard, he simply "double clicks" the two XY points in front of the door ..... indicating a "masked" zone ..... no pc or user intervention required!
"Actually, here the circle method might come in very handy -- there is no reason why one could not merge the two approaches. The exit zones could be circular, so the owner just need to "mark" them with one click. (You can set the radius with another click.)"
..... sorry! just read this part now : )
Last edited by Rick19468; 10-13-2012 at 08:55 PM.
"How accurate are the GPS units you'll use for local measurements?"
<3ft @ (hot start) <1ft after 10min (running with an on chip precision point position algorithm)
"You really should consider the big picture and real-world use cases before delving into the details like point-in-polygon testing, in my opinion."
... I disagree! The simplistic method of "Point-in-Poly" is the core engine of all the location iterations, including resolving the masking functions ..... all else .. are minor details.
There is absolutely no need to apologize! I just wanted to make sure that if there is any negativity in my post, it is because of a character flaw I have, not something I wanted to direct at anyone.
I think I should perhaps rephrase what I tried to say.
_ _
The first part of the polygon_distance() function I showed in post #48 in this thread is a very efficient implementation of the point-in-polygon test, very useful with a microcontroller such as the MSP430.
The second part of the function is a different approach, currently executed only for points outside the polygon, which calculates the distance to the perimeter of the polygon. (In other words, if you execute the second part with a point inside the polygon, it will return the shortest distance to outside the polygon.) It does require 32-bit integers in practice for 16-bit coordinates, perhaps 64-bit for some results, but as only additions, subtractions and multiplications are used, they don't need to be native, just supported by the compiler, for the code to be efficient. The one division is slow when emulated, but it is executed rarely enough that I don't think it should matter in practice.
The second part handles each vertex and each edge separately, using Cartesian coordinates and Pythagorean theorem (distance2 = x2 + y2) for the vertices, and point-line distance (see eq.(14) and eq.(16) in the Wolfram Mathworld article for example), after testing the point is perpendicular to the edge (within the edge segment -- otherwise the point is closer to one vertex). It computes the distance squared to each vertex and each edge, and returns the minimum.
If you want different behaviour overall, the function can be modified. For example, it can test whether it is some distance from a specific edge. Or you can store a distance for each edge and vertex, and the function can report whether it is inside the polygon, near the edges (inside), or just completely outside the polygon. The math implemented shows what is easily feasible.
_ _
At this point, you know you can trivially test whether a point is inside a polygon or not. You can also trivially find out the distance from any point to any fixed point, and therefore check whether a point is inside a circle (whose radius squared you know) just as easily.
You also know that it is possible to find out the distance from a point inside or outside a polygon to the polygon edge, and identify that edge. This is a bit more involved, requiring a few more variables, and sometimes a division operation using at least 32-bit integers (for 16-bit coordinates). If you can do without this, your implementation is easier. But if you need this, then you know you should be able to implement it even on MSP430, via larger-than-hardware-supports integers (emulation); the real downside is only that it requires a few more bytes of RAM, and is lots slower compared to the trivial checks mentioned above.
You have the mathematical tools you need, in other words. Now is the point where you start looking at your use cases, and considering what you wish your device to do, and whether the above operations are enough. (I believe they are, that they can be used to solve all the scenarios you've posed in this thread thus far.)
_ _
I feel that we are drifting too far from the original question, so if you have followup questions, I think you should start a new topic. Your original question was about eight points around a target point, and we've gotten miles away.
If you start a new thread, where you describe your next problem, your solution, and whatever difficulties you're having with it -- rather than us getting further and further away in this thread from the original topic -- the results won't be lost inside a meandering topic started under a completely different thread title.
After all, we should hope the question and discussion and solutions should be useful to others, too, if they encountered a similar situation. Right?
At least, that is the reason I'm here. Not to help you personally, but to make sure the stuff I've discovered along the road -- and especially the discoveries I (and to a lesser extent, others here -- I'm being honest about my selfishness here!), make when somebody poses a good puzzle or question, is described in an useful form and available to anyone interested. I love to see what others can build when we help them with a solid foundation; it gives me the warm fuzzies. (And I'm absolutely, literally addicted to solving puzzles. Especially ones labeled "impossible".)
agreed! .... and thank you! : )
