が正方形に
を回転させ、私は上記のEgor Skriptunoffの答えを好きですが、私は に別の答えを与えることを試してみましょう。複雑さはO（N^2）だと私は思う。
アルゴリズム
点（P0、P1）（それらのN^2である）の任意の対について、P1に をP0からベクトルV01を見つけるし、次いで90 によってこのベクトルを回転させます度（V12になります）。それをP1に追加し、そこに という点があるかどうかを確認してください。 （これはハッシュマップルックアップで行うことができます - 詳細は以下を参照してください）もしそうなら あなたはP2を持っており、手順を続行します。
ベクトルをさらに90度回転させて（それはV23になります）、それを P2に追加して、ポイントを見つけることができるかどうかを確認します。 （再び、ハッシュマップルックアップによって）
もしそうなら、あなたはP3を持っており、手順を続行します。
は別の90度（それはV34となる）によってベクターを回し。 をP3に追加して、そこにポイントを見つけることができますか？ （再び、ハッシュマップルックアップによって）。 もしそうなら、この点P4がP0と同じであるかどうかをチェックしてください。その場合は、 あなたはちょうど正方形を検出しました。
次の図は、アイデアを示しています。
データ構造
正方形が回転可能である場合、ポイント のx、y座標は、浮動小数点（二重）でなければならず、整数ことができません。 ので、計算の多くは（例えばSQRT（2））
しかし、二重の表現は整数として正確にすることはできませんあなたが無理数を与える、 は、私たちは近くにある二つの二重の数字を治療するための を注意する必要があります十分な倍の 値で十分です。私のコードでは、 "approximate equivalence"のために を許可する許容値としてイプシロンを使用します。イプシロンとして1E-3を選んだ。
public class Point2 {
private double x;
private double y;
private final double eps = 1E-3;
public double getEps() {
return eps;
}
そしてequals()とhashCode()に関するすべての計算では、 はあなたが彼らの元 ダブル表現、xとyの値を「スナップ」ではないを使用してください。 （グラフィカルに、 グラフィカルエディタのようにグリッドサイズ がイプシロンである「グリッドにスナップ」機能を与えると想像することができます）。また、二重reprsentations には、正の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;
}
さらに、各正方形は4ポイントを持っています。 あなたのプログラムには、 のアルゴリズム（P0-> P1-> P2-> P3）で、角度関係 （上記のアルゴリズムを参照）を使用して、4つのポイントが順番に並んでいなければならないという規則を追加できます。しかし、あなたはまた、 と同じ4点があることを覚悟する必要があります。開始点を とする選択肢が4つあります。
P0->P1->P2->P3
P1->P2->P3->P0
P2->P3->P0->P1
P3->P0->P1->P2
これは広場オブジェクトのコンストラクタで行われ、常に 「カノニカル」 による入力がポイントを選ぶことができます。だからあなたのスクエアオブジェクト・コードは、同等のものとしてこれらの4点で指定された 次正方形を扱わなければなりません特定のセーリング機能 を開始点として使用します（例：他の点とのx値タイは、その後結ば対の中で最も低い xおよび小さいY）
テスト入力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
を有する点を選択した場合、最低Xを有する点を選択し、そして
試験結果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のテスト
の出力
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)
警告
エリックDuminilは互いに任意に近い、まだグリッド上の異なる点にスナップさ 2点が存在し得ることを指摘で正しいです。
私の頭の上から、私はこの問題を解決する方法を知らない。提案 を歓迎します！
など。 2点が異なると考えられている - 私は出力を次のようになるだろう
public static void debugPrint(boolean isDebug, String format, Object... args) {
if (!isDebug) {
return; // don't print
}
System.out.format(format, args);
}
：
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（）：これらの追加デバッグコード付き
@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));
}
！
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
リスト内で正方形を形成する点は連続していますか？ – StaticBeagle