В файле с 10 000 точками формы X1 y1 X2 y2 ,,, Как определить не менее 4, которые образуют квадрат? Java

Question

Я попробовал этот пример только с 4 пунктов, она работает с:

-1 -1
4 -2
1 -4

import java.io.BufferedReader; 
import java.io.FileReader; 
import java.io.IOException; 

public class CarreSimple { 
    static int distance(Point point1, Point point2) { 
     int dist = (int) (Math.pow(point1.getX() - point2.getX(), 2) + Math.pow(point1.getY() - point2.getY(), 2)); 
     dist = (int) Math.sqrt(dist); 
     return dist; 
    } 

    public static void main(String[] args) { 
     boolean EstCarre = false; 
     Point[] tb = new Point[10000]; 
     int i = 0; 
     BufferedReader br = null; 
     try { 
      br = new BufferedReader(new FileReader("C:/Users/walid/Downloads/points.txt")); 
      String line; 
      while ((line = br.readLine()) != null) { 
       String[] parts = line.split(" "); 
       int part1 = Integer.parseInt(parts[0]); 
       int part2 = Integer.parseInt(parts[1]); 

       Point p = new Point(part1, part2); 
       tb[i] = p; 
       System.out.println("X " + tb[i].getX() + " y " + tb[i].getY()); 
       i++; 
      } 
     } catch (IOException e) { 
      e.printStackTrace(); 
     } finally { 
      try { 
       if (br != null) { 
        br.close(); 
       } 
      } catch (IOException ex) { 
       ex.printStackTrace(); 
      } 
     } 

     int[] distances = new int[3]; 
     distances[0] = distance(tb[0], tb[1]); 
     distances[1] = distance(tb[0], tb[2]); 
     distances[2] = distance(tb[0], tb[3]); 
     System.out.println(distances[0]); 

     int CoteEgal1 = -1; 
     int CoteEgal2 = -1; 
     int CotePasEgal = -1; 


     if (distances[0] == distances[1]) { 
      if (distances[0] != distances[2]) { 
       CoteEgal1 = 0; 
       CoteEgal2 = 1; 
       CotePasEgal = 2; 
      } 
     } else if (distances[1] == distances[2]) { 
      if (distances[1] != distances[0]) { 
       CoteEgal1 = 1; 
       CoteEgal2 = 2; 
       CotePasEgal = 0; 
      } 
     } else if (distances[0] == distances[2]) { 
      if (distances[0] != distances[1]) { 
       CoteEgal1 = 0; 
       CoteEgal2 = 2; 
       CotePasEgal = 1; 
      } 
     } 
     if (CoteEgal1 != -1) { 
      int coinOpposÈ = 0; 
      switch (CotePasEgal) { 
       case 0: 
        coinOpposÈ = distance(tb[2], tb[3]); 
        break; 
       case 1: 
        coinOpposÈ = distance(tb[1], tb[3]); 
        break; 
       case 2: 
        coinOpposÈ = distance(tb[1], tb[2]); 
        break; 
       default: 
        break; 
      } 

      if (coinOpposÈ == distances[CotePasEgal]) { 
       int diagonal = coinOpposÈ; 
       int adjacent = distances[CoteEgal1]; 
       boolean stillOK = true; 
       for (int a = 0; a < 4; a++) { 
        int diagonalCount = 0; 
        int adjacentCount = 0; 
        for (int b = 0; b < 4; b++) { 
         if (a != b) { 
          int dist = distance(tb[a], tb[b]); 
          if (dist == diagonal) { 
           diagonalCount++; 
          } else if (dist == adjacent) { 
           adjacentCount++; 
          } 
         } 
        } 
        // est ce que on a 1 diagonal et 2 adjacents 
        if (!(diagonalCount == 1 && adjacentCount == 2)) { 
         stillOK = false; 
         break; 
        } 
       } 
       if (stillOK) { 
        EstCarre = true; 
       } 
      } 
     } 
     if (EstCarre) { 
      System.out.println("C'est un carre"); 
     } else { 
      System.out.println("Ce n'est pas un carre"); 
     } 
    } 
} 

К сделайте петлю на файле в 10 000 очков и проверьте каждую комбинацию 4, которую я нашел слишком сложной.

import java.io.BufferedReader; 
import java.io.FileReader; 
import java.io.IOException; 

public class Square { 
    static int distance(Point point1, Point point2) { 
     int dist = (int) (Math.pow(point1.getX() - point2.getX(), 2) + Math.pow(point1.getY() - point2.getY(), 2)); 
     dist = (int) Math.sqrt(dist); 
     return dist; 
    } 

    public static void main(String[] args) { 
     boolean EstCarre = false; 
     Point[] tb = new Point[10000]; 
     int i = 0; 
     BufferedReader br = null; 
     try { 
      br = new BufferedReader(new FileReader("C:/Users/walid/Downloads/exercice.txt")); 
      String line; 
      while ((line = br.readLine()) != null) { 
       String[] parts = line.split(" "); 
       int part1 = Integer.parseInt(parts[0]); 
       int part2 = Integer.parseInt(parts[1]); 

       Point p = new Point(part1, part2); 
       tb[i] = p; 
       System.out.println("X " + tb[i].getX() + " y " + tb[i].getY()); 
       i++; 
      } 
     } catch (IOException e) { 
      e.printStackTrace(); 
     } finally { 
      try { 
       if (br != null) { 
        br.close(); 
       } 
      } catch (IOException ex) { 
       ex.printStackTrace(); 
      } 
     } 
     for (int i2 = 0; i2 < 10000; i2++) { 
      for (int j = 0; j < 10000; j++) { 
       for (int k = 0; k < 10000; k++) { 
        for (int l = 0; l < 10000; l++) { 
         if (i2 != j && i2 != k && i2 != l && j != k && j != l && k != l) { 
          int[] distances = new int[10000000]; 
          distances[i2] = distance(tb[i2], tb[j]); 
          distances[j] = distance(tb[i2], tb[k]); 
          distances[k] = distance(tb[i2], tb[l]); 

          int CoteEgal1 = -1; 
          int CoteEgal2 = -1; 
          int CotePasEgal = -1; 

          if (distances[i2] == distances[j]) { 
           if (distances[i2] != distances[k]) { 
            CoteEgal1 = i2; 
            CoteEgal2 = j; 
            CotePasEgal = k; 
           } 
          } else if (distances[i2] == distances[k]) { 
           if (distances[j] != distances[i2]) { 
            CoteEgal1 = j; 
            CoteEgal2 = k; 
            CotePasEgal = i2; 
           } 
          } else if (distances[i2] == distances[k]) { 
           if (distances[i2] != distances[j]) { 
            CoteEgal1 = i2; 
            CoteEgal2 = k; 
            CotePasEgal = j; 
           } 
          } 

          int coinOpposÈ = 0; 
          if (CoteEgal1 != -1) { 
           if (CotePasEgal == i2) { 
            coinOpposÈ = distance(tb[k], tb[l]); 
           } else if (CotePasEgal == j) { 
            coinOpposÈ = distance(tb[j], tb[l]); 
           } else if (CotePasEgal == k) { 
            coinOpposÈ = distance(tb[j], tb[k]); 
           } 

           if (coinOpposÈ == distances[CotePasEgal]) { 
            int diagonal = coinOpposÈ; 
            int adjacent = distances[CoteEgal1]; 
            boolean stillOK = true; 
            for (int a = 0; a < 10000000; a++) { 
             int diagonalCount = 0; 
             int adjacentCount = 0; 
             for (int b = 0; b < 10000000; b++) { 
              if (a != b) { 
               int dist = distance(tb[a], tb[b]); 
               if (dist == diagonal) { 
                diagonalCount++; 
               } else if (dist == adjacent) { 
                adjacentCount++; 
               } 
              } 
             } 
             // est ce que on a 1 diagonal et 2 adjacents 
             if (!(diagonalCount == 1 && adjacentCount == 2)) { 
              stillOK = false; 
              break; 
             } 
            } 
            if (stillOK) { 
             EstCarre = true; 
            } 
           } 
          } 
         } 
         if (EstCarre) { 
          System.out.println("square found"); 
         } 
        } 
       } 
      } 
     } 
    } 
} 

код 2: пара это класс, который занимает две точки

import java.io.BufferedReader; 
import java.io.FileReader; 
import java.io.IOException; 
import java.util.Iterator; 
import java.util.Map; 
import java.util.HashMap; 
import java.util.Set; 

public class CarreP { 
    public static void main(String[] args) { 
     Point[] tb = new Point[10000]; 
     int i = 0; 
     BufferedReader br = null; 
     try { 
      br = new BufferedReader(new FileReader("C:/Users/walid/Downloads/exercice.txt")); 
      String line; 
      while ((line = br.readLine()) != null) { 
       String[] parts = line.split(" "); 
       int part1 = Integer.parseInt(parts[0]); 
       int part2 = Integer.parseInt(parts[1]); 

       Point p = new Point(part1, part2); 
       tb[i] = p; 
       i++; 
      } 
     } catch (IOException e) { 
      e.printStackTrace(); 
     } finally { 
      try { 
       if (br != null) { 
        br.close(); 
       } 
      } catch (IOException ex) { 
       ex.printStackTrace(); 
      } 
     } 

     HashMap<Couple, Integer> hmap = new HashMap<Couple, Integer>(); 
     int j = 0; 
     while (j < tb.length) { 
      for (int k = 0; k < tb.length; k++) { 
       int xcarre = (int) Math.pow(tb[j].getX() - tb[k].getX(), 2); 
       int ycarre = (int) Math.pow(tb[j].getY() - tb[k].getY(), 2); 

       int distance = (int) Math.sqrt(xcarre + ycarre); 
       Couple c = new Couple(tb[k], tb[k]); 
       hmap.put(c, distance); 
       Set set = hmap.entrySet(); 
       Iterator iterator = set.iterator(); 
       Iterator iterator2 = set.iterator(); 
       int[] distances = new int[hmap.size()]; 
       int s = 0; 
       while (iterator.hasNext()) { 
        Map.Entry mentry = (Map.Entry) iterator.next(); 
        distances[s] = (int) mentry.getValue(); 
        System.out.println(distances[s]); 
        s++; 
       } 
       int CoteEgal1 = -1; 
       int CoteEgal2 = -1; 
       int CoteInegal = -1; 
       for (int i1 = 0; i1 < distances.length; i1++) { 
        for (int i2 = 0; i2 < distances.length; i2++) { 
         for (int i3 = 0; i3 < distances.length; i3++) { 
          if (distances[i1] == distances[i2]) { 
           if (distances[i1] != distances[i3]) { 
            CoteEgal1 = i1; 
            CoteEgal2 = i2; 
            CoteInegal = i3; 
           } 
          } else if (distances[i2] == distances[i3]) { 
           if (distances[i2] != distances[i1]) { 
            CoteEgal1 = i2; 
            CoteEgal2 = i3; 
            CoteInegal = i1; 
           } 
          } else if (distances[i1] == distances[i3]) { 
           if (distances[i1] != distances[i2]) { 
            CoteEgal1 = i1; 
            CoteEgal2 = i3; 
            CoteInegal = i2; 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
} 

Answer 1

Основная идея заключается в следующем:

Предположим, у нас есть две точки: A и B. Есть только два способа построить квадрат с этим указывает: ABCD и ABEF (смотри рисунок ниже). Теперь рассмотрим AB как вектор. Мы можем повернуть его на 90 градусов по часовой стрелке, и мы получим точку D. Если переместить его в точку В, то мы получим точку C. Аналогично можно вращать AB 90 градусов против часовой стрелки и получить F и E.

Теперь нам нужно только проверить, содержит ли файл точки C и D, или E и F. Если это так, у нас есть квадрат. Мы можем сделать это быстро, если мы сохраним все точки в hashmap.

Вот пример реализации:

import java.util.HashSet; 
import java.util.Set; 

public class Main { 
    public static Set<Point> pointsSet = new HashSet<>(); 

    public static void main(String[] args) { 
     //Suppose, that points are already parsed from file 
     Point[] points = new Point[]{ 
       new Point(-1, -1), 
       new Point(2, 1), 
       new Point(4, -2), 
       new Point(1, -4) 
     }; 

     //Fill hashset with points. Important: hashCode() and equals() methods are overrided in Point class 
     for (Point point : points) { 
      pointsSet.add(point); 
     } 

     Point point1; 
     Point point2; 
     Point suggested_point3; 
     Point suggested_point4; 

     //Consider every pair of points 
     for (int i = 0; i < points.length - 1; i++) { 
      point1 = points[i]; 
      for (int j = i + 1; j < points.length; j++) { 
       point2 = points[j]; 

       //Calculate vector coordinates for pair of points 
       Vector vector = new Vector(point2.getX() - point1.getX(), point2.getY() - point1.getY()); 

       //Rotate vector clockwise by 90 degrees and calculate coordinates, 
       //where two more points should be to form a square with current pair of points 
       Vector clockwise_rotated_vector = rotateVector(vector, 90); 
       suggested_point3 = moveVectorToPoint(clockwise_rotated_vector, point1); 
       suggested_point4 = moveVectorToPoint(clockwise_rotated_vector, point2); 
       if (pointsSet.contains(suggested_point3) && pointsSet.contains(suggested_point4)) { 
        squareFound(point1, point2, suggested_point3, suggested_point4); 
       } 

       //Same for counterclockwise rotated vector 
       Vector counterclockwise_rotated_vector = rotateVector(vector, -90); 
       suggested_point3 = moveVectorToPoint(counterclockwise_rotated_vector, point1); 
       suggested_point4 = moveVectorToPoint(counterclockwise_rotated_vector, point2); 
       if (pointsSet.contains(suggested_point3) && pointsSet.contains(suggested_point4)) { 
        squareFound(point1, point2, suggested_point3, suggested_point4); 
       } 
      } 
     } 
    } 

    private static void squareFound(Point point1, Point point2, Point point3, Point point4) { 
     System.out.println(String.format("%s, %s, %s, %s", point1, point2, point3, point4)); 
    } 

    private static Point moveVectorToPoint(Vector vector, Point point) { 
     double x = point.getX() + vector.getX(); 
     double y = point.getY() + vector.getY(); 
     return new Point(x, y); 
    } 

    private static Vector rotateVector(Vector original_vector, double degrees) { 
     double radians = Math.toRadians(degrees); 
     double x = original_vector.getX() * Math.cos(radians) - original_vector.getY() * Math.sin(radians); 
     double y = original_vector.getX() * Math.sin(radians) + original_vector.getY() * Math.cos(radians); 
     return new Vector(x, y); 
    } 
} 

Класс Point:

import java.math.BigDecimal; 
import java.util.Locale; 

public class Point { 
    public Point(double x, double y) { 
     this.x = x; 
     this.y = y; 

     //Store decimal values with certain scale, which would later be used for hashCode() calculation 
     this.decimalX = new BigDecimal(x).setScale(DECIMAL_SCALE, BigDecimal.ROUND_HALF_EVEN); 
     this.decimalY = new BigDecimal(y).setScale(DECIMAL_SCALE, BigDecimal.ROUND_HALF_EVEN); 
    } 

    private static final int DECIMAL_SCALE = 3; 

    private double x; 
    public double getX() { 
     return x; 
    } 

    private double y; 
    public double getY() { 
     return y; 
    } 

    private BigDecimal decimalX; 
    private BigDecimal decimalY; 

    @Override 
    public boolean equals(Object o) { 
     if (this == o) return true; 
     if (o == null || getClass() != o.getClass()) return false; 

     Point point = (Point) o; 

     if (!decimalX.equals(point.decimalX)) return false; 
     return decimalY.equals(point.decimalY); 
    } 

    @Override 
    public int hashCode() { 
     //calculate for decimal values, so two very close enough points will have equal hash codes 
     int result = decimalX.hashCode(); 
     result = 31 * result + decimalY.hashCode(); 
     return result; 
    } 

    @Override 
    public String toString() { 
     return String.format(Locale.ENGLISH, "(%2f,%2f)", x, y); 
    } 
} 

Класс Vector:

public class Vector { 
    public Vector(double x, double y) { 
     this.x = x; 
     this.y = y; 
    } 

    private double x; 
    public double getX() { 
     return x; 
    } 

    private double y; 
    public double getY() { 
     return y; 
    } 
} 

UPDATE: Как уже упоминалось в комментариях s, было немного улучшений, поэтому я обновил свой код.

Answer 2

найти все возможные комбинации квадратов из 10000 точек было бы слишком много работы делать это перебором.

Итак, вам нужно найти точки, которые может содержать, чтобы сформировать квадрат, то есть точки, которые имеют координаты X или Y.

Итак, загрузите все точки в память, «индексируя» их, создав Map<Integer, Set<Integer>>, сопоставляя координаты X с набором координат Y. Значение равно Set, поэтому дубликаты точек устраняются и улучшают производительность кода ниже.

Теперь наступает более грубая сила, но она значительно уменьшена, поэтому не должно быть слишком плохо. Поиск как этот (псевдо-код, так что вы должны сделать часть этого тоже):

for eRight in xMap: 
    xRight = eKey.key 
    continue if eRight.value.size() == 1 
    for eLeft in xMap: 
     xLeft = eLeft.key 
     continue if xLeft >= xRight 
     continue if eLeft.value.size() == 1 
     // at this point we now have two distinct X coordinates 
     // with their corresponding collection of Y coordinates 
     for yTop : eLeft.value: 
      continue if ! eRight.value.contains(yTop) 
      for yBottom : eLeft.value: 
       continue if yBottom >= yTop // assuming (0,0) is lower-left 
       continue if ! eRight.value.contains(yBottom) 
       // at this point we now have two distinct Y coordinates 
       // that fit both X coordinates, i.e we have a rectangle 
       new Rectangle(xLeft, yTop, xRight, yBottom) 

Вышеприведенный код находит прямоугольниками, не квадратов. Я оставлю это вам, чтобы изменить его, чтобы найти квадраты.
Подсказка: Цикл yBottom (или yTop) заменен на расчет.

Answer 3

У меня есть ответ, подобный приведенному выше Марату Сафину, за исключением того, что я думаю, что мы должны быть осторожны в том, что арифметика с плавающей запятой неточна, и мы должны быть осторожны, что после некоторых этапов расчета число с плавающей запятой, 3.1415926 может стать 3.1415927 (просто отличаются 1E-7). Решением этого является то, что мы также должны объявить аргумент epsilon (допуск), который позволяет нам «приблизительно равняться» из двух чисел с плавающей запятой (например, double).

В ответе также есть тестовый ввод, который вы можете использовать для проверки своей программы.

Вы можете найти свой ответ здесь в другом СЦ пост Detect square in a List of Points