Loading [MathJax]/jax/output/CommonHTML/jax.js

同一直線上に並ぶ点のカウント

問題設定

  • 2次元平面上の N 点の座標が与えられる
    • (1) 同一直線上に並んでいる3点組の個数を求めよ
    • (2) 最も多くの点を通る直線(複数ある場合はその一例)と、通る点の個数を求めよ

制約とか

  • 座標は整数値で与えられ、各点の座標 |x|,|y|109
    • つまり、傾きを求める場合などに除算をおこない小数型にすると、精度が足りず、誤差が生じうる

解法例

O(N3) 解法

(1)

全ての3点組について、同一直線上に存在するか調べればよい。

(2)

2点 i,ji<j)を固定し、通る直線 L を求める。
3点目を j<k の範囲で探索し、L 上にあった k の個数+2が、その直線が通る点の個数。

全ての i,j を通して、最も通った点の数が多い直線が求めるもの。

3点が同一直線上か調べる方法

いくつかの方法がある。なるべく途中で小数が出てこないようにする方がよい。

面積が0

3点に囲まれた三角形の面積は以下で求められる。

  • 12|(x2x1)(y3y1)(x3x1)(y2y1)|

これが0なら同一直線上にある。

反時計回り判定

幾何でよく使われるユーティリティ関数に、ccw(Counter-ClockWise、反時計回り判定)がある。
AB の線分から見て、BC がどっち向きに曲がっているか(まっすぐか)を、外積で判定する。

汎用性があるので、これで判定してもよい。

O(N2) 解法

2点組ごとに「2点を結ぶ直線の方程式 ax+by+c=0 の係数 (a,b,c)」を求め、それごとにカウントする。

(x1,y1),(x2,y2) を通る直線の方程式は、dx=x2x1,dy=y2y1 として、以下のようになる。

ただし、係数に定数倍をかけたものは (a,b,c) が異なっても同一の直線を示すので、それらを統一する必要がある。

  • dxdy は、GCDで割って互いに素にしておく
  • dx が負の場合、dx,dy1 をかける
  • dx が0かつ dy が負の場合、dy を正にする

こうすると、違いを吸収して、同一の直線は同一の (a,b,c) となる。

k 個の点が並ぶ直線は、k(k1)2 回カウントされることになるので、 最終カウント結果から、各直線にいくつの点が並ぶか復元できる。

(1)

O(N2) 本の全てのカウントされた直線に対して個数を復元する。k 個の点が並ぶ直線上には、kC3 組の3つ組みがある。

(2)

最も多くカウントされた直線が、求める直線である。

programming_algorithm/geometry/collinear_points.txt · 最終更新: 2024/03/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0