0

いくつかの水平線分が与えられた場合、すべての水平線分と交差する垂直線を見つけたいと思います。アルゴリズムは、そのような行が存在しない場合に報告することになっています。また、複数の垂直線の場合、すべての水平線分の境界ボックスの中心から最も離れていない線を見つけることが望ましいです。

組み合わせ幾何学にはこの種の何かがあると確信していますが、私は見つけることができません。誰かが私たちがそれをどのように行うことができるかについて私にいくつかのアイデアを教えてもらえますか？

前もって感謝します。

4

1 に答える 1

3

すべての線分をループして、次の値を見つけます。

minxstart - smallest x value of all of the left end of your horizontal segments
maxxstart - largest x value of all of the left ends of your horizontal segments
minxend - smallest x value of the right end of your horizontal segments
maxxend - largest x value of the right end of your horizontal segments
miny - smallest y value of horizontal segments
maxy - largest y value of horizontal segments

minxend <maxxstartの場合、これらの値を含む両方の行にヒットする方法がないため、行は存在しません。

バウンディングボックスの中心を見つけます。

centerx = (minxstart + maxxend) / 2

垂直線分のx値は、maxxstartとminxendの間にある必要があります。centerxに最も近い値を選択し、このnewxと呼びます。

垂直線分は（newx、ymin）から（newx、ymax）になります。

于 2012-09-09T15:38:25.080 に答える