title: Count the number of intersections of line segments whose endpoints are located on a circle?
body: <hr>
  
  <blockquote>
    <p>The input is an array of 2n integers which defines line segments by saying how the points located on a circle are paired
    and connected. (Each point has its own pair that's connected to it.)</p>
    
    <p>Array <code>[2,3,0,1]</code> reads: </p>
    
    <p>Point 0 is connected to point 2<br> Point 1 is connected to point 3
    <br> Point 2 is connected to point 0<br> Point 3 is connected to
    point 1</p>
    
    <p>Meaning we have line segments (0,2) and (1,3).</p>
    
    <p>The points are located on a circle, in the same order that they are
    located in the array. (Their exact coordinates are irrelevant.)</p>
    
    <p>Here is the picture of my array example. (1 intersection occured.)</p>
    
    <p><a href="https://i.stack.imgur.com/6kkFZ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/6kkFZ.png" alt="enter image description here"></a></p>
    
    <p>The output is the number of intersections. (Number of points where 2 line segments touch.)</p>
    
    <p>What would be the best (fastest) way to calculate this?</p>
  </blockquote>
  
  <p>What I've tried:</p>
  
  <pre><code>public static int count(int[] world) {
      int i = 0;
      int intersections = 0;
      int endpoint = 0;
  
      // run trought all points in order, find their pairs and check if the line they make is intersected
      while (i &lt; world.length - 1) {
  
          if (world[i] == i+1) { // if 2 neighbouring points are connected, there are no intersections with the line they make
              i++;
          } else if (world[i] &gt; i) { // don't need to check previously checked pairs
              endpoint = world[i];
  
                  // check if any intersections with the line L(i,world[i]):
                  // This goes through all points that are located before the endpoint of the line defined by point i and its pair world[i]
                  // And checks if their pair is located after the endpoint, which means that the line they make intersects the line L(i,world[i])
                  for (int j = i+1; j &lt; endpoint; j++) {
                      if (world[j] &gt; endpoint) {
                          intersections++;
                      }
              }
          } 
          i++;
      }
  
      return intersections;
  }
  </code></pre>
  
  <p>Thanks to <a href="https://stackoverflow.com/questions/43017527/count-the-number-of-intersections-of-line-segments-whose-endpoints-are-located-o/43017875#43017875">saby</a>s answer, I also coded this:</p>
  
  <pre><code>    public static int countIntersections(int[] world) {
      int intersections = 0;
  
      for (int i = 1; i &lt; world.length; i++) {
          for (int j = 0; j &lt; i; j++) {
              if (!C(i,world[i],i-j,world[i-j])) {
                  intersections++;
              }
          }
      }
  
      return intersections;
  }
  
  public static boolean C(int a, int b, int x, int y) {
      return ((a &lt;= x &amp;&amp; b &lt;= x) || (a &gt;= x &amp;&amp; b &lt;= y) || (a &gt;= x &amp;&amp; b &gt;= x));
  }
  </code></pre>
  
  <p>Which gives the same results as my initial code meaning they both work! But my initial code is faster than this one.</p>
  
  <p>I'll be accepting his answer since both codes work and optimization questions are better suited for <a href="https://codereview.stackexchange.com/">Codereview</a>.</p>
  
  <hr>