Определить квадрат в списке точек

Я хочу проверить, есть ли квадрат в списке объекта Point или нет.Определить квадрат в списке точек

Это моя точка класс:

class Point { 
    private int x; 
    private int y; 

    public Point(int x, int y) { 
     this.x = x; 
     this.y = y; 
    } 

    public int getX() { 
     return x; 
    } 

    public void setX(int x) { 
     this.x = x; 
    } 

    public int getY() { 
     return y; 
    } 

    public void setY(int y) { 
     this.y = y; 
    } 

    public int distanceSquare(Point q) { 
     return (x - q.getX()) * (x - q.getX()) + 
       (y - q.getY()) * (y - q.getY()); 
    } 
}

я могу проверить, если четыре точки квадратная или нет:

static boolean isSquare(Point p1, Point p2, Point p3, Point p4) { 
     int d2 = p1.distanceSquare(p2); // from p1 to p2 
     int d3 = p1.distanceSquare(p3); // from p1 to p3 
     int d4 = p1.distanceSquare(p4); // from p1 to p4 

     if (d2 == d3 && 2 * d2 == d4) { 
      int d = p2.distanceSquare(p4); 
      return (d == p3.distanceSquare(p4) && d == d2); 
     } 

     if (d3 == d4 && 2 * d3 == d2) { 
      int d = p2.distanceSquare(p3); 
      return (d == p2.distanceSquare(p4) && d == d3); 
     } 
     if (d2 == d4 && 2 * d2 == d3) { 
      int d = p2.distanceSquare(p3); 
      return (d == p3.distanceSquare(p4) && d == d2); 
     } 

     return false; 
    }

Но я не нашел лучший способ поиска площади в список точек.

Помогите мне!

источник

2016-12-17 Mohamed2a

Являются ли точки, которые образуют квадрат, смежный в списке? – StaticBeagle

Здесь O (N^2 Л.Г. (п)) -time и алгоритма О (п) -пространством. Если вы зададите вершины по углу, то для каждой пары {A, B} вы можете найти оба угла OC и OD.

compute angle for every point -- O(n) 
sort point by angles -- O(n*lg(n)) 
for each pair -- O(n^2*lg(n)) 
    if (B.x > A.x) && (B.y > A.y) 
     compute positions of C and D 
     compute angles of C and D 
     for C and D 
      if there is a pair of points with same angles and same positions 
       return true 
return false

Как найти координаты C:

Xc = Xb - (Yb - Ya) 
Yc = Yb + (Xb - Xa)

источник

2016-12-17 15:19:23 Yola

Возьмите все пары точек; для каждой пары вычисляют его угол, его длину и среднюю точку. Это займет время O (n^2).
Для каждого набора пар , имеющих такую же среднюю точку и ту же длину, сортируйте эти пары по углу, это займет общее время O (n^2 * log (n)). Это поможет вам найти две ортогональные диагонали одинаковой длины, имеющие одну и ту же среднюю точку (то есть квадрат!).
Общая сложность времени алгоритма O (n^2 * log (n)).

источник

2016-12-17 15:40:23

* Это поможет вам найти две ортогональные диагонали одинаковой длины, имеющие одну и ту же среднюю точку * - вы имеете в виду, что можете сделать это в lg (n) для каждой пары? Можете ли вы уточнить, пожалуйста? Для меня это выглядит как lg (n^2). – Yola

@Yola - просто переместите два указателя в этом отсортированном списке, чтобы найти два значения, имеющие delta = pi/2. Эта операция имеет линейную временную сложность –

ах, извините, я пропустил еще одну часть о наборах пар *, имеющих ту же среднюю точку и ту же длину *. Хотя неясно, как вы получаете такие наборы, какова сложность этой операции? А что, если у вас есть только один такой набор (точки на круге), то сортировка примет O (n^2 * lg (n^2)), правильно? – Yola

Обновлено также обнаружены повернутые квадраты

Мне нравится ответ Егора Skriptunoff в выше, но позвольте мне попытаться дать другой ответ. Я считаю, что сложность только O (N^2).

Алгоритм

Для любой пары точек (P0, P1) (есть N^2 из них), выяснить, вектор V01 от P0 до P1, а затем вращать этот вектор на 90 градусов (он становится V12). Добавьте его в P1 и посмотрите, можете ли вы найти точку ? (это можно сделать с помощью поиска хэшмапа - см. ниже). Если так , то у вас есть P2 и продолжите процедуру.

Поверните вектор еще на 90 градусов (он станет V23), добавьте его в P2 и посмотрите, можете ли вы найти там пункт? (Опять же, с помощью поиска хэшмапа)
Если это так, то у вас есть P3 и продолжите процедуру.

Поверните вектор еще на 90 градусов (он станет V34). Добавьте его в P3 и посмотрите, сможете ли там найти точку? (Опять же, с помощью поиска хэшмапа). Если да, проверьте также, если эта точка P4 такая же, как P0. Если это так, то вы только что обнаружили квадрат.

Следующая диаграмма иллюстрирует идею.

Структура данных

Если квадраты выполнены с возможностью вращения, то х и у координаты точки должны быть в плавающей точкой (двойной) и не может быть целым числом. Поскольку много вычислений даст вам иррациональные числа (например, SQRT (2))

Однако двойное представление может не быть точным, как целое, поэтому мы должны быть осторожными для лечения двух двойных номеров, которые близки достаточно одного и того же двойного значения . В моем коде я использую epsilon как допуск, который мы разрешаем для «приблизительной эквивалентности». Я выбрал 1E-3 как эпсилон.

public class Point2 { 
    private double x; 
    private double y; 
    private final double eps = 1E-3;  
    public double getEps() { 
     return eps; 
    }

А потом во всех вычислениях относительно equals() и hashCode(), убедитесь, что вы используете «щелкнул» значение х и у, а не их первоначальных двойных представлений. (Графически вы можете себе представить, что ваш графический редактор дает вам функцию «привязки к сетке», размер сетки - это epsilon). Также вам нужно быть осторожным, что в двойных рецензентах есть положительные 0 и отрицательные 0, и вы также должны относиться к ним как к того же значения.

Что-то вроде этого:

public long getXsnapped() { 
    return Math.round(this.getX()/this.getEps()); 
} 
public long getYsnapped() { 
    return Math.round(this.getY()/this.getEps()); 
} 
@Override 
public int hashCode() { 
    final int prime = 31; 
    int result = 1; 
    long temp; 
    temp = Double.doubleToLongBits(eps); 
    result = prime * result + (int) (temp^(temp >>> 32)); 
    if (Math.abs(this.getX())>this.getEps()) { 
     // include X only if it is larger than eps 
     temp = this.getXsnapped(); 
     result = prime * result + (int) (temp^(temp >>> 32)); 
    } 
    if (Math.abs(this.getY())>this.getEps()) { 
     temp = this.getYsnapped(); 
     result = prime * result + (int) (temp^(temp >>> 32)); 
    } 
    return result; 
} 
@Override 
public boolean equals(Object obj) { 
    if (this == obj) 
     return true; 
    if (obj == null) 
     return false; 
    if (getClass() != obj.getClass()) 
     return false; 
    Point2 other = (Point2) obj; 
    if (Double.doubleToLongBits(eps) != Double.doubleToLongBits(other.eps)) 
     return false; 
    boolean answer = true; 
    if (Math.abs(this.getX())>this.getEps() 
      || Math.abs(other.getX())>this.getEps()) { 
     // compare value and sign only if X of both points are larger than eps 
     if (this.getXsnapped()!= other.getXsnapped()) 
      answer = false;   
    } 
    if (Math.abs(this.getY())>this.getEps() 
      || Math.abs(other.getY())>this.getEps()) { 
     // compare value and sign only if Y of both points are larger than eps 
     if (this.getYsnapped()!= other.getYsnapped()) 
      answer &= false; 
    } 
    boolean isDebug = false; 
    Util.debugPrint(isDebug, "p1 %s; p2 %s: %b (eps is %.9f)%n" 
     , this, other, answer, this.getEps()); 
    return answer; 
}

Кроме того, каждый квадрат имеет четыре точки. Вы можете добавить правило в вашей программе, говоря, что четыре точки должны быть в порядке, как используется в алгоритмом (P0-> P1-> P2-> P3) с заданным угловым отношением (см. Алгоритм выше). Тем не менее, вы также должны быть осторожны, чтобы предоставили те же четыре точки, что есть четыре варианта, чтобы выбрать начальную точку. Таким образом, ваш Квадратный объектный код должен обработать следующих квадраты, установленных этих четырех точек, как эквивалент:

P0->P1->P2->P3 
P1->P2->P3->P0 
P2->P3->P0->P1 
P3->P0->P1->P2

Это может быть сделано в конструкторе площади объекта и всегда «КаноническаяФорм» вход на захватывающую точку с определенной плавающей функцией в качестве отправной точки (например,выбрать точку, имеющую самую низкую х и , если его значение х связь с другой точкой, а затем выбрать точку с наименьшим х и меньше у среди привязанной пары)

Тест вход 1

-1.4142, 9.8995 
-5.6569, 15.5563 
1.4142, 9.8995 
-1.4142, 14.1421 
-2.1213, 14.8492 
1.4142, 14.1421 
0.0000, 15.5563 
-2.1213, 17.6777 
7.0711, 11.3137 
5.6569, 12.7279 
4.2426, 14.1421 
6.3640, 10.6066 
7.0711, 14.1421 
5.6569, 15.5563 
1.4142, 19.7990 
7.7782, 14.8492

Результат теста 1

===== Given a set of following points from file src\detectSquare\inputSet1_45_1_1_0_0.txt ===== 
1: Point2 [x=-1.4142, y=9.8995] 
2: Point2 [x=-5.6569, y=15.5563] 
3: Point2 [x=1.4142, y=9.8995] 
4: Point2 [x=-1.4142, y=14.1421] 
5: Point2 [x=-2.1213, y=14.8492] 
6: Point2 [x=1.4142, y=14.1421] 
7: Point2 [x=0.0000, y=15.5563] 
8: Point2 [x=-2.1213, y=17.6777] 
9: Point2 [x=7.0711, y=11.3137] 
10: Point2 [x=5.6569, y=12.7279] 
11: Point2 [x=4.2426, y=14.1421] 
12: Point2 [x=6.3640, y=10.6066] 
13: Point2 [x=7.0711, y=14.1421] 
14: Point2 [x=5.6569, y=15.5563] 
15: Point2 [x=1.4142, y=19.7990] 
16: Point2 [x=7.7782, y=14.8492] 
===== The following squares have been found ===== 
1: SquareRotatable [points=[Point2 [x=4.2427, y=14.1421], Point2 [x=5.6569, y=12.7279], Point2 [x=7.0711, y=14.1421], Point2 [x=5.6569, y=15.5563]]]

Тест вход 2

0.0000, 0.0000 
-0.7071, 0.7071 
-1.4142, 1.4142 
0.7071, 0.7071 
0.0000, 1.4142 
-0.7071, 2.1213 
1.4142, 1.4142 
0.7071, 2.1213 
0.0000, 2.8284

Результат теста 2

===== Given a set of following points from file src\detectSquare\inputSet2_45_0_0_0_0.txt ===== 
1: Point2 [x=0.0000, y=0.0000] 
2: Point2 [x=-0.7071, y=0.7071] 
3: Point2 [x=-1.4142, y=1.4142] 
4: Point2 [x=0.7071, y=0.7071] 
5: Point2 [x=0.0000, y=1.4142] 
6: Point2 [x=-0.7071, y=2.1213] 
7: Point2 [x=1.4142, y=1.4142] 
8: Point2 [x=0.7071, y=2.1213] 
9: Point2 [x=0.0000, y=2.8284] 
===== The following squares have been found ===== 
1: SquareRotatable [points=[Point2 [x=-1.4142, y=1.4142], Point2 [x=0.0000, y=0.0000], Point2 [x=1.4142, y=1.4142], Point2 [x=0.0000, y=2.8284]]] 
2: SquareRotatable [points=[Point2 [x=-0.7071, y=0.7071], Point2 [x=0.7071, y=0.7071], Point2 [x=0.7071, y=2.1213], Point2 [x=-0.7071, y=2.1213]]] 
3: SquareRotatable [points=[Point2 [x=-1.4142, y=1.4142], Point2 [x=-0.7071, y=0.7071], Point2 [x=0.0000, y=1.4142], Point2 [x=-0.7071, y=2.1213]]] 
4: SquareRotatable [points=[Point2 [x=-0.7071, y=2.1213], Point2 [x=0.0000, y=1.4142], Point2 [x=0.7071, y=2.1213], Point2 [x=-0.0000, y=2.8284]]] 
5: SquareRotatable [points=[Point2 [x=-0.7071, y=0.7071], Point2 [x=0.0000, y=0.0000], Point2 [x=0.7071, y=0.7071], Point2 [x=0.0000, y=1.4142]]] 
6: SquareRotatable [points=[Point2 [x=0.0000, y=1.4142], Point2 [x=0.7071, y=0.7071], Point2 [x=1.4142, y=1.4142], Point2 [x=0.7071, y=2.1213]]]

Программа испытаний JUnit тестирования Point2#getXsnapped() (фрагмент только)

import org.junit.Before; 
import org.junit.BeforeClass; 
import org.junit.Ignore; 
import org.junit.Test; 

public class Point2Test { 
    private List<Point2> points = new ArrayList<>(); 

    @Before 
    public void setUp() throws Exception { 
     points.add(new Point2(0.49999999f, 0)); 
     points.add(new Point2(0.50000001f, 0)); 
    } 
    ... 

    @Test 
    public void testGetXsnapped() { 
     System.out.format("testing xSnapped of two points: %s and %s%n" 
       , points.get(0), points.get(1)); 
     System.out.format("and they are %d and %d respectively%n" 
       , points.get(0).getXsnapped() 
       , points.get(1).getXsnapped()); 
     System.out.format("(Note: epsilon is %f)%n" 
       , points.get(0).getEps()); 

     assertEquals(points.get(0).getXsnapped() 
        , points.get(1).getXsnapped()); 
    } 
}

Выход JUnit Test

testing xSnapped of two points: Point2 [x=0.5000, y=0.0000] and Point2 [x=0.5000, y=0.0000] 
and they are 500 and 500 respectively 
(Note: epsilon is 0.001000)

Caveat

Эрик Duminil правильно указывает на то, что там может быть 2 точки, сколь угодно близко друг к другу, и по-прежнему быть привязанным к различным точкам на сетке.

Сверху моей головы я не знаю, как решить эту проблему. Предложения приветствуются!

E.g.

@Before 
public void setUp() throws Exception { 
    Point2 dummy = new Point2(0, 0); // just to get epsilon 
    points.add(new Point2(dummy.getEps()*0.5, 0)); 
    points.add(new Point2(dummy.getEps()*0.49999999999999, 0)); 
}

С этим добавленным отладки кода:

public long getXsnapped() { 
    boolean isDebug = true; 
    String _ = " "; // indent 
    double X = this.getX(); 
    Util.debugPrint(isDebug, _ + "X is %E (long bits is 0x%x)%n" 
           , X, Double.doubleToLongBits(X)); 
    double eps = this.getEps(); 
    Util.debugPrint(isDebug, _ + "eps is %E%n", eps); 
    double fraction = X/eps; 
    Util.debugPrint(isDebug, _ + "fraction is %E (long bits is 0x%x)%n" 
           , fraction, Double.doubleToLongBits(fraction)); 
    long answer = Math.round(fraction); 
    Util.debugPrint(isDebug, _ + "xSnapped is %d%n", answer); 
    return answer; 
}

Util.debugPrint():

public static void debugPrint(boolean isDebug, String format, Object... args) { 
    if (!isDebug) { 
     return; // don't print 
    } 
    System.out.format(format, args); 
}

я хотел бы получить следующий вывод - две точки считаются разными!

testing xSnapped of two points: Point2 [x=0.0005, y=0.0000] and Point2 [x=0.0005, y=0.0000] 
    X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9fc) 
    eps is 1.000000E-03 
    fraction is 5.000000E-01 (long bits is 0x3fe0000000000000) 
    xSnapped is 1 
    X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9a0) 
    eps is 1.000000E-03 
    fraction is 5.000000E-01 (long bits is 0x3fdfffffffffff4c) 
    xSnapped is 0 
and they are 1 and 0 respectively 
(Note: epsilon is 0.001000) 
delta between the two x (as double) is 9.974660E-18 
    X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9fc) 
    eps is 1.000000E-03 
    fraction is 5.000000E-01 (long bits is 0x3fe0000000000000) 
    xSnapped is 1 
    X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9a0) 
    eps is 1.000000E-03 
    fraction is 5.000000E-01 (long bits is 0x3fdfffffffffff4c) 
    xSnapped is 0

источник

2016-12-17 17:22:13 leeyuiwah

Это работает для повернутых квадратов? – Lidae

Извините, нет. Неплохо подмечено. Я посмотрю, смогу ли я дать обновленный ответ позже. – leeyuiwah

Спасибо, что указали на необходимость того, чтобы квадрат мог поворачиваться. Я обновил свой ответ выше. – leeyuiwah

Определить квадрат в списке точек

ответ

Смежные вопросы