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; Hi! (beginner) In my code below, the pxx and the pyy arrays provide circular reference points around my test XY ...

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    62

    8 points in a circle around target point

    Hi! (beginner)

    In my code below, the pxx and the pyy arrays provide circular reference points around my test XY point for an early "warning zone" .... sounding off a beeper.

    This code works, but being hard coded ..... makes it hard to change. Is there a better way to create this "circle of points"?

    ie: lets say I want a 3ft circle of points around my test point, I just enter a "3" and the code calculates the 8 circle point coordinates into the array for me.

    Thanks!




    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    
    
    
    int main(int argc, char** argv) {
       
    
    
    int bi = 8; //Set Boundry loop indexing variable (Number of Points in polygon)
    int ci = 9; // Set loop indexing for 8 circle points plus the test point
    
    
    float x[bi];
    float y[bi];
    float pxx[ci];
    float pyy[ci];
    
    
    float px=16;// Real Test X location point
    float py=13.77; // Real Test Y location point
     
    /* The coordinates of the test point */
    pxx[0]=px;// Real Test X location point
    pyy[0]=py; //Real Test Y location point
    
    
    /*8 X,Y points circled around the real XY location for a circular WARNING ZONE)*/
    pxx[1] = px;        
    pyy[1] =(py+1);
    
    
    pxx[2] = px;
    pyy[2] =(py-1);
    
    
    pxx[3] =(px+1);
    pyy[3] = py;
    
    
    pxx[4] =(px-1);
    pyy[4] = py;
    
    
    pxx[5] =(px+.75);
    pyy[5] =(py+.75);
    
    
    pxx[6] =(px+.75);
    pyy[6] =(py-.75);
    
    
    pxx[7] =(px-.75);
    pyy[7] =(py+.75);
    
    
    pxx[8] =(px-.75);
    pyy[8] =(py-.75);
    
    
    
    
    float x1;
    float x2;
    float k;
    
    
    /* The points creating the polygon (INVISIBLE FENCE YARD BOUNDRY) */      
    x[0] = 7;      y[0] = 22;      
    x[1] = 10;     y[1] = 10;      
    x[2] = 7;      y[2] = 2;       
    x[3] = 15;     y[3] = 7;       
    x[4] = 21;     y[4] = 6;       
    x[5] = 30;     y[5] = 14;      
    x[6] = 22;     y[6] = 18;      
    x[7] = 20;     y[7] = 26;  
    
    
    int armedflag = 0; 
    int cnt = 0;
    
    
    int status_a = 0;
    int status_b = 0; 
    int status_c = 0;  
    
    
    
    
    
    
    for ( int v = 0; v < 30; v++ ){ // Simulated interrupt from GPS (once every second)
    
    
    
    
    for ( int c = 0; c < ci; c++ ){
    
    
        
    int crossings = 0;            
    /* Iterate through each line */
    for ( int i = 0; i < bi; i++ ){
       
      
        /* This is done to ensure that we get the same result when
               the line goes from left to right and right to left */
            if ( x[i] < x[ (i+1)%bi ] ){
                    x1 = x[i];
                    x2 = x[(i+1)%bi];
            } else {
                    x1 = x[(i+1)%bi];
                    x2 = x[i];
                              
            }
           
            /* First check if the ray is possible to cross the line */
            if ( pxx[c] > x1 && pxx[c] <= x2 && ( pyy[c] < y[i] || pyy[c] <= y[(i+1)%bi] ) ) {
                    static const float eps = 0.000001;
     
                    /* Calculate the equation of the line */
                    float dx = x[(i+1)%bi] - x[i];
                    float dy = y[(i+1)%bi] - y[i];
                    float k;
     
                    if ( fabs (dx) < eps ){
                        k =  INFINITY; //REM: <include math.h> !!!!
                    } else {
                            k = dy/dx;
                    }
     
                    float m = y[i] - k * x[i];
                   
                    /* Find if the ray crosses the line */
                    float y2 = k * pxx[c] + m;
                    if ( pyy[c] <= y2 ){
                            crossings++;
                            
           }
        }
    }
    
    
               
    if (( crossings % 2 == 1)&& (c == 0)) 
                   {
        
                   printf("The dog is OK INSIDE the yard\n");
                   status_a = 1;
                   armedflag = 1;               
                   
                   }
        
    if (( crossings % 2 != 1)&& (c > 0)&& (armedflag == 1))      
                   {
                   printf("BEEP!! BEEP!! BEEP!! The dog is IN THE WARNING ZONE\n");
                   status_b = 1;
                                  
                   } 
    if (( crossings % 2 == 1)&& (c > 0) && (status_a == 0)) 
                   {
                   armedflag = 0;
                   }
               
                   
    if (( crossings % 2 != 1)&& (c == 0 )&& (armedflag == 1))     
                   {
                   printf("ZAP!! ZAP!! ZAP!! The dog is OUTSIDE the yard\n");
                   status_c = 1;
                   armedflag = 0;
                      
        } 
       
      }
        
        printf("Armed Flag: %d\n",armedflag);
        printf("Status_a: %d\n",status_a);
        printf("Status_b: %d\n",status_b);           
        printf("Status_c: %d\n",status_c);  
        
     }
     
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,854
    Polar coordinate system - Wikipedia, the free encyclopedia

    Just work out r*cos(theta) and r*sin(theta) for 8 points.

    Since 4 points are cardinal points, these are either 0 or 1

    The rest are multiples of 45', so you only really need one pair of constants, and then use symmetry to calculate the other 3.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    Thanks Salem! .... I'll have to read up on what your saying. Not sure how to put all that together. : )

  4. #4
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    I see what to do now! .... but this may be too costly in MCU computational time to be calling function sin() and cos() constantly for this real time program code.

  5. #5
    Registered User
    Join Date
    Jun 2011
    Posts
    2,706
    Have you performed a timing analysis of calling those functions?
    Is the MCU going to be performing any other functions, or will it be exclusively adjusting coordinates and monitoring for out-of-bounds?
    You can also implement a timer so that the calculations are only performed in certain time increments (once every 500ms, 1s, etc), depending on how long it takes for the calculations to be performed.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    If it's too costly, but you know you are sticking to 8 points, evenly distributed around a center point, just hard-code the known sin/cos values for each point on a unit circle (radius 1). Then you just multiply it by the radius of the border you actually want. For pi/4 + N*(pi/2) angles (45 deg + N * 90 deg), both the x and y coordinates will be +/- sqrt(2), depending on what quadrant you're in.

    EDIT: Matticus is right, only worry about optimizing when you know for a fact that it is too slow, and that sin/cos is the biggest cause of this slowdown. What you are concerned with is a few clock cycles, whereas a speedup in your algorithm, say from O(n^2) to O(n log(n)), would be worth much, much more in performance.
    Last edited by anduril462; 10-11-2012 at 04:25 PM.

  7. #7
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @ Matticus: The MCU will be doing some other things as well, but aprox. 99.5% of the time, every 1/2 second, will be at resolving boundary and an 8 point warning zone violations of the dog's location in the yard. All my calculations must finish out before this time (Note: GPS module capable of 5*per. sec reads).

    @ Anduril462: I think the look up table is the best way to address this problem, since I am using only 8 known points. But is my hard coded way even faster than this?

    NOTE: The boundary and warning zones calculations are not of any needed high precision.

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I don't understand the "8 points" idea. Why not just calculate the distance from the center? That would give you an "infinte" number of points at a low cost. You don't even have to calculate the square root, just compare to the square of the radius. So if the dog is supposed to stay within a 5 meter circle with center (cx, cy) and the dog's current position is (x, y), you can tell if it's inside by:
    Code:
    if ((cx-x)*(cx-x) + (cy-y)*(cy-y) <= 25)
        // inside circle
    else
        // outside circle
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    [QUOTE=Rick19468;1127446]@ Anduril462: I think the look up table is the best way to address this problem, since I am using only 8 known points. But is my hard coded way even faster than this?[/code]
    Yes, the hard-coded way is quicker, but my way at least allows you to easily change the radius of the circle.

    oogabooga has the best advice if you simply want to check whether a point is within a circle. Your code, however, mentioned "rays", implying the dogs had a direction they were headed, and you had to account for that. If it's just a point (location at a given instant), use oogabooga's method. If you actually have directionality, then it's more complicated.

    Still, all of this boils down to: do you already know that sin/cos are not fast enough? If you can't prove that a sin and cos can't be executed in time, then this discussion is meaningless.

  10. #10
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @oogabooga: NO!! ... the dog is within the X,Y [8] polygon! (yard boundary) .... The "8 point circle" I generate around the dog is to violate the boundary early (giving the dog a warning "beep")

  11. #11
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    In my origional post, I just wanted a "single digit entry" to set all radius parms. This was all I needed to do:



    Code:
    rc = 3; // Single number assignment of "Boundry Radius" here
    rd = (rc -.75);
    
    
    /*8 X,Y points circled around the real XY location for a circular WARNING ZONE)*/
    pxx[1] = px;        
    pyy[1] =(py+rc);
    
    
    pxx[2] = px;
    pyy[2] =(py-rc);
    
    
    pxx[3] =(px+rc);
    pyy[3] = py;
    
    
    pxx[4] =(px-rc);
    pyy[4] = py;
    
    
    pxx[5] =(px+rd);
    pyy[5] =(py+rd);
    
    
    pxx[6] =(px+rd);
    pyy[6] =(py-rd);
    
    
    pxx[7] =(px-rd);
    pyy[7] =(py+rd);
    
    
    pxx[8] =(px-rd);
    pyy[8] =(py-rd);
    ...... silly me! : (

  12. #12
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    So the dog is confined to an octagon?
    And the warning zone is also an octagon (not a circle)?

    Exactly how is the dog moving?

    Another point:
    For the following variables, if only one at a time is ever supposed to be 1, then you can replace them by an enumeration:
    Code:
    int status_a = 0;
    int status_b = 0;
    int status_c = 0;
    
    // replace them with:
    enum {STATUS_INSIDE, STATUS_WARNING, STATUS_OUTSIDE} status = STATUS_INSIDE;
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  13. #13
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @oogabooga:....... then each of the eight circle points are separably tested to be ether "inside" or "outside" the polygon.

  14. #14
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,501
    Does it really matter if the beep goes off 30cm outside a 8m radius circle whilst the dog is running in that direction?

    Now, consider the accuracy of a GPS -> Can you get a reading that you can guarantee is within a 30cm radius?...

    If you can't use sin or cos -> stick to a static square boundary.
    Fact - Beethoven wrote his first symphony in C

  15. #15
    Registered User
    Join Date
    Oct 2012
    Posts
    62
    @oogabooga: NO!!.... Polygon! (see its shape by looking at the XY array coordinates) This polygon would be the shape of your needed fenced in area at your home. Could be of any shape! This boundary violation code is based on "point-in-polygon" algorithms.

Page 1 of 5 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, 03: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, 02:34 AM
  3. Points on circle
    By Suchy in forum C++ Programming
    Replies: 2
    Last Post: 11-16-2008, 03:08 PM
  4. point lies in circle?
    By cozman in forum Game Programming
    Replies: 3
    Last Post: 12-20-2001, 04:39 PM
  5. Finding a point within a circle
    By Unregistered in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2001, 09:34 PM

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