0

総数を見つけたいです。2Dデカルト平面の3つの頂点すべてのx座標とy座標が与えられた場合、三角形の内側と境界上にある点の数。三角形を長方形で囲み、直線方程式を見つけて、不等式を満たすために点を1つずつチェックすることを考えています。この問題を解決するためのより良い計算アプローチはありますか？

私を助けてください。

4

2 に答える 2

1

3 三角形エッジ ベクトルのすべての組み合わせの外積を取ります。結果として得られるベクトルの方向が、点 p へのベクトルと三角形の点 (A、B、または C) のいずれかへのベクトルの外積の結果と同じでない場合、p は三角形に含まれません。 3D になります)

より詳細な説明: http://www.blackpawn.com/texts/pointinpoly/default.html

于 2012-08-16T05:29:26.457 に答える
0

ポイントがポリゴン内にあるかどうかをテストする一般的なケースの概要については、http: //community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry3のPointInPolygonの説明を参照してください。常に凸である三角形があるため、これは (疑似コード) に単純化されます。

for point in test_points:
  //infinity can just be a point outside the bounding box of the triangle
  ray := line from point to infinity 
  intersection_points := 0

  for side in triangle_sides
    isect := intersection ray, side
    intersection_points++ if isect

  return intersection_points %2 == 1
于 2012-08-16T05:40:22.687 に答える