注意を喚起する目的で、変更箇所などを囲む用途を想定しています。
完成品は点の指示方向により外に凸・内に凸と、2種類の描画が可能ですが、
構想段階では時計回り・反時計回りに関らず、常に外側に凸の雲形を描画する予定でした。
この場合、円弧の中心点が多角形の領域内に含まれるかどうかを判定する必要があります。
そこで最初に利用しようと考えたのが、時計回り・反時計回りを判定する関数を使ったアルゴリズムで、
某資格試験の対策本に掲載されていたものです。
それによると、
3点P1・P2・P3がある。
P1-P2の角度より、P1-P3の角度の方が小さいとき、P1→P2→P3は時計回りである。
・・・だそうです。(下図)
角度を0〜2πの範囲に改めた上で、
P1-P3の角度が、(P1-P2の角度)〜(P1-P2の角度+π)の範囲にないとき、P1→P2→P3は時計回りである。
ArcTan2()の戻り値の範囲が、-π〜π であることを踏まえて、
3点の位置関係を判定する関数 IsClockwise() を書いてみました。
P1→P2→P3が時計回りのときTrueを返します。
TPointRec = record
x:double;
y:double;
end;
function IsClockwise(P1,P2,P3:TPointRec):Boolean;
var
Degrees:array [0..1] of double;
begin
Degrees[0] := ArcTan2(P1.y-P2.y,P1.x-P2.x);
if Degrees[0] < 0 then
Degrees[0] := Degrees[0] + 2 * Pi; //0〜2πの範囲に改める
Degrees[1] := ArcTan2(P1.y-P3.y,P1.x-P3.x);
if Degrees[1] < 0 then
Degrees[1] := Degrees[1] + 2 * Pi; //0〜2πの範囲に改める
if InRange(Degrees[1],Degrees[0],Degrees[0] + Pi) then
Result := False
else
Result := True;
end;
IsClockwise()関数は、3点が一直線上にあるケースを想定していません。
で、そのような場合を判定する IsSeries()関数 を用意しておきます。
3点が一直線上にある場合、Trueを返します。
function IsSeries(P1,P2,P3:TPointRec):Boolean;
var
Degrees:array [0..1] of double;
begin
Degrees[0] := Abs(ArcTan2(P1.y-P2.y,P1.x-P2.x));
Degrees[1] := Abs(ArcTan2(P1.y-P3.y,P1.x-P3.x));
if (Degrees[0] = Degrees[1]) or (Degrees[0] + Degrees[1] = Pi) then
Result := True
else
Result := False;
end;
次に、ある点が多角形の内部に含まれるか否かの判定ですが、ネタ本にはこうあります。
頂点P1、P2、P3、・・・、Pnで与えられるn角形と、点Qにおいて、
P1・P2・Q、P2・P3・Q、・・・、Pn・P1・Qの位置関係がすべて同じとき、
点Qはこの多角形の内部に存在する。
これをそのままコーディングしたのが、IsSurrounded()関数です。
判定対象の点Qが多角形内部に含まれる場合、Trueを返します。
引数Pは多角形の頂点座標を格納した配列で、
オープン配列の要請として添え字は 0 から始まっている必要があります。
(以前、別のプログラムで 1 から始まる配列を使い、
いきなりシステムをダウンさせた経験があります^_^;)
この関数を実際に使用するときは、Pの要素数が3未満の場合への対応を忘れないで下さい。
function IsSurrounded(var P:array of TPointRec;Q:TPointRec):Boolean;
var
Criterion:Boolean;
i:Integer;
begin
Result := False;
Criterion := IsClockwise(P[Length(P)-1],P[0],Q); //Pn・P1・Qの位置関係を基準にする
for i := 0 to Length(P)-2 do //P1・P2・Q、P2・P3・Q、・・・、Pn-1・Pn・Qまで調べる
begin
if IsSeries(P[i],P[i+1],Q) then //3点が一直線上にある場合は判断を保留
Continue;
if Criterion <> IsClockwise(P[i],P[i+1],Q) then //位置関係が基準と異なる場合、直ちにFalseを返す
Exit;
end;
Result := True; //ループを完遂できたらTrue
end;
下図の点Q1が典型です。
点Q2・Q3は、P4-P5との関係においてIsSurrounded()関数内で判断が保留されるケースですが、
他の辺との関係で、正しい判定ができることに注意してください。
