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);  
    
 }
 
}

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.

Thanks Salem! .... I'll have to read up on what your saying. Not sure how to put all that together. : )

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.

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.

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.

@ 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.

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

[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.

@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")

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! : (

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;

@oogabooga:....... then each of the eight circle points are separably tested to be ether "inside" or "outside" the polygon.

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.

@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.