4

To check for ray-triangle collisions, we can first see if the ray collides with the triangle's plane. If it does, we then check if the intersection point is on the same side for all triangle sides. If true, this means that the point is inside the triangle. This procedure is analogous for rectangles and other convex figures.

This is a list of vertexes belonging to a rectangle (counter-clockwise ordered):

vertexes = [ll, lr, ur, ul]

and I want to generate a list with all its sides; that is, all adjacent pairs of vertexes:

vertexPairs = [(ll, lr), (lr, ur), (ur, ul), (ul, ll)]

(note that the last vertex, ul, also pairs with the first one, ll)

How can I lazily generate such a list for a generic convex geometric figure, assuming I have an ordered list of its vertexes?

The idea is to feed each of the pairs to a function, isInside, and check if all of its return values are the same. This is what I'm doing:

1.  vertexes = [<list of vertexes>]
2.  vertexPairs = ???
3.  results = map (\(v1, v2) -> isInside point v1 v2) vertexPairs
4.  allequal = all (== head results) (tail results)

Because Haskell is lazy, if a call to isInside returns a value that differs from the first call's return value, the call to all ends (line 4). Similarly, I wanted a way to generate the vertexPairs list in a lazy way.

As I was writing this question, I thought of a possible solution to generate the pairs:

vertexPairs = zip (vertexes) (tail vertexes ++ [head vertexes])
  1. Is this lazy? I would say so, as it doesn't use last or similar functions, but I'm still relatively new to Haskell.
  2. It also looks a bit ugly, thanks to the concatenation and single-element list. Is there a better way?
  3. As a related question, what should be the free-point notation for line 3?
4

2 に答える 2

4

tikhon はほとんどの質問に答えていますが、もう少しきれいに書きたい場合は、

vertexPairs v = zip v (tail $ cycle v)

zip引数の1つが「なくなる」とリストの生成が停止するため、これは機能します

于 2013-04-28T17:07:45.207 に答える
3

はい、リストを生成するこの方法は怠惰です。一般に、Haskell のリスト関数は遅延型です。

エラーになるもの (例: undefined) を最初のリストに含めることで、それが遅延しているかどうかを自分でテストできます。たとえば、

vertexes = [(0,0), (10,0), undefined, undefined]

次にvertexPairs、エラーが発生します（リスト全体を評価して印刷する必要があるため）。ただし、怠惰な場合head vertexPairsでも、正しいペアを提供する必要があります-そして、そうです!

あなたのコードは実際にはかなり見栄えが良いと思います。あなたtail vertexes ++ [head vertex]がしていることは非常に明確になります。はい、ここで使用するのは少し奇妙に見えます++が、理にかなっています。リストの末尾への追加はコストのかかる操作であるため、目立つ必要があります。そのコードを書くためのより良い方法は考えられません。マイナーなスタイルのヒントとして、括弧を削除できますvertexes:

vertexPairs = zip vertexes (tail vertexes ++ [head vertexes])

isInside point3. については、概念的には、各ペアに適用する必要があります。現在、のようなタイプがありPoint -> Point -> Boolます。最初の 2 つの引数をタプルとして受け取る関数を取得したいとします(Point, Point) -> Bool。この関数が呼び出されるuncurryのは、逆の変換 (タプルを期待する関数を複数のパラメーターの 1 つに変換すること) をカリー化と呼ぶためです。したがって、次のように 3. を書くことができます。

results = map (uncurry (isInside point)) vertexPairs
于 2013-04-28T16:59:46.727 に答える