Z^2で3点が正確に同一線上にあるかどうかを調べる方法

Question

もう一つの共線点問題。これは私が整数演算を使用していて、正確にの共線性を探していて、曖昧なイプシロンベースのテストではありません。

インラインアセンブリでは、私は正確な答えを得ることができます：x86の乗算命令をクロス積を計算する際に重要で、どちらも製品のハイとローの部分、両方へのアクセスを提供します（X - ） x（b-）;私は単純に2つの半分を一緒にORしてゼロをテストすることができます。しかし、私はそれはだ、Cでそれを行う方法があります願っています：

エレガント

ポータブル

1. オーバーフロー防止大体そのためです。そして、あると同時に、それを行うための方法で/しない：
   1. は大きな整数型を使用することを含む
   doubleにキャスト関与 - 私はすでにのために利用できる最大の整数型を使用していることを前提としてい私の座標成分タイプ
   3. は、偽陽性または偽陰性のいずれかを生じます。

   私はXは、セグメントABを超えているかどうかについては、この問題の心配はありませんよ。それはちょうど4つの無益な比較です。

   私の悪夢のシナリオは、各座標コンポーネントを2つの半分に分割し、明示的に長時間の乗算をしなければならないということです。部分積の上位半分をすべて追跡できるようにします。 （。そしてアドオンで持ち運び明示的に行うために持つ）

Answer 1

いくつかの比較と簡単なチェックの後に、、(x2,y2)の正の数の2つのカップルを得ることができます。x1*y2==x2*y1の場合はチェックしてください。

ユークリッドアルゴリズムを使用して、x1とy1のGCDを検索し、両方をGCMで除算することができます。 (x2,y2)についても同じことをしてください。両方のケースで同じカップルを得た場合、両方のベクトルは同じ方向になります。

Answer 2

三点（a、b、c）を正確に同一直線上にある場合、以下のアイデンティティが成り立つ：

c = a + (a - b) * scalar 

すなわち：

c - a = scalar * (a - b) 

(c-a)の最初のコンポーネントをとり、最初のコンポーネントを(a-b)で割り、その値を保存します。その後、後続のコンポーネントごとに繰り返します。いずれかが異なる場合は、点は同一線上にありません。

浮動小数点除算（これを実行する最も簡単な方法です）を完全に使用しないようにしたい場合は、比率を格納し、代わりにそれを比較する必要があります。