0

これは、私が解決できなかった 2D 計算幾何学の単純な問題です。

we have four points A, B, C, D defining a CONVEX QUADRILATERAL 

(not a square or a rectangle!)

we know the (x, y) coordinates of each point.

2 つのポイントを接続する 6 つのセグメントがあります。

AB, AC, AD, BC, BD, CD

これらのセグメントの交点の 1 つは、図の内側の点、つまり 2 つの対角線の交点を形成します。

対角線の対には 3 つの可能性があります。

[AB] and [CD]
[AC] and [BD]
[AD] and [BC]

(下図参照)

図

A、B、C、D の (x、y) 座標を変化させたときに、3 つの考えられるケースのどれが発生しているかを見つけるための単純なアルゴリズムを探しています。

4

5 に答える 5

1

ヒント: 凸包の点と線を定義することから始めるべきだと思います。Wiki-Graham Scan Alg. を使用して、凸包の作成に関与する線分を決定できます。線分を決定したら、対角線を簡単に見つけることができます。リンクの例を使用すると、次の線分を (アルゴリズムによって決定された順序で) 配列に格納できます (点の各ペアは線分を定義します)。

P,A
A,B
B,D
D,P

この配列から、対角点をすぐに取得して P、B および A、D にすることができます。

このアルゴリズムは角度の計算を必要とせず、領域の形状に関する仮定もありません。

于 2013-11-06T23:03:30.797 に答える
1

私が理解できる単純なもの：

  1. 点Aを取ります。
  2. ベクトル AB、AC、AD の傾きを測定します。

  3. それらの間の関係を参照してください。

      Case 1: SAC>SAB>SAD,
  Case 2: SAB>SAC>SAD,
  Case 3: SAB>SAD>SAC.

    360度の違いを考慮してください。

PS 角度が 180 を超える四角形を気にするかどうかはわかりません。はいの場合は、さらに考慮する必要があります。

于 2013-11-06T22:36:00.000 に答える
0

座標が次の場合:

0,0
0,1
1,0
1,1

x 座標と y 座標が同じものは対角線を形成し、x 座標と y 座標が異なるものは対角線を形成することがわかります。

したがって、座標が次の場合:

1,1
1,3
3,1
3,3

次に、a=b である a,b の文字が 1 を形成し、a!=b である a,b の文字が 1 を形成するため、1,1 と 3,3 の文字は 1 になり、1,3 と3,1.

これは正方形の場合にのみ機能することに注意してください。

また、どのような場合でも、これを行うことができます：

同じ座標を共有しないペアを一致させることができます。

為に

A--B
|  |
C--D

A と C は X 座標を共有し、A と B は Y 座標を共有しているため、A と D がペアであることを知ることができます。

共通の座標なし == 対角線。（この方法で正方形または長方形の場合。）

お役に立てれば。

于 2013-11-06T22:28:19.407 に答える