3

私は次のコードを勉強しています。

boolean convex(double x1, double y1, double x2, double y2, 
       double x3, double y3)
{
if (area(x1, y1, x2, y2, x3, y3) < 0)
    return true;
else
    return false;
}


/* area:  determines area of triangle formed by three points
 */
double area(double x1, double y1, double x2, double y2,
    double x3, double y3)
{
double areaSum = 0;

areaSum += x1 * (y3 - y2);
areaSum += x2 * (y1 - y3);
areaSum += x3 * (y2 - y1);

/* for actual area, we need to multiple areaSum * 0.5, but we are
     * only interested in the sign of the area (+/-)
     */

return areaSum;
}

面積が負であるという概念がわかりません。面積は常に正であるべきではありませんか? ここでの用語の理解が不足している可能性があります。元の作者に連絡しようとしましたが、このコードは約 8 年前のものであり、元の作者に連絡する方法がありません。与えられた頂点 x2y2 が凸であるかどうかを判断するこの方法は、本当にモバイルのようです。私は本当にそれを理解したいです。このコードを理解するのに役立つ指示や参照は大歓迎です。

ソースコード: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applets/BruteForceEarCut.java

4

3 に答える 3

4

このアルゴリズムは、三角形の面積の 2 倍を計算できる非常に単純な式を使用します。

この式には 2 つの利点があります。

  • 分割は必要ありません
  • ポイントが反時計回りの順序である場合、負の領域を返します。

コード サンプルでは、​​面積の実際の値は問題ではなく、結果の符号のみが必要です。

この式は、3 つの点が同一線上にあるかどうかを確認するためにも使用できます。

この式の詳細については、次のサイトを参照してください: http://www.mathopenref.com/coordtrianglearea.html

于 2013-06-18T16:14:19.173 に答える
2

積分がどのように機能するか知っていますよね？積分を考える 1 つの方法は、積分曲線の下の領域の観点からです。厳密に正の関数の場合、その定義はうまく機能しますが、ある時点で関数が負になると、絶対値を取らなければならないので問題が発生しますよね?

実際には常にそうであるとは限りません。曲線を負のままにしておくと、状況によっては非常に便利な場合があります。前に述べたことを思い出してください:曲線の下の領域。負の無限大と関数の間のすべてのスペース。明らかに、それはばかげていますよね？これは、曲線の下の面積と x 軸の下の面積の差と考えるとよいでしょう。そうすれば、関数が正の場合、曲線はより多くの面積を獲得し、負の場合は x 軸よりも小さくなります。

同じことは、厳密な関数ではない平面図形にも当てはまります。これを実際に決定するには、エッジがフィギュアの周りを移動するときにエッジがどの方向に向かうかを定義する必要があります。曲線の右側のすべての領域が領域内にあり、左側のすべての領域が領域外になるように定義できます (または、逆に定義することもできますが、最初の方法を使用します)。

したがって、私たちの図には、そこから右にある平面の無限遠端までのすべての領域が含まれています。時計回りに囲まれた領域には、通常の内部が 2 回含まれています。反時計回りに囲まれた領域には、従来の内部がまったく含まれていません。したがって、面積は、私たちの地域と平面全体との差です。

これを凹面に適用するのは、凹面または凸面が実際に何を意味するかを理解していれば、かなり簡単です。与えられた三角形は、平面から領域を切り取っている場合は凹型であり、余分な領域を追加している場合は凸型です。これは、面積を決定するために行っていたのとまったく同じことです。したがって、正の面積は凸型の形状に対応し、負の面積は凹型の形状に対応します。

この概念モデルでは、他にも奇妙なことができます。たとえば、エッジの方向を逆にすることで、領域を「裏返し」にすることができます。

少しわかりにくかったら申し訳ありませんが、これが私がネガティブ領域を理解する実際の方法です。

于 2013-06-18T16:47:31.460 に答える