Come utilizzare il teorema di Pick su qualsiasi triangolo dato

Question

Quindi voglio calcolare il numero di punti all'interno di un dato triangolo. So che devo usare il Teorema di Pick, ma il mio codice finisce per essere ridicolmente lungo con la quantità di if-else se le dichiarazioni da testare per ogni caso. Sto usando questo come una guida How many integer points within the three points forming a triangle?, ma poi alla fine con questa (. Vertici è un array di array 3 Ogni array è (x, y) coordinate di un vertice del triangolo):

int maxX = Math.max(Math.max(vertices[0][0], vertices[1][0]), vertices[2][0]), 
     minX = Math.min(Math.min(vertices[0][0], vertices[1][0]), vertices[2][0]), 
     maxY = Math.max(Math.max(vertices[0][1], vertices[1][1]), vertices[2][1]), 
     minY = Math.min(Math.min(vertices[0][1], vertices[1][1]), vertices[2][1]); 

    int height = Math.abs(maxY - minY), 
     width = Math.abs(maxX - minX); 

    double area = Math.abs(((vertices[0][0] * (vertices[1][1] - vertices[2][1] 
        )) + (vertices[1][0] * (vertices[2][1] - vertices[0][1])) 
        + vertices[2][0] * (vertices[0][1] - vertices[1][1]))/2); 


    if ((vertices[0][0] == vertices[1][0]) && (vertices[0][1] == vertices[2][1])) 
    { 
     area = ((Math.abs(vertices[0][1] - vertices[1][1]) - 1) * 
        (Math.abs(vertices[0][0] - vertices[2][0]) - 1))/2; 
    } 
    else if ((vertices[0][0] == vertices[2][0]) && (vertices[0][1] == vertices[1][1])) 
    { 
     area = ((Math.abs(vertices[0][1] - vertices[2][1]) - 1) * 
        (Math.abs(vertices[0][0] - vertices[1][0]) - 1))/2; 
    } 
    else if ((vertices[1][0] == vertices[2][0]) && (vertices[1][1] == vertices[0][1])) 
    { 
     area = ((Math.abs(vertices[1][1] - vertices[2][1]) - 1) * 
        (Math.abs(vertices[1][0] - vertices[0][0]) - 1))/2; 
    } 
    else if ((vertices[1][0] == vertices[2][0]) && (vertices[1][1] == vertices[0][1])) 
    { 
     area = ((Math.abs(vertices[1][1] - vertices[2][1]) - 1) * 
        (Math.abs(vertices[1][0] - vertices[0][0]) - 1))/2; 
    } 
    else if(vertices[0][0] == vertices[1][0]) 
    { 
     int b = Math.abs(vertices[0][1] - vertices[1][1]); 

     /*double dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + 
        Math.pow(vertices[0][1] - vertices[2][1], 2)), 
       dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + 
        Math.pow(vertices[1][1] - vertices[2][1], 2));*/ 
     if (vertices[0][1] > vertices[1][1]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist1*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist2*/)/2); 
     } 
     else if (vertices[0][1] < vertices[1][1]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist2*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist1*/)/2); 
     } 
    } 
    else if(vertices[0][0] == vertices[2][0]) 
    { 
     int b = Math.abs(vertices[0][1] - vertices[2][1]); 

     /*double dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) + 
        Math.pow(vertices[0][1] - vertices[1][1], 2)), 
       dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) + 
        Math.pow(vertices[2][1] - vertices[1][1], 2));*/ 
     if (vertices[0][1] > vertices[2][1]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist1*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist2*/)/2); 
     } 
     else if (vertices[0][1] < vertices[2][1]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist2*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist1*/)/2); 
     } 
    } 
    else if(vertices[1][0] == vertices[2][0]) 
    { 
     int b = Math.abs(vertices[1][1] - vertices[2][1]); 

     /*double dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[0][0], 2) + 
        Math.pow(vertices[1][1] - vertices[0][1], 2)), 
       dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) + 
        Math.pow(vertices[2][1] - vertices[0][1], 2));*/ 
     if (vertices[1][1] > vertices[2][1]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist1*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist2*/)/2); 
     } 
     else if (vertices[1][1] < vertices[2][1]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist2*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist1*/)/2); 
     } 
    } 
    else if(vertices[0][1] == vertices[1][1]) 
    { 
     int b = Math.abs(vertices[0][0] - vertices[1][0]); 

     /*double dist1 = Math.sqrt(Math.pow(vertices[0][1] - vertices[2][0], 2) + 
        Math.pow(vertices[0][1] - vertices[2][1], 2)), 
       dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + 
        Math.pow(vertices[1][1] - vertices[2][1], 2));*/ 
     if (vertices[0][0] > vertices[1][0]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist1*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist2*/)/2); 
     } 
     else if (vertices[0][0] < vertices[1][0]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist2*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist1*/)/2); 
     } 
    } 
    else if(vertices[0][1] == vertices[2][1]) 
    { 
     int b = Math.abs(vertices[0][0] - vertices[2][0]); 

     /*double dist1 = Math.sqrt(Math.pow(vertices[0][1] - vertices[1][0], 2) + 
        Math.pow(vertices[0][1] - vertices[1][1], 2)), 
       dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) + 
        Math.pow(vertices[2][1] - vertices[1][1], 2));*/ 
     if (vertices[0][0] > vertices[2][0]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist1*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist2*/)/2); 
     } 
     else if (vertices[0][0] < vertices[2][0]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist2*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist1*/)/2); 
     } 
    } 
    else if(vertices[1][1] == vertices[2][1]) 
    { 
     int b = Math.abs(vertices[1][0] - vertices[2][0]); 

     /*double dist1 = Math.sqrt(Math.pow(vertices[1][1] - vertices[0][0], 2) + 
        Math.pow(vertices[1][1] - vertices[0][1], 2)), 
       dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) + 
        Math.pow(vertices[2][1] - vertices[0][1], 2));*/ 
     if (vertices[1][0] > vertices[2][0]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist1*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist2*/)/2); 
     } 
     else if (vertices[1][0] < vertices[2][0]) 
     { 
      area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * 
        (height - 1) /*- dist2*/)/2) - (((width - 1) * (height - b - 1) 
        /*- dist1*/)/2); 
     } 
    } 
    else if (minX == vertices[0][0]) 
    { 
     int a = 0, 
      b = 0; 

     /*double dist1 = 0, 
       dist2 = 0, 
       dist3 = 0;*/ 

     if(Math.min(vertices[1][0], vertices[2][0]) == vertices[1][0]) 
     { 
      a = width - (vertices[1][0] - vertices[0][0]); 
      b = height - (vertices [1][1] - vertices[0][1]); 

      /*dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) + 
        Math.pow(vertices[0][1] - vertices[1][1], 2)); 
      dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + 
        Math.pow(vertices[1][1] - vertices[2][1], 2)); 
      dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + 
        Math.pow(vertices[0][1] - vertices[2][1], 2));*/ 
     } 
     else if(Math.min(vertices[1][0], vertices[2][0]) == vertices[2][0]) 
     { 
      a = width - (vertices[2][0] - vertices[0][0]); 
      b = height - (vertices [2][1] - vertices[0][1]); 

      /*dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + 
        Math.pow(vertices[0][1] - vertices[2][1], 2)); 
      dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + 
        Math.pow(vertices[1][1] - vertices[2][1], 2)); 
      dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) + 
        Math.pow(vertices[0][1] - vertices[1][1], 2));*/ 
     } 

     area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1) 
        * (b - 1) /*- dist1*/)/2) - (((width - a - 1) * (height - 1) 
        /*- dist2*/)/2) - (((width - 1) * (height - b - 1) /*- dist3*/)/2); 
    } 
    else if (minX == vertices[1][0]) 
    { 
     int a = 0, 
      b = 0; 

     /*double dist1 = 0, 
       dist2 = 0, 
       dist3 = 0;*/ 

     if(Math.min(vertices[0][0], vertices[2][0]) == vertices[0][0]) 
     { 
      a = width - (vertices[0][0] - vertices[1][0]); 
      b = height - (vertices [0][1] - vertices[1][1]); 

      /*dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[0][0], 2) + 
        Math.pow(vertices[1][1] - vertices[0][1], 2)); 
      dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + 
        Math.pow(vertices[0][1] - vertices[2][1], 2)); 
      dist3 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + 
        Math.pow(vertices[1][1] - vertices[2][1], 2));*/ 
     } 
     else if(Math.min(vertices[0][0], vertices[2][0]) == vertices[2][0]) 
     { 
      a = width - (vertices[2][0] - vertices[1][0]); 
      b = height - (vertices [2][1] - vertices[1][1]); 

      /*dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + 
        Math.pow(vertices[1][1] - vertices[2][1], 2)); 
      dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + 
        Math.pow(vertices[0][1] - vertices[2][1], 2)); 
      dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) + 
        Math.pow(vertices[0][1] - vertices[1][1], 2));*/ 
     } 

     area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1) 
        * (b - 1) /*- dist1*/)/2) - (((width - a - 1) * (height - 1) 
        /*- dist2*/)/2) - (((width - 1) * (height - b - 1) /*- dist3*/)/2); 
    } 
    else if (minX == vertices[2][0]) 
    { 
     int a = 0, 
      b = 0; 

     /*double dist1 = 0, 
       dist2 = 0, 
       dist3 = 0;*/ 

     if(Math.min(vertices[0][0], vertices[1][0]) == vertices[0][0]) 
     { 
      a = width - (vertices[0][0] - vertices[2][0]); 
      b = height - (vertices [0][1] - vertices[2][1]); 

      /*dist1 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) + 
        Math.pow(vertices[2][1] - vertices[0][1], 2)); 
      dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) + 
        Math.pow(vertices[0][1] - vertices[1][1], 2)); 
      dist3 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + 
        Math.pow(vertices[1][1] - vertices[2][1], 2));*/ 
     } 
     else if(Math.min(vertices[0][0], vertices[1][0]) == vertices[1][0]) 
     { 
      a = width - (vertices[1][0] - vertices[2][0]); 
      b = height - (vertices [1][1] - vertices[2][1]); 

      /*dist1 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) + 
        Math.pow(vertices[2][1] - vertices[1][1], 2)); 
      dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + 
        Math.pow(vertices[0][1] - vertices[2][1], 2)); 
      dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + 
        Math.pow(vertices[0][1] - vertices[2][1], 2));*/ 
     } 

     area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1) 
        * (b - 1) /*- dist1*/)/2) - (((width - a - 1) * (height - 1) 
        /*- dist2*/)/2) - (((width - 1) * (height - b - 1) /*- dist3*/)/2); 
    } 

Qualcuno potrebbe aiutarmi a risolvere l'algoritmo oa darmi un modo più semplice/migliore per farlo? Questo codice praticamente non funziona mai.

Mi dispiace per il codice lungo, non sapevo quali parti dovrei aggiungere, quindi ho messo l'intero algoritmo.

Edit: così ho cambiato l'algoritmo a questo (Grazie alla MBo):

public static int answer(int[][] vertices) 
{ 
    int a = (Math.abs((vertices[1][0] - vertices[0][0]) * (vertices[2][1] 
       - vertices[0][1]) - (vertices[2][0] - vertices[0][0]) * 
         (vertices[1][1] - vertices[0][1])))/2, 
     b = pointsOnLine(vertices[0][0], vertices[0][1], vertices[1][0], 
       vertices[1][1]) + pointsOnLine(vertices[1][0], 
       vertices[1][1], vertices[2][0], vertices[2][1]) + 
       pointsOnLine(vertices[0][0], vertices[0][1], 
       vertices[2][0], vertices[2][1]), 
      area = (2 * a - 2 - b)/2; // Also tried a + (b/2) - 1; 

    return (int)area; 
} 

public static int pointsOnLine(int x0, int y0, int x1, int y1) 
{ 
    BigInteger b1 = BigInteger.valueOf(Math.abs(x1 - x0)), 
       b2 = BigInteger.valueOf(Math.abs(y1 - y0)); 

    return b1.gcd(b2).intValue(); 
} 

Ma, non sempre la risposta giusta. Ho fatto qualcosa di male?

Answer 1

Picks theorem:
Numero di punti reticolari all'interno

i = (2*A + 2 - b)/2

dove A è l'area del triangolo, b è il numero di punti reticolari alle frontiere
Area through crossproduct:

2*A = Abs (V[1].x-V[0].x)*(V[2].y-V[0].y) - (V[2].x-V[0].x)*(V[1].y-V[0].y)) 

NumPoints on the edge tra i punti (x0, y0) - (x1, y1), incluso il primo punto, escluso la st (GCD è Great Common Divisor):

function PointsOnLine(x0, y0, x1, y1) = GCD(Abs(x2-x1), Abs(y2-y1)) 

per tutti i bordi:

b = PointsOnLine(V[0].x, V[0].y, V[1].x, V[1].y) + 
    PointsOnLine(V[1].x, V[1].y, V[2].x, V[2].y) + 
    PointsOnLine(V[0].x, V[0].y, V[2].x, V[2].y) 

Ora è possibile ottenere i

Answer 2

Sulla base @Mbo risposta: [Modificato]

private static long gcd(long n0, long n1) { 
    long a = n0; 
    long b = n1; 
    while (a != 0) { 
     long temp = a; 
     a = b % a; 
     b = temp; 
    } 
    return b; 
} 

public static long pointOnLine(long[][] vertices) {   
    return gcd(Math.abs(vertices[0][0] - vertices[1][0]), 
       Math.abs(vertices[0][1] - vertices[1][1])) + 
      gcd(Math.abs(vertices[1][0] - vertices[2][0]), 
       Math.abs(vertices[1][1] - vertices[2][1])) + 
      gcd(Math.abs(vertices[2][0] - vertices[0][0]), 
       Math.abs(vertices[2][1] - vertices[0][1])); 
} 

public static long area(long[][] vertices) { 
    return Math.abs((vertices[1][0] - vertices[0][0]) * (vertices[2][1] - vertices[0][1]) 
      - (vertices[2][0] - vertices[0][0]) * (vertices[1][1] - vertices[0][1])); 
} 

public static void main(String[] args) { 
    long[][] vertices = {{91207, 89566}, {-88690, -83026}, {67100, 47194}}; 
    //long[][] vertices = {{2,3}, {6,9}, {10,160}}; 
    long i = (area(vertices) + 2 - pointOnLine(vertices))/2; 
    System.out.println("points: " + i); 

}