странное поведение сравнения двух знаковых целых чисел в цикле for

Question

Я пытаюсь решить проблему, сформулированную следующим образом: заданные сегменты набора и набор точек вычисляют, сколько сегментов содержит каждую точку.

Проблема, с которой я столкнулся, - это когда мне приходится подсчитывать, сколько раз точка содержит сегмент. Когда у меня есть определенный вход, внутренний цикл, правильно увеличивает счетчик каждой точки, погоду, когда у меня есть другой набор данных, где происходит сравнение нуля с отрицательным числом и неотрицательным числом, оно ведет себя странно.

Ниже приведен просто сценарий, созданный для поиска проблемы, с которой я столкнулся, и не представляет фактической реализации.

Тестовые дают выходы следующим образом:

Случай 1:

String debug = "Test case 1: \n "; 
    debug += " \n - 2 Segments with coordinates [0, 5] and [7, 10]."; 
    debug += " \n - 3 points at the coordinates 1, 6, and 11."; 
    int [] starts = new int[]{0, 7}; 
    int [] ends = new int[]{5, 10}; 
    int [] points = new int[]{1, 6, 11}; 

    debug += "\n \n Calculating the coverage of the points: "; 
    for (int i=0; i<starts.length; i++) { 
     for (int j=0; j<points.length && (starts[i] <= points[j] && points[j] <= ends[i]); j++) { 
      debug += " \n * Point with coordinate " + points[j] + ", is between " + starts[i] + " and " + ends[i]; 
     } 
    } 
    debug += "\n \n FINISHED the calculation!"; 

    int start = 0, point = 1, end = 5; 
    debug += "\n \n Custom check for the 1st point: "; 
    debug += "\n - Is (" + start + " <= " + point + " and " + point + " <= " + end + ")? " + (start <= point && point <= end); 
    System.out.println(debug); 

Выход:

Тестовый пример 1:

• 2 Сегменты с координатами [0, 5] и [7, 10].

• 3 точки с координатами 1, 6 и 11.

  Расчет охвата точек:

• точка с координатами 1, находится в пределах от 0 и 5

  ЗАВЕРШЕНА расчет!

  Пользовательские проверки на 1-й точки:

• Is (0 < = 1 и 1 < = 5)? истинная

Случай 2:

String debug = "Test case 2: \n "; 
    debug += " \n - 1 Segment with coordinates [-10, 10]."; 
    debug += " \n - 3 points at the coordinates -100, 100, and 10."; 
    int [] starts = new int[]{-10}; 
    int [] ends = new int[]{10}; 
    int [] points = new int[]{-100, 100, 0}; 

    debug += "\n \n Calculating the coverage of the points: "; 
    for (int i=0; i<starts.length; i++) { 
     for (int j=0; j<points.length && (starts[i] <= points[j] && points[j] <= ends[i]); j++) { 
      debug += " \n * Point with coordinate " + points[j] + ", is between " + starts[i] + " and " + ends[i]; 
     } 
    } 
    debug += "\n \n FINISHED the calculation!"; 

    int start = -10, point = 0, end = 10; 
    debug += "\n \n Custom check: "; 
    debug += "\n - Is (" + start + " <= " + point + " and " + point + " <= " + end + ")? " + (start <= point && point <= end); 
    System.out.println(debug); 

Выход:

Тестовый пример 2:

• 1 Сегмент с координатами [-10, 10].

• 3 точки с координатами -100, 100 и 10.

  Расчет охвата точек:

  ЗАВЕРШЕНА расчет!

  Пользовательские проверки:

• Is (-10 < = 0 и 0 < = 10)? true

Как вы можете видеть, условие во внутреннем цикле каким-то образом не правильно вычисляет случай с координатой 0 относительно сегмента [-10, 10].

Заранее благодарен, Endrit.

Answer 1

Ваша проблема с условием for петли:

for (int j=0; j<points.length && (starts[i] <= points[j] && points[j] <= ends[i]); j++) { 

Как только вы столкнулись с какой-либо point[j], не лежащее между starts[i] и ends[i] то цикл завершится, и вы не будете проверять все последующие пункты.

Вместо этого вы должны отделить условие цикла от условия пересечения. В псевдокоде:

for every (start, end) pair: 
    for every point: 
     if point intersects (start, end): 
       increment counter 
     otherwise continue to next point 

Это имеет смысл?

Answer 2

Чтобы уменьшить порядок больших-0 от points.Length * ends.Length, вы можете прокручивать оба в одно и то же время. Я предполагаю, что сегменты не могут пересекаться.

Array.sort(starts); 
Array.sort(ends); 
Array.sort(points); 
int pointIndex = 0; 
String debug = "" 
int numCollisions = 0; 
bool collides = False; 
for (int i=0; i < ends.length; i++) { 
    debug += "Points between " + starts[i] + " and " + ends[i] ":\n"; 
    while (pointIndex < points.Length && points[pointIndex] < starts[i]) { 
     pointIndex++; 
    } 
    while (pointIndex < points.Length && points[pointIndex] <= ends[i]) { 
     numCollisions++; 
     debug += " " + points[pointIndex] "\n"; 
     pointIndex++; 
    } 
} 
debug += "Total number of collisions: " + numCollisions; 
System.out.println(debug); 

// Оригинал Ответ:

В Test Case 2 выхода для цикла на 2-й итерации внутреннего цикла (i==0 и j==1), так как и ends[i] == 10. Поскольку вы вышли из цикла, 0 никогда не проверяется.

Попробуйте сортировать points перед тем, как ввести петлю цикла.