Like Tree1Likes

8 points in a circle around target point

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; "3) The rogue pit bull of the neighborhood, who has no zapper collar on, walks right through the perimeter, and ...

  1. #61
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    "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?

  2. #62
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    "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!

  3. #63
    Registered User
    Join Date
    Oct 2011
    Posts
    826
    Quote Originally Posted by Rick19468 View Post
    Does this method afford self "re-entry" back into the yard (no zapping or beeping)? .... then system must "self reset" to an armed status.
    Of course. My example code does not do that, as it's just an example of an one-off test.

    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):
    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. */
    }
    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.

    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.

    Quote Originally Posted by Rick19468 View Post
    Does this method afford crossing the outer polygon where needed? (ie: dog is allowed out the front door to roam only the front yard. The polygon is only in the front yard. The house is NOT then in the polygon. One line of the boundary now cuts across the front door!! .... dog gets ZAPPED! ... is your method "maskable" to this area?
    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.

    Quote Originally Posted by Rick19468 View Post
    This looks like your method requires the homeowner (during set-up) to record his primary yard points (polygon) offseted 3-4ft (warning buffer) from the real intended boundary.This would be unacceptable. The homeowner should have only to think about where the intended boundary line is desired and to walk to that point and "click" (recording that XY).
    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.

  4. #64
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @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!

  5. #65
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    "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.

  6. #66
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    "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)

  7. #67
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    "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.

  8. #68
    Registered User
    Join Date
    Oct 2011
    Posts
    826
    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".)

  9. #69
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    agreed! .... and thank you! : )

Page 5 of 5 FirstFirst 12345
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Plot Simple Points / Graph, X & Y array points
    By Khadafi in forum C++ Programming
    Replies: 9
    Last Post: 11-11-2011, 02:47 AM
  2. Point to lie on a circle. Help!
    By plus.c.plus in forum C++ Programming
    Replies: 8
    Last Post: 08-08-2011, 01:34 AM
  3. Points on circle
    By Suchy in forum C++ Programming
    Replies: 2
    Last Post: 11-16-2008, 02:08 PM
  4. point lies in circle?
    By cozman in forum Game Programming
    Replies: 3
    Last Post: 12-20-2001, 03:39 PM
  5. Finding a point within a circle
    By Unregistered in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2001, 08:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21