n角形の頂点を通るy軸に平行な直線とn角形の公差部

質問

xy平面上に P1(x1, y1), P2(x2, y2), ..... Pn(xn, yn) の n角形がある時、各点を通る y軸に平行な直線と n角形の交差部の長さを計算する方法を考えています。
図で示された赤線の長さを計算したいのです。
座標値が定数なら方程式で解けますが、座標値が変数の場合にどのようなアルゴリズムでプログラムすれば良いいのか、途方に暮れています。
どなたか、お知恵を拝借願います。

回答No.3

178-tall · ベストアンサー

>「それぞれの点において、その点を通るy軸に平行な直線と交わるのは、どの2点を結んだ直線か？」

各点の座標 Pi(xi, yi) とペア {Pi, Pj} の連結セットから推定できませんか？

[例] P4 を「通る y 軸に平行な直線と交わる連結ペア {Pi, Pj} は？

各点の座標と連結ペアセットから、
　候補ペア ： {P6, P5} , {P2, P4}
をピックアップ可。

補足

ご回答ありがとうございます。
> 各点の座標と連結ペアセットから、
> 　候補ペア ： {P6, P5} , {P2, P4}
> をピックアップ可。

おそらく私が求めている解法だと思うのですが、結合セットとか連結ペアという概念がわかりません。
検索してもプラレール関係のホームページしか見つかりません（笑）
その概念を説明しているホームページがあれば、教えてください。
厚かましい申し出ですみません。

回答No.4

178-tall

参照 URL のたぐい？

参考URL：

http://www.hiramine.com/programming/graphics/2d_ispointinpolygon.html

回答No.2

178-tall

ANo.1 の錯誤訂正。

[例] P1(x1, y1) → P2(x2, y2) 間を結ぶ「赤い線分」の下端座標 (x6, y6) ？

P1 → P2 間を結ぶ直線の方程式は？
y = ax+b として、
　y1 = ax1 + b
　y2 = ax2 + b
a, b について解くと、
　a = (y2-y1)/(x2-x1)
　b = (x1y2-x2y1)/(x2-x1)

この算式を使い、
　y6 = ax6 + b
が求まる。

回答No.1

178-tall

[例] P1(x1, y1) → P2(x2, y2) 間を結ぶ「赤い線分」の下端座標 (x6, y6) ？

「赤い線分」の方程式は？
y = ax+b として、
　y1 = ax1 + b
　y2 = ax2 + b
a, b について解くと、
　a = (y2-y1)/(x2-x1)
　b = (x1y2-x2y1)/(x2-x1)

この算式を使い、
　y6 = ax6 + b
が求まる。

補足

早速の回答ありがとうございます。
私の質問方法がマズかったのかと思います。
こちらの回答ですと、x1≦x6≦x2 の場合ですよね。
x2≦x6≦x4 だと、p6(x6, y6) を通りy軸に平行な直線と P2(x2, y2) と P3(x3, y3) を結ぶ直線の交点を求めなければなりません。
Pn(xn, yn) は変数で与えられますので、数学的な一般解は求められないように思います。
私の質問を言い換えますと「それぞれの点において、その点を通るy軸に平行な直線と交わるのは、どの2点を結んだ直線か？」このアルゴリズムを知りたいのです。