Self-Intersecting spiral moves - Algorithms and Problem SolvingAlgorithms and Problem Solving

Self-Intersecting spiral moves - Algorithms and Problem SolvingAlgorithms and Problem Solving

You are given a list of n float numbers x_1, x_2, x_3, … x_n, where x_i > 0. A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counter-clockwise).
Write an single-pass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it's self-intersecting)
e.g.
2 1 1 2 -> crosses
1 2 3 4 -> doesn't cross

Note that, the traveller is actually moving in spiral (either decreasing or increasing) with only exception that while moving in a outward (or increasing) spiral the traveller can change its direction to a inward (or decreasing) spiral.
So, it is clear that the travelers path doesn't cross as long as the spiral in increasing or decreasing. But if the traveler starts with a increasing spiral and then at some point it moves into an decreasing spiral, we need to check whether the changing move itself crosses the increasing spiral the traveller was moving on just before the move.
For example, if the moves are s1=[2, 1, 4, 4, 3, 2, 2, 1, 1] the we can see that there is a increasing spiral and then it changes to a inward spiral with no self-intersection. In case of s2=[2, 1, 4, 4, 3, 3, 2, 1, 1] we can see that 6th move intersect with first move. (s= start, e=end)

 __                                                       __                                  
|  |   ____        |  |_______ 
|  |s |    |       |  |s |    |
|     |__e |        |     |__e |
| ________ |       | ________ |

    (s1)          (s2)

public static boolean isCrossed(double[]  s){
 //base case 
 if(s.length < 4){
  return false;
 }
 if(s[0] >= s[2] && s[3] >= s[1]){
  return true;
 }
 
 //test if the moves are on outward increasing spiral
 int i = 3;
 while(i < s.length){
  if(s[i] > s[i-2] && s[i-1] > s[i-3])
   i++;
  else break;
 }
 
 //if we visited all the moves then there is no intersection
 if(i == s.length){
  return false;
 }
 
 //otherwise moves are on a decreasing inward spiral starting from i
 //we first need check if the two spirals are crossing each other which can only possible
 //when edge i+1 crosses edge (i-4)  or edge i+1 crosses edge i-2 (if exists)
 
 if(i < s.length && i > 3 && s[i + 1] >= (s[i - 1] - s[i - 3])){
  if (s[i] >= (s[i - 2] - s[i - 4]) || s[i + 1] >= s[i - 1])
      return true;
 }
 
 //if two spiral didn't intersect then check for decreasing s
 while(i+3 < s.length){
  if(s[i] > s[i+2] && s[i+1] > s[i+3]){
   i++;
  }
  else break;
 }
 
 //if we visited all the moves then there is no intersection
 if(i+3 == s.length){
  return false;
 }
 
 return false;
}

Read full article from Self-Intersecting spiral moves - Algorithms and Problem SolvingAlgorithms and Problem Solving