1

ポイントが三角形の内側にあるかどうかを確認するための非常に高速なJavaメソッドを追求しています。

Kasper Fauerby の論文で次の C++ コードを見つけました。

typedef unsigned int uint32;
#define in(a) ((uint32&) a)
bool checkPointInTriangle(const VECTOR& point, const VECTOR& pa,const VECTOR& pb, const VECTOR& pc) {
  VECTOR e10=pb-pa;
  VECTOR e20=pc-pa;

  float a = e10.dot(e10);
  float b = e10.dot(e20);
  float c = e20.dot(e20);
  float ac_bb=(a*c)-(b*b);
  VECTOR vp(point.x-pa.x, point.y-pa.y, point.z-pa.z);

  float d = vp.dot(e10);
  float e = vp.dot(e20);
  float x = (d*c)-(e*b);
  float y = (e*a)-(d*b);
  float z = x+y-ac_bb;
  return (( in(z)& ~(in(x)|in(y)) ) & 0x80000000);
}

このコード スニペットを Java に変換できるかどうか、もしそうなら、私の Java コードよりも優れているかどうか疑問に思っていました。

public class Util {
    public static boolean checkPointInTriangle(Vector p1, Vector p2, Vector p3, Vector point) {
        float angles = 0;

        Vector v1 = Vector.min(point, p1); v1.normalize();
        Vector v2 = Vector.min(point, p2); v2.normalize();
        Vector v3 = Vector.min(point, p3); v3.normalize();

        angles += Math.acos(Vector.dot(v1, v2));
        angles += Math.acos(Vector.dot(v2, v3));
        angles += Math.acos(Vector.dot(v3, v1));

        return (Math.abs(angles - 2*Math.PI) <= 0.005);
    }

    public static void main(String [] args) {
        Vector p1 = new Vector(4.5f, 0, 0);
        Vector p2 = new Vector(0, -9f, 0);
        Vector p3 = new Vector(0, 0, 4.5f);
        Vector point = new Vector(2, -4, 0.5f);

        System.out.println(checkPointInTriangle(p1, p2, p3, point));
    }
}

および Vector クラス:

public class Vector {
    public float x, y, z;

    public Vector(float x, float y, float z) {
        this.x = x; this.y = y; this.z = z;
    }

    public float length() {
        return (float) Math.sqrt(x*x + y*y + z*z);
    }

    public void normalize() {
        float l = length(); x /= l; y /= l; z /= l;
    }

    public static float dot(Vector one, Vector two) {
        return one.x*two.x + one.y*two.y + one.z*two.z;
    }

    public static Vector min(Vector one, Vector two) {
        return new Vector(one.x-two.x, one.y-two.y, one.z-two.z);
    }
}

またはJava用のさらに高速な方法はありますか?

前もって感謝します！

4

1 に答える 1

1

あなたが見つけたコードが正しければ、あなたが持っているものよりもかなり速いはずです。リターンステートメント

return (( in(z)& ~(in(x)|in(y)) ) & 0x80000000);

浮動小数点数の符号ビットをチェックするトリッキーな方法です。私が完全に間違っていなければ、次と同等です：

return z < 0 && x >= 0 && y >= 0;

論文のテキストはこれを確認する必要があります。残りはあなたが自分自身を変換できると思います。

于 2013-10-10T12:28:52.303 に答える