ポリゴンポイントのリストが時計回りに並んでいるかどうかを判断する方法

1. 概要

ポリゴンポイントのリストを時計回りに並べるか反時計回りに並べるかを決定するには、いくつかの方法があります。

このチュートリアルでは、ポリゴンポイントの方向を決定するための簡単なアルゴリズムを作成します。さらに、面積の計算にいくつかの式を修正して使用します。ポリゴンの基本的な知識があることを前提とし、線形代数の基本的な定義も使用します。

ポリゴンがメモリに保存される方法を思い出してみましょう。がポリゴンであると仮定します。ポイントで構成されています。したがって、は、として表すことができます。ここで、です。したがって、の形状は点のリストとして表されます。

別のポリゴンも定義します。逆の順序で同じポイントで構成されていることに注意することが重要です。とは2つの異なるポリゴンであり、外観はまったく同じで、形状と面積は同じです。

それらの間で異なるのは、それらのポイントの向きです。のポイントが時計回りに向いている場合、のポイントの向きは反時計回りになり、その逆も同様です。

ポイントの向きに関するこの情報は、チュートリアルでさらに使用します。さらに、前述のように、との面積は数値的には等しいが、面積の符号は異なる。

2Dポリゴン領域の計算には単純な線形時間アルゴリズムがあります。アルゴリズムは、面積の式を導入します。ポリゴン面積計算の重要な側面について簡単に説明し、ポイント方向アルゴリズムでこの式を使用します。

形状の面積は、正または負のいずれかになります。形状がポイントのリストとして表される場合、それはポイントの方向に依存します。三角形と多角形の面積を計算するための式を簡単に覚えておきましょう。

ここで、三角形が3つの点、、、およびで定義されていると仮定します。

この三角形の面積は、線形代数からの簡単な式で計算できます。

三角形をシフトして点をにすると、三角形の面積は変わりません。

ただし、面積計算の式は少し単純化されます。

これで、三角形の面積の式を使用してポリゴンの面積を計算できます。アプローチの考え方は単純です。それは分解技術を使用します。点の多角形を三角形に分解することができます。これを行うには、任意のポイント、通常はを選択します。

その後、三角形の面積を計算できます。ポイントのセットで表されたポリゴンがあると仮定します。ポイント、、を選択して三角形を形成し、、を使用します。次に、すべての面積を合計して、ポリゴン全体の面積を取得します。

ポリゴンの面積を計算する最後の式：

、ここで。

ポリゴンの面積は正または負のいずれかになり得ることを覚えておくことが重要です。それは、頂点の分解と順序のために選択されたポイントに依存します。

簡単なSignum関数を定義しましょう。パラメータとして任意の数値を取り、3つの値のみを返します。もしも、。もしも、。最後に、の場合、。 この関数は、数字の符号に関する情報を提供します。

次に、ポリゴンのポイントの向きを取得するためのアルゴリズムを紹介します。まず、上記の式で符号付き面積を計算し、数値を求めます。次に、を計算します。最後に、ゼロと比較します。の場合、ポイントは反時計回りに向けられます。

同様に、の場合、ポイントは時計回りになります。の場合は予想していません。これは、ポリゴンの面積が0であることを意味します。その場合、ポリゴンが正しく定義されていない可能性があります。

上記のアルゴリズムの時間計算量は、です。ここで、はポリゴンのポイント数です。面積の計算には線形時間がかかります。その後、そのエリアがポジティブかどうかを知るのに時間がかかります。したがって、最終的な複雑さはです。

スペースの複雑さはです。これは、エリアを格納するために必要な変数が1つだけだからです。

この記事では、線形時間でポリゴンポイントの方向を決定するのに役立つアルゴリズムを紹介しました。さらに、ポリゴンの面積を計算するための簡単なアプローチを思い出しました。ポイントの向きを決定するための他のいくつかのテクニックがあります。ただし、それらはすべてこの単純なアイデアに基づいています。