Thread: How to return the edge points positions-zero crossing points of array values?

  1. #1
    Registered User
    Join Date
    Nov 2020
    Posts
    34

    How to return the edge points positions-zero crossing points of array values?

    Hello !
    I'm trying to implement in c a function that returns the positions of the zero crossing points of its array values, this means to return all the positions where there's a transition between positive values nd negative values(or vice versa -transition between negative and positive values).
    Assumption that the value zero is considered as transition and there couldn't be more than one zero continuously- can't appear two zeros following each other (I will explain in progress by an example about this).
    In addition , the value of the array is considered as transition because there's nothing after the last value of the array so we assume that implicitly the last value and NULL (there's nothing after the last value of the array) is a transition.

    the array values are float values .

    @Note: first position of the array is considered index = 1 and not index = zero (this is assumption to my problem).

    Examples:
    #1
    Code:
    Array data= {-1,3}
    so the output is array of positions/indexes of the array where there's transition between positive and negative values:
    Code:
    {1 ,2};
    Explanation:
    the value of position 1 is (-1) so after it we see positive value 3 so the position 1 is considered as transition between negative or positive (vice versa also ok).
    the position 2 (last position at the array) is also added to the output positions because there's no values after position 2 (out of the array size) so it's as assumption considered transition, so we always in my case add the last position of the array to the output positions .


    #2
    Code:
    Array data= {-1,-1,1,-3,-1,3,3}
    so the output is array of positions where there's transition between positive and negative values:
    Code:
    {2,3,5,7};
    #3
    Code:
    Array data= {-1,-1,1,-3,-1,3,3,0}
    so the output is array of positions where there's transition between positive and negative values:
    Code:
    {2,3,5,7,8};
    (see here that position 8 is added because there's zero appeared in the last position of the array, and as I said value with zero is considered as transition so we need to write its position on the output)

    #4
    Code:
    Array data= {-1,-1,1,-3,-1}
    so the output is array of positions where there's transition between positive and negative values:
    Code:
    {2,3};
    (see what I marked in the array data in this example its corresponded to the output positions where there's a transition between positive values and negative values)

    #5
    Code:
    Array data= {-1,0,1}
    so the output is array of positions/indexes of the array where there's transition between positive and negative values:
    Code:
    {1 ,2 , 3};
    Explanation:
    the value of position 1 is (-1) so after it we see positive value 0 so the position 1 is considered as transition between negative or positive (vice versa also ok)- I already said above the when there's value 0 as it's considered as position because it's transition.

    the position 2 (second value 0 ) is also added to the output positions because as I said the value 0 is considered as transition (doesn't matter if we implicitly look at it from right to left or left to right).

    the position 3 (last position at the array) is also added to the output positions because there's no values after position 3 (out of the array size) so it's considered transition as assumption, so we always in my case add the last position of the array to the output positions .

    #5
    Code:
    Array data= {-1,0,1,0}
    so the output is array of positions/indexes of the array where there's transition between positive and negative values:
    Code:
    {1 ,2 , 3, 4};
    #6
    Code:
    Array data= {0,1}
    so the output is array of positions/indexes of the array where there's transition between positive and negative values:
    Code:
    {1 ,2 };
    (as I said the value zero is implicitly considered as transition, so the position 1 is added )

    #7
    there can't be case that more than one zero following each other this means
    Code:
    {1,0,0}
    isn't possible but it could be like this
    Code:
    {1,0,1,0}
    this is possible because there's no more than one zero following each other.


    Hope my problem is understandable!


    So what I've implemented in C and I'm to get correct outputs:
    Code:
    
    
    Code:
    #include<stdio.h>
    #include<stdbool.h>
    
    zeroCrossing(float *data, float *zerCross, int nx);
    /* zero crossing function */
    /* data = input array which it's the Array data*/
    /* zerCross = output zero crossing array- output positions */
    void zeroCrossing(float *data, float *zerCross, int nx)
    {
        int i;
        bool sign1, sign2;
    
    
        memset(zerCross, 0, nx*sizeof(float));
        for(i=0; i<nx-1; i++)     /* loop over data  */
        {
            sign1 = getSign(data[i]);
            sign2 = getSign(data[i+1]);
            if(sign1!=sign2)  /* set zero crossing location */
                zerCross[i+1] = 1;
        }
    }
    
    
    /* get sign of number */
    bool getSign(float data)
    {
        if(data>0)      /* positif data */
            return (1);
        else            /* negatif data */
            return (0);
    } 
    
    
    
    int main()
    {
       %we input manually the float of our array
        float array[9] = {1.0,2.0,3.0,0.0,-1.0,-2.0,-3.0,0.0,1.0}; 
    
        float *p = array;
        float f1[9];
        float *p2 = f1;
        int bx= 2 ;
        zeroCrossing(array, f1, bx); 
    }

    I get wrong outputs and a compilations error, any help please?
    maybe my algorithm isn't good so for my problem it would be appreciated for any suggestion/help.

    thanks alot!
    Last edited by JohnnyOmari; 12-22-2020 at 01:42 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,801
    > I get wrong outputs and a compilations error, any help please?
    You can't have output and compilation errors - it's one or the other.

    > %we input manually the float of our array
    % isn't a comment in C or C++

    > zeroCrossing(array, f1, bx);
    Your array is 9 elements, but bx is 2
    No wonder not much happens.
    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.

  3. #3
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    Code:
    #include<stdio.h>
    #include<stdbool.h>
    Code:
    zeroCrossing(float *data, float *zerCross, int nx);
    /* zero crossing function */
    /* data = input array which it's the Array data*/
    /* zerCross = output zero crossing array- output positions */
    void zeroCrossing(float *data, float *zerCross, int nx)
    {
        int i;
        bool sign1, sign2;
    
    
        memset(zerCross, 0, nx*sizeof(float));
        for(i=0; i<nx-1; i++)     /* loop over data  */
        {
            sign1 = getSign(data[i]);
            sign2 = getSign(data[i+1]);
            if(sign1!=sign2)  /* set zero crossing location */
                zerCross[i+1] = 1;
        }
    }
    
    
    /* get sign of number */
    bool getSign(float data)
    {
        if(data>0)      /* positif data */
            return (1);
        else            /* negatif data */
            return (0);
    } 
    
    
    
    int main()
    {
       //we input manually the float of our array
        float array[9] = {1.0,2.0,3.0,0.0,-1.0,-2.0,-3.0,0.0,1.0}; 
    
        float *p = array;
        float f1[9];
        float *p2 = f1;
        int bx= 9 ;
        zeroCrossing(array, f1, bx); 
    }
    I edited my code, @salem sorry I mean by wrong output ..the compilation error! sorry for the missunderstanding.

  4. #4
    Registered User
    Join Date
    May 2012
    Posts
    505
    Quote Originally Posted by JohnnyOmari View Post
    this is the compilation errors I get:

    In function 'void zeroCrossing(float*, float*, int)':11:38: error: 'memset' was not declared in this scope In function 'int main()':38:27: error: cannot convert 'float' to 'float*' for argument '1' to 'void zeroCrossing(float*, float*, int)'
    Use this interface

    void zeroCrossings(const float *x, bool *crossings, int N);

    The array crossings is the same length as the input array x, but each position represents the line between adjacent positions in x (so it would be one less were it not for the special rule about array end).

    Now you iterate through it. Basically you just set the flag every time you get a sign change, but you need to handle zeros specially, and you need a special case for the last value.

    If you need output as a list of integers rather than flags, wrap this function with a simple data reformatting function - that makes it easier for you.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  5. #5
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    Hi, I edited my code again, and I fixed all the compilation error , but I get wrong output ..wrong output of the array positions:
    (Yes I used some library from C++ but it's ok .. I can use c/c++ in my case)
    Code:
    void zeroCrossing(float *data, float *zerCross, int nx);
    #include <iostream>
    #include <cstring>
    bool getSign(float data);
    /* zero crossing function */
    /* data = input array */
    /* zerCross = output zero crossing array */
    void zeroCrossing(float *data, float *zerCross, int nx)
    {
        int i;
        bool sign1, sign2;
        std:: memset(zerCross, 0, nx*sizeof(float));
        for(i=0; i<nx-1; i++)     /* loop over data  */
        {
            sign1 = getSign(data[i]);
            sign2 = getSign(data[i+1]);
            if(sign1!=sign2)  /* set zero crossing location */
                zerCross[i+1] = 1;
        }
    }
    
    
    /* get sign of number */
    bool getSign(float data)
    {
        if(data>0)      /* positif data */
            return (1);
        else            /* negatif data */
            return (0);
    }
    int main()
    {
        float array[9] = {1,2,3,0,-1,-2,-3,0,1};
        float *p = array;
    
    
        float f1[9];
        float *p2 = f1;
        int bx= 9 ;
        zeroCrossing(array, f1, bx); 
        for(int i=0;i<9;i++)
        {
            printf("%d",f1[i]);
        }
        
    }
    output is: 0.0000000.0000000.0000001.0000000.0000000.0000000. 0000000.0000001.000000

    Any help please?!
    Last edited by JohnnyOmari; 12-22-2020 at 03:08 PM.

  6. #6
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    Quote Originally Posted by Malcolm McLean View Post
    Use this interface

    void zeroCrossings(const float *x, bool *crossings, int N);

    The array crossings is the same length as the input array x, but each position represents the line between adjacent positions in x (so it would be one less were it not for the special rule about array end).

    Now you iterate through it. Basically you just set the flag every time you get a sign change, but you need to handle zeros specially, and you need a special case for the last value.

    If you need output as a list of integers rather than flags, wrap this function with a simple data reformatting function - that makes it easier for you.
    Thanks for your reply, I already solved the compilation error, and now I have wrong output.
    Appreciated for any help/suggestion.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,361
    Quote Originally Posted by JohnnyOmari
    first position of the array is considered index = 1 and not index = zero (this is assumption to my problem).
    One-based indexing is a perfectly legitimate approach, but arrays in C use zero-based indexing. Therefore, you should use zero-based indexing for your arrays in C, and treat this as a matter of output: when you finally have the array indices, you translate them for output into the one-based indexed positions by adding 1. This way, you avoid possible off-by-one errors when accessing the arrays by doing things as you normally would in C. (However, if you're only using the array of indices/positions purely as)

    Next, I understand that your input consists of data in float type. Great. But indices/positions are non-negative/positive integers, not floating point values, so your second array should be an array of unsigned integers, e.g., size_t.

    EDIT:
    Also, would it hurt to use some whitespace in your output to make it more readable? For example:
    Code:
    printf("%d ", f1[i]);
    but you should note that this printf is wrong because f1[i] is a float, not an int. If you make f1 an array of size_t, you could then write:
    Code:
    printf("%zu ", f1[i]);
    Speaking of which, f1 is a terrible name: does it have something to do with Formula One racing? If you want it to be an array of indices/positions, then name it "indices" or "positions".
    Last edited by laserlight; 12-22-2020 at 04:11 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,801
    The getSign function isn't really adding any value IMO, and doesn't capture the essence of the problem.
    Code:
    #include <stdio.h>
    #include <stdbool.h>
    
    bool isCrossing(float *pair) {
      return pair[0] < 0 && pair[1] >= 0 ||
             pair[0] > 0 && pair[1] <= 0;
    }
    
    void zeroCrossing(float *data, bool *zerCross, int datasize)
    {
      for ( int i = 0 ; i < datasize - 1 ; i++ ) {
        zerCross[i] = isCrossing(&data[i]);
      }
    }
    
    int main()
    {
      // we input manually the float of our array
      float array[9] = {1.0,2.0,3.0,0.0,-1.0,-2.0,-3.0,0.0,1.0};
      bool crossings[8] = { 0 };
      zeroCrossing(array, crossings, 9);
      for ( int i = 0 ; i < 8 ; i++ ) {
        printf("%3.0f to %3.0f is %d\n", array[i], array[i+1], crossings[i]);
      }
    }
    
    $ gcc foo.c
    $ ./a.out 
      1 to   2 is 0
      2 to   3 is 0
      3 to   0 is 1
      0 to  -1 is 0
     -1 to  -2 is 0
     -2 to  -3 is 0
     -3 to   0 is 1
      0 to   1 is 0
    All you need do is fiddle with the logic in isCrossing.
    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.

  9. #9
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    Alright, you're right, SOLVED It appreciated!

  10. #10
    Registered User
    Join Date
    Feb 2019
    Posts
    888
    NOT a correction, just a little bit of improvement. Instead of:
    Code:
    bool isCrossing(float *pair) {
    
      return pair[0] < 0 && pair[1] >= 0 ||
             pair[0] > 0 && pair[1] <= 0;
    }
    Well... just a little correction: the second criteria (after ||) should be:
    Code:
    pair[0] >= 0 && pair[1] < 0
    My little imprivement is this:
    Code:
    bool isCrossing(float *pair) 
    {
      return !!signbit(pair[0]) ^ !!signbit(pair[1]);
    }
    OBS: !! is there to make sure signbit returns a boolean value (0 or 1) and XOR makes sure the result is true only if both signs are different.
    Must link with libm.
    Last edited by flp1969; 12-23-2020 at 07:49 AM.

  11. #11
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    792
    Quote Originally Posted by flp1969 View Post
    My little imprivement is this:
    Code:
    bool isCrossing(float *pair) 
    {
      return !!signbit(pair[0]) ^ !!signbit(pair[1]);
    }
    OBS: !! is there to make sure signbit returns a boolean value (0 or 1) and XOR makes sure the result is true only if both signs are different.
    Must link with libm.
    Since you're doing XOR, you can drop one of the ! on each side:

    Code:
    bool isCrossing(float *pair) 
    {
      return !signbit(pair[0]) ^ !signbit(pair[1]);
    }
    Or it might be faster to just do it this way:

    Code:
    bool isCrossing(float *pair) 
    {
      return (pair[0] < 0) ^ (pair[1] < 0);
    }
    (I'd also add const to the parameter since the function does not modify it: const float *pair. But that's picking nits.)

  12. #12
    Registered User
    Join Date
    Feb 2019
    Posts
    888
    The second tip is ok (droping a !), but the third is a little bit different, since uses two floating point comparisons.
    Notice signbit simply isolates the sign bit without any comparison... The third tip has a tendency to be a little bit slower:

    Code:
    isCrossing:                     isCrossing:
      mov   eax, DWORD PTR [rdi]        pxor  xmm0, xmm0
      mov   edx, DWORD PTR [rdi+4]      comiss  xmm0, DWORD PTR [rdi]
      test  eax, eax                    seta  al
      sets  al                          comiss  xmm0, DWORD PTR [rdi+4]
      test  edx, edx                    seta  dl
      sets  dl                          xor eax, edx
      xor   eax, edx                    movzx eax, al
      movzx eax, al                     ret
      ret

  13. #13
    Registered User
    Join Date
    Feb 2019
    Posts
    888
    And, in other architetures besides Intel (like ARM) these functions are different. Here the 3 isCrossing() in ARM Cortex-A53 using vfp3-d16:

    Code:
    isCrossing:
      ldm r0, {r0, r3}
      lsr r3, r3, #31
      eor r0, r3, r0, lsr #31
      bx  lr
    Eliminating one !:

    Code:
    isCrossing:
      ldm r0, {r0, r3}
      mvn r3, r3
      lsr r3, r3, #31
      cmp r0, #0
      movlt r0, r3
      eorge r0, r3, #1
      bx  lr
    And using floating point comparisons:

    Code:
    isCrossing:
      vldr.32 s14, [r0]
      vldr.32 s15, [r0, #4]
      vcmpe.f32 s14, #0
      vmrs  APSR_nzcv, FPSCR
      vcmpe.f32 s15, #0
      movmi r0, #1
      movpl r0, #0
      vmrs  APSR_nzcv, FPSCR
      movmi r3, #1
      movpl r3, #0
      eor r0, r0, r3
      bx  lr

  14. #14
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,801
    Trading readability for IOCCC entries hardly seems like an improvement to me.

    The comparisons are obvious to pretty much anyone, whereas the bit magic requires quite a lot of detailed understanding of what's going on.

    > Well... just a little correction: the second criteria (after ||) should be:
    You mean 'correct' so that your cleverness will work.

    What if the condition really has to be > 0 when crossing from negative to positive?
    Hysteresis - Wikipedia

    It's zero crossing.
    Meaning bouncing off the floor (1 0 1) or ceiling (-1 0 -1) don't count as crossing zero.

    Not to mention this little pitfall.
    Floating-point arithmetic - Wikipedia
    Last edited by Salem; 12-24-2020 at 05:50 AM. Reason: Semantics, and signed zeros
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Trouble printing x and y values of struct points in an array?
    By arcadedragon in forum C Programming
    Replies: 6
    Last Post: 10-03-2012, 10:15 AM
  2. 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
  3. Decimal Points and Binary Points
    By Shadow12345 in forum A Brief History of Cprogramming.com
    Replies: 9
    Last Post: 11-07-2002, 01:06 AM
  4. multiple return points
    By Unregistered in forum C Programming
    Replies: 10
    Last Post: 05-09-2002, 03:01 AM

Tags for this Thread