1

私は混乱しています。点が線分上にあるかどうかを確認したいのです。私はそれをグーグルしますが、基本的に2つの異なる答えを受け取ります.

http://en.wikipedia.org/wiki/Line_segment

と

http://www.softwareandfinance.com/Turbo_C/Check_Point_Lies_line_Segment.html

正解は？postgis のようなジオメトリ アプリケーションには、このアルゴリズム (C 言語の方が優れています) が必要です。

4

3 に答える 3

8

浮動小数点演算は、必要なすべての数値を格納できるわけではありません。ある時点で、近似する必要があります。ウィキペディアから入手したアルゴリズムは次のことを伝えていると思います。

y=mx+b

あなたが知っているm、あなたが知っているb、今プラグインして、方程式が成り立つことを確認してください。数学に最適です。(2 の平方根) の 2 乗は、4 の平方根に等しくなります。

しかし今、あなたがそれをコンピュータ上で行うと想像してみてください。コンピューターは小さな整数を保持するのが得意なので、4 の平方根は正確に 2 になります。ただし、右辺の 2 の平方根は少しずれています。いくつかの桁を切り取らなければならなかったので、それを 2 乗すると、1.999998 またはそのようなものになる可能性があります。これに対応するには、次のことを確認する必要がありますy is approx. mx+b。

tolerance = .01
x,y
rhs = m*x + b //right hand side
dif = abs(rhs - y)
if dif < tolerance //the point is approximately on the segment

次に、境界ボックスを確認する必要があります（最大x、y、最小x、yを見つけます）

もちろん、これらの方法は完全ではありません ( http://xkcd.com/217/ ) が、ほとんどの実用的なアプリケーションでは十分に当てはまります。正確な数値が本当に必要な場合は、Wolfram Alpha (API か何かがあると聞きました) を使用するか、独自の正確な数値ライブラリを作成することをお勧めします。

于 2013-02-24T17:13:06.647 に答える
2

先に進む前に、何らかの方法で線をグラフィカルに表現しただけなのか、それとも実際に線を作成した式を持っているのかを知っておくと役に立ちます。「平面」ではなく「線」と言ったので、2D線について話していると思います。

線の式がある場合、答えは簡単です。点の x、y 値を式に代入します。式が有効な場合、点は線上にあります。

たとえば、線が y = 2x + 1.5 で、ポイントが (1,1) の場合

1 = 1(1) + 1.5 1 = 3.5 は偽なので、点は線上にありません

変数の数や線の形に関係なく、2D または 3D の線の数式でも同じことが言えます。

x + 2y = 0 1.5x + 12y - 4z = 84

作業している点をポップするだけで、方程式の両辺が等しい場合、その点は線 (または平面) 上にあります。

道路地図のビットマップなどのグラフィカルなソリューションを探していて、誰かがクリックした場所が「道路の線上」にあるかどうかを知りたい場合、それはまったく別の問題です。

于 2013-02-24T17:18:50.583 に答える
1

どちらも正しいです。

Turbo C は非常に古く、現在は規格外であることを覚えておいてください。たとえば、void main() は使用しないでください (代わりに int main() を使用します)。

また、C の浮動小数点で比較 (==) を使用しないでください。浮動小数点は不正確であるためです。これが、Turbo C コードが < 0.001 %% > 0.001 スタイルである理由です。

于 2013-02-24T17:13:15.447 に答える