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; Another approach you could consider, is creating a bit map of the safe area (and another of the warning zone, ...

  1. #31
    Registered User
    Join Date
    Oct 2011
    Posts
    838
    Another approach you could consider, is creating a bit map of the safe area (and another of the warning zone, if you want). Using S for set safe bitmask bits, W for set warning and safe zone bitmask bits, and . for unset bits, this could look like
    Code:
     (0,0)
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . W W . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . W W W . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . W W W W . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . W W W W W . . . . . . . . . . . . . . . . . . .
        . . . . . . . . W W W S W W W . . . . W W W . . . . . . . . . .
        . . . . . . . . . W W S S W W W W W W W W W W . . . . . . . . .
        . . . . . . . . . W W W S S W W W W W W S W W W . . . . . . . .
        . . . . . . . . . . W W S S S S W W W S S S W W W . . . . . . .
        . . . . . . . . . . W W S S S S S S S S S S S W W W W . . . . .
        . . . . . . . . . . W W S S S S S S S S S S S S W W W W . . . .
        . . . . . . . . . . W W S S S S S S S S S S S S S W W W W . . .
        . . . . . . . . . W W W S S S S S S S S S S S S S S S W W W . .
        . . . . . . . . . W W S S S S S S S S S S S S S S S W W W W W .
        . . . . . . . . . W W S S S S S S S S S S S S S W W W W W . . .
        . . . . . . . . W W S S S S S S S S S S S S W W W W W . . . . .
        . . . . . . . . W W S S S S S S S S S S S W W W W . . . . . . .
        . . . . . . . . W W S S S S S S S S S S S W W . . . . . . . . .
        . . . . . . . . W W S S S S S S S S S S S W W . . . . . . . . .
        . . . . . . . W W W S S S S S S S S S S W W W . . . . . . . . .
        . . . . . . . W W W W S S S S S S S S S W W . . . . . . . . . .
        . . . . . . . W W W W W W W S S S S S S W W . . . . . . . . . .
        . . . . . . . . . . W W W W W W S S S W W W . . . . . . . . . .
        . . . . . . . . . . . . . W W W W W W W W . . . . . . . . . . .
        . . . . . . . . . . . . . . . W W W W W W . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . W W . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
                                                                    (31,31)
    The above uses your original coordinates. I think.

    The above two bitmaps only need 1024 bits, or 128 bytes of storage per bitmap. In flash or ROM on a microcontroller, of course. If the warning zone is at the edge only, then you only need one bitmap; you can easily test if one of the four (or eight) neighboring bits is zero. Checking if there is a zero bit in a rectangular area around some coordinates is also easy.

    For 64x64, you need 512 bytes per bitmap. For 128x128, 2048 bytes. For 256x256, 8192 bytes per bitmap. And so on: width height / 8 bytes.

    You could use
    Code:
    static const unsigned char safe_bitmap[HEIGHT][WIDTH/8] = { ... };
    
    static inline int safe(const int x, const int y)
    {
        if (x >= 0 && y >= 0 && x < HEIGHT && y < WIDTH)
            return !!(safe_bitmap[y][x / 8] & (1U << (x & 7)));
        else
            return 0; /* Not safe! */
    }
    
    static inline int warn(const int x, const int y)
    {
        return !(safe(x-1, y-1) && safe(x, y-1) && safe(x+1, y-1) &&
                 safe(x+1, y) && safe(x+1, y+1) && safe(x, y+1) &&
                 safe(x-1, y+1) && safe(x-1, y));
    }
    where !!(expression) is the not not operator. It just returns false/0 when (expression) is also false/zero, and true/1 otherwise. This way the function returns 1 if in a safe pixel, 0 otherwise. You can omit the !! if it bugs you; then the function returns nonzero when safe, 0 otherwise.

    The warn() above is simplistic, returning true/1 if there is at least one unsafe pixel around the coordinates, and false/0 otherwise. There are more efficient ways of coding it, especially detecting unsafe areas from further (multiple pixels) away.

    If the doggie is outside the safe area, (!safe(dog_x, dog_y)), ZAP!. Otherwise, if (warn(dog_x, dog_y)), BEEP!. Otherwise, GOOD DOG.
    Last edited by Nominal Animal; 10-11-2012 at 09:39 PM.

  2. #32
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @Nominal Animal (REM: I don't know anything) .... but that looks like it would require a large amount of memory in my small MCU (MPS430) . Think of a resolution of 6" over a 5 acre property.

    Can you tell me why my "point-in-poly" approach is not to your liking?

    I'm a complete novice ..... but it works great! .... in every requirement.

    I can even "mask-out" areas along a permanent barrier (ie: a real fence or entry into the house) to allow the dog full use of the yard right up to the real fence. This also allows a simpler initial set up of the multi-point boundary.

  3. #33
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,344
    but that looks like it would require a large amount of memory in my small MCU (MPS430)
    How much memory do you have? There appear to be 20 versions of your chip that all have different memory. Over 5 acres, you do not need 1ft accuracy -> I think that 2m squared would be great. What area are you dealing with for your project?

    A look up table would be the fastest run time approach, so you would be silly to not consider it.

    I don't like your poly approach because you are not using sin or cos to work out your coordinates.
    Last edited by Click_here; 10-11-2012 at 10:42 PM.
    Fact - Beethoven wrote his first symphony in C

  4. #34
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,231
    O_o

    Okay.

    I know this has been asked, but I didn't see an answer so I have to ask again: what is wrong with the overlapping circles?

    Soma

  5. #35
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @Click_here: "What area are you dealing with for your project?"

    Could be 5 or 10 acres or just a small suburban home with real side fences on both sides and back yard,... but with an open 25' yard front.

    @Click_here: "I don't like your poly approach because you are not using sin or cos to work out your coordinates."
    Do I need to! It works! : (

    @Click_here: "A look up table would be the fastest run time approach"
    I could do that too .... but runs very fast now!

  6. #36
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    Quote Originally Posted by phantomotap View Post
    O_o

    Okay.

    I know this has been asked, but I didn't see an answer so I have to ask again: what is wrong with the overlapping circles?

    Soma


    Does not allow for "self re-entry" ..... for one thing
    Boundary and warning zones would have "dead spots" I would think and a night mare to set up.





    Can you tell me more of is features?
    Last edited by Rick19468; 10-11-2012 at 10:59 PM. Reason: more...

  7. #37
    Registered User
    Join Date
    Oct 2011
    Posts
    838
    Quote Originally Posted by Rick19468 View Post
    Think of a resolution of 6" over a 5 acre property
    Inches and acres, grumble.. Okay, that means about a million samples, with each sample being about 6"6" ≃ 0.15m0.15m.

    MSP430 is 16-bit, so let's use something like 1" coordinate units -- you should choose it wisely, looking at your GPS output first -- so you get about 13-bit range of coordinates, but won't have to change code if you get a bigger yard. And you can work with integer coordinates without hassle, since the units are small enough compared to the resolution you need.

    Quote Originally Posted by Rick19468 View Post
    Can you tell me why my "point-in-poly" approach is not to your liking?
    Well, the circle method is just faster and simpler. I don't have anything specific against the point-in-poly approach, I just think circles are better suited for this.

    If you use the greedy approach, always adding the largest circle that covers most not-yet-covered area possible to cover the yard, you'll also get very efficient checking: most of the time, you only check one or two circles. If you use the same circle centerpoints to cover both the safe area and the warning area, using just different radiuses, each circle will still take only 8 bytes, and four multiplies and three additions/subtractions per test. (Just two multiplications if you store the radiuses squared.)

    The computing power in MSP430 should not be the issue anyway, as GPSs only provide a point per second or so. (Faster ones cost more.)

    I also suspect that when you map out your yard, it would be easier to handle the circles. You could connect the MPS430 to a laptop, and walk around the yard. You can write a trivial program (I like Python and PyQt4 or PyGTK for this) that lets you modify the yard model. With a polygon, local "weird zones" (radio wave reflecting surfaces etc) might need a few funky line segments to get right. (Have you checked your code for a concave polygon? I haven't, I'm just asking.) With circles, you can add tiny little circles at weird zones, and cover the rest with big ones. You can even use negative radius to mark exclusion zones, in case there is a plant you like that cannot handle dog wee (adding another test loop when inside the safe zone).

    That said, if you like the polygon approach, and it works for you, just go with it! Your project looks like a lot of fun.

    I started wondering if it would be possible to ditch the GPS, using inertial measurements and some form of external reference, maybe three or more very weak radio transmitters for distance measurement and trilateration (which gives you the 2D Cartesian coordinates of the point, when the coordinates of the three transmitters, and the distances from the point to each transmitter, is known). (Signal strength behaves approximately 1/distance2 with omnidirectional antennas and fixed height.)

  8. #38
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    Question: Since I would have to only shrink or expand my polygon once during set-up and not use in normal operation ..... would not matrix scaling do this for me?

    If so, then code looping drops from 9 to 2!

    But.... how do you do matrix scaling? .....any examples? : )

  9. #39
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @Nominal Animal:Thanks for your great input on this app! .... so many questions I have about your way. I am having a tuff time trying to see it.

    Your methods sounds like it requires a lot of user set-up intervention. Can you give me an example?

    My way, you walk the GSP collar to each corner of your yard and "click" .... grabbing that XY ..... no PC needed! DONE!
    Last edited by Rick19468; 10-12-2012 at 12:10 AM.

  10. #40
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,344
    Quote Originally Posted by Rick19468
    Is there a better way to create this "circle of points"?
    Quote Originally Posted by Rick19468
    My way, you walk the GSP collar to each corner of your yard and "click" grabbing that XY ..... no PC needed! DONE!
    It looks like you've answered your question.
    Fact - Beethoven wrote his first symphony in C

  11. #41
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @Nominal Animal: Have you checked your code for a concave polygon? YES! .... works well with concave and/or convex polys.

    ..... also works with "holes" in the middle (inside yard protected zones)
    Last edited by Rick19468; 10-12-2012 at 12:04 AM. Reason: more info

  12. #42
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @Click_here: The "circle of points" (original post) question was a minor detail in providing a warning buffer zone (aprox. 3ft) around the dog and follows the dog where ever he is ..... the prevailing discussion has been "Point-in Polygon" v. "boundary circles" that definds the entire yard area ..... two separate issues!
    Last edited by Rick19468; 10-12-2012 at 12:08 AM.

  13. #43
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    Nominal Animal:I started wondering if it would be possible to ditch the GPS, using inertial measurements and some form of external reference, maybe three or more very weak radio transmitters for distance measurement and trilateration (which gives you the 2D Cartesian coordinates of the point, when the coordinates of the three transmitters, and the distances from the point to each transmitter, is known). (Signal strength behaves approximately 1/distance2 with omnidirectional antennas and fixed height.

    I am currently working on an RFID UHF version where the reader is mounted on the collar. You place passive tags in the ground at grass root level spaced 2ft apart to defined the yard boundary ..... works great!!

    I always felt it wrong to have the ZAP contacts strapped onto the sensitive throat area. I was able to wirelessly remote the ZAP modual to the mass side of the neck muscle
    .

  14. #44
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @Nominal Animal: " .......very weak radio transmitters for distance measurement and trilateration"

    Well with the cost of atomic clocks these days .... I'd stay with the GPS system! : )


    .... other RSSI (signal strength) location systems are really ify at best for this app.

  15. #45
    Registered User
    Join Date
    Oct 2011
    Posts
    838
    Quote Originally Posted by Rick19468 View Post
    My way, you walk the GPS collar to each corner of your yard and "click"
    You know, that does sound easier. I'm starting to think your approach is better, after all.

    Why not do a separate polygon for the warning area? Have your code check the safe area first. If the dog is within the safe area, then GOOD DOG. Otherwise, if the dog is inside the warning area, BEEP. Otherwise, ZAP!.

    It would be trivial to write a suitable polygon editor in say Python, though. You could walk the perimeter to get the safe area polygon first, then visually edit it to add the warning area.

    Edited to add: If you want it all built-in to the MSP430, then you could calculate the distance to the nearest edge or vertex, when outside the safe polygon. Vertices (corner points) are simple, just the sum of the squared differences in coordinates (Pythagoras again). Point-line distance tells you the distance to each edge, if the edge was extended to infinity; you must limit it to the edge span. Wolfram Mathworld has the math.

    Let me see...
    Last edited by Nominal Animal; 10-12-2012 at 05:36 AM.

Page 3 of 5 FirstFirst 12345 LastLast
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