Javaで不連続な点を回転させずに回転させる

Question

GenerateSolidThetaZero関数を使用して整数成分のみを持つ点のリストを生成しています。私の目標は、これらの離散点をラジアン単位の角度θを使って回転させ、回転後の新しい点に整数成分が残るようにすることです。問題は、2点を同じ値にマッピングしたくないということです。私は回転の前後に同じ数のユニークな点が必要です。この問題を少しでも解決するためにラウンド関数を使用しましたが、私はまだ一意でないマッピングを取得します。基本的には、これらのポイントを回転させ、可能な限り最小限のポイントを失うように、できるだけ多くの構造を保持する方法を探したいだけです。私は任意のライブラリを使用して喜んでです。どんな助けや指導も素晴らしいでしょう。

注：私のコードでは、半径は2で、13ポイントが生成されます。 Pi/6の回転後、同じ値にマッピングされた点のために4点が失われ、もう1点は既にマップされています。

public class pointcheck{ 
     // this HashSet will be used to check if a point is already in the rotated list 
     public static HashSet<Point> pointSet = new HashSet<Point>(); 

     public static void main(String args[]) { 
      //generates sort of circular solid with param being the radius 
      ArrayList<Point> solid_pointList = GenerateSolidThetaZero(2); 

      //used to store original point as first part of pair and rotated point as second part of pair 
      ArrayList<Pair> point_pair = new ArrayList<Pair>(); 

      //goes through all points in Solid_pointList adds each point to Point List with its corresponding rotated angle 
      for(Point t : solid_pointList){ 
       point_pair.add(new Pair(t,rotation_about_origin(t,Math.PI/6))); 
      } 

      for(Pair t : point_pair){ 
       System.out.println(t.getFirst() + " " + t.getSecond()); 
      } 

      System.out.println(pointSet.size()); 

     } 

     //takes the point we want to rotate and then the angle to rotate it by 
     public static Point rotation_about_origin(Point P, double theta){ 
      Point new_P = null; 
      double old_X = P.x; 
      double old_Y = P.y; 
      double cos_theta = Math.cos(theta); 
      double sin_theta = Math.sin(theta); 
      double new_X = old_X * cos_theta - old_Y * sin_theta; 
      double new_Y = old_X * sin_theta + old_Y * cos_theta; 

      new_P = new Point((int)Math.round(new_X),(int)Math.round(new_Y)); 

      //if new_p is already in rotated solid 
      if(pointSet.contains(new_P)) 
       System.out.println("Conflict  " + P + "   " + new_P); 
      else 
       //add new_P to pointSet so we know a point already rotated to that spot 
       pointSet.add(new_P); 
      return new_P; 
     } 


     private static ArrayList<Point> GenerateSolidThetaZero(int r){ 
      int rsq = r * r; 
      ArrayList<Point> solidList=new ArrayList<Point>(); 
      for (int x=-r;x<=r;x++) 
       for (int y=-r;y<=r;y++) 
        if (x*x + y*y <= rsq) 
         solidList.add(new Point(x,y)); 

      return solidList; 
     } 

    public static class Pair<F,S>{ 
     private F first; //first member of pair 
     private S second; //second member of pair 

     public Pair(F first, S second) { 
      this.first = first; 
      this.second = second; 
     } 

     public void setFirst(F first) { 
      this.first = first; 
     } 

     public void setSecond(S second) { 
      this.second = second; 
     } 

     public F getFirst() { 
      return first; 
     } 

     public S getSecond() { 
      return second; 
     } 
     } 
    }//end of pointcheck class 

90の整数倍を使用しない角度を使用してポイントを回転させるにはどうすればよいですか？マッピングが既に行われている場合は、回転後のポイントをどこで翻訳する必要がありますか？

Answer 1

回転したディスクは元のピクセルとまったく同じピクセルをカバーします。したがって、実際には、元のピクセルから回転ピクセルへの割り当て問題を解決したいと考えています。

元のピクセル(ox, oy)を対応するピクセル(cx, cy)に割り当てるコストは、潜在的に表現することができます。たとえば、距離：

E_o,c = length(R(ox, oy, theta) - (cx, cy)) 

ここで、Rはローテーション演算子です。あるいは、他の基準を試すこともできます。二次距離。

その後、問題は全体的なエネルギーを最小限に抑える対応を見つけることです：

min_C Sum_{o \in O} E_o,c 

これはまさにHungarian Algorithmで解くアルゴリズムを。しかし、ピクセル数が多い場合は非常に高価です。また、回転位置を記憶し、代わりに色のみを有することが、注目画素において

：

はその代わりに、ここでは近似の考え方です。その後、以前と同じように元のピクセルを順番に回転させます。回転した位置を丸め、対応するピクセルがまだ占有されているかどうかを確認します。

そうでない場合は、回転した（丸められていない）位置を新しい色とともに保存します。

もし占有されている場合は、対応を交換するとエネルギーが減少するかどうかを確認してください。そうであれば、スワップして元のピクセルにします。いずれにしても、マッピングされていない元のピクセルがあります。このピクセルをリストに格納します。

この手順を実行すると、部分一致マップとマップされていないピクセルの一覧が表示されます。マップされていないピクセルのいずれかを選択します。ターゲットピクセルの近傍を分析します。おそらく、私はそれについての証拠はありませんが、空のピクセルが常に存在します。もしそうなら、これを選択してください。そうでない場合は、隣接するすべてのピクセルを調べて、エネルギーの減少と交換を最適にします。リストが空になるまで続行します。

近似アルゴリズムは単なるアイデアであり、実際には動作するという証明はありません。しかし、それは試してみる価値があるかのように聞こえます。そしてそれは間違いなくハンガリーのアルゴリズムよりも速くなります。しかし、この近似は潜在的な定義に対してp> = 1のLpノルムでのみ機能します。