では、ポリゴンを詳しく見てみましょう。
私たちは彼をテッドと呼びます。テッド（または一般的に多角形）が点を見ると、彼はそれを自分の中に同化させようとします。そして同化のために、彼は彼の多くの側面の1つに手を差し伸べてポイントをつかむという名誉を与えることにしました. 現在、テッドはもっと重要なことで忙しいので、両陣営はどちらが善行を行うかを決める必要があります。もう一度言います。側面。
ほら、テッドの近くにポイントがあり、すぐにそれが悪意を持って消費されることに幸いなことに気づいていません. では、テッドの陣営は、どちらがポイントを獲得するかをどのように決定するのでしょうか? まあ、それは公正なゲームである必要があります。そこから点までの垂直距離が最短だと感じた側がやります。最短。垂直。距離。
同化完了！
心に留めておくべきもう 1 つのことは、Ted のようなポリゴンは同化よりも生存を重視するということです。点からの垂直距離が最も短い側は、他の側を通り抜けない場合にのみ同化を開始します。したがって、同化が有効な陣営のみが考慮されます。そうしないと、悪いことが起こります。
私の不必要な演説には、2 つの重要なポイントがあります。
- ポイントを追加する側は、ポイントからの垂直距離が最短である必要があります。
- ポイントからの垂直距離が最短であることは別として、この側へのポイントの追加は有効である必要があります。これは重要です。結局のところ、ポリゴンの大量殺人を犯したくありません。
それで、ここにいくつかの疑似コードがあります。
For each side S in polygon P
Do
d := perpendicularDistanceFromSide(S, point);
If d is less than shortestPerpendicularDistance
Do
If additionIsValid(S, point, P)
Do
shortestPerpendicularDistance := d;
index = S.index;
End If
End If
End For
側面からの垂直距離を見つけるのは簡単です。
var perpendicularDistance = function(side, point) {
//Find direction vector of side
var dir = {x: side.p2.x - side.p1.x, y: side.p2.y - side.p1.y};
var m = Math.sqrt(dir.x*dir.x + dir.y*dir.y);
if(m !== 0) {
d.x = d.x/m;
d.y = d.y/m;
}
//Find position vector of point, from side
var pVec = {x: point.x - side.p1.x, y: point.y - side.p1.y};
//Absolut of cross product of dir and pVec.
//It's essentially |pVec|*Sin(q), q is the angle between
//dir and pVec.
return Math.abs(dir.x*pVec.y - dir.y*pVec.x);
};
では、妥当性を見てみましょう。多角形にポイントを追加した後、新しい辺が他の辺のいずれかを通過した場合、小さな男は終わりです。アルゴリズムがこれを考慮していることを確認する必要があります。
これには 2 つのバージョンを考えました。安いものと高いもの。
方法 1 :
ポリゴンに凹みがほとんどまたはまったくない場合、この方法は完全に機能します。このメソッドは、新しい辺が古い辺に隣接する辺と交差しないことのみをチェックします。
側があるとしましょうS。隣接する 2 つの辺はSprevとSnextです。2 つの新しい面はS1pとS2pです。S1pと共通Sprev点があります。と共通点があります。S.p1S2pSnextS.p2
この方法によれば、追加は次の間に交差がない場合にのみ有効です。
したがって、この方法は拒否に対して機能します。交点が見つからない場合、側Sは有効にポイントを追加できます。
方法 1 のデモ
方法 2 :
方法 1 は、多角形の凹みが大きくなると失敗します。そのため、ポイントの追加が有効であることを確認するために、さらにチェックを行う必要があります。
この方法は実際には方法 1 の拡張です。ペアSprevとS2p、およびSnextがS1p交差していないことを確認した後、新しい辺が多角形の他のすべての辺と交差しているかどうかを確認します (もちろんSprevとは別Snextとして)。
すべての側面がチェックされた後、追加が拒否されない場合、この追加が有効であると完全に確信しています。
問題は、拒否は十分に迅速に行われますが、受け入れられるまでには長い時間がかかり、この方法は非常に高価になることです。
さらに、複雑さは多角形の辺の数に依存します。ポリゴンの複雑さが増すにつれて、有効性の確認に時間がかかります。
方法 2 デモ
線分の交差をチェックするために使用したアルゴリズムは、2 つの線分が交差する場所をどのように検出しますか? . それは完全に素晴らしいです。
そして、それは私が持っているすべてです。これはそれを行う1つの方法です、私は言わなければなりません。まだ私を驚かせていない別のより良い方法があるかもしれません。テッドをひどく気にかけなかったことを願っています。また、良い質問をしてくれてありがとう、楽しかったです。