Wie man Picks Theorem für jedes gegebene Dreieck verwendet

Question

Also ich möchte die Anzahl der Punkte innerhalb eines gegebenen Dreiecks berechnen. Ich weiß, dass ich Picks Theorem verwenden muss, aber mein Code endet mit der Menge an if-else if-Anweisungen, die für jeden Fall zu testen sind. Ich habe dies wurde unter Verwendung von als Führung How many integer points within the three points forming a triangle?, aber dann mit diesem Ende (. Vertices ist ein Array von 3 Arrays Jedes Array ist die (x, y) Koordinaten eines Scheitels des Dreiecks):

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); 
    } 

Könnte jemand mir helfen, entweder den Algorithmus zu reparieren oder mir einen leichteren/besseren Weg zu geben? Dieser Code funktioniert so gut wie nie.

Sorry über den langen Code, ich wusste nicht, welche Teile ich hinzufügen sollte, also legte ich den ganzen Algorithmus.

Edit: Also änderte ich den Algorithmus auf diese (Dank 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(); 
} 

Aber ich habe nicht immer die richtige Antwort. Habe ich etwas falsch gemacht?

Answer 1

Picks theorem:
Anzahl der Gitterpunkte innerhalb

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

wobei A Fläche des Dreiecks ist, b ist die Anzahl der Gitterpunkte an den Grenzen
Gebiet 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 zwischen den Punkten (x0, y0) - (x1, y1), einschließlich des ersten Punktes, außer la st (GCD ist Great Common Divisor):

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

für alle Kanten:

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) 

Jetzt können Sie i

Answer 2

Basierend auf @Mbo Antwort erhalten: [EDITED]

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); 

}