現在、Convex HUll と連携して Graham's Scan に取り組んでいます。私は学生なので、自分でやろうとしていますが、答えを見つけるために複数のサイトをふるいにかけています。要するに、ファイルから 1 つとランダムに生成された 1 つのコンストラクターが動作しているので、ポイントの配列を作成できます。次のステップは、極角でソートするクイックソートを実装することです。これは、比較クラスを介して行われます。比較クラスは私が立ち往生しているところです。角度の比較を行うためにドット比較とクロス比較を使用するように言われていますが、かなり迷っています。
/**
* Use cross product and dot product to implement this method. Do not take square roots
* or use trigonometric functions. See the PowerPoint notes on how to carry out cross and
* dot products.
*
* Call comparePolarAngle() and compareDistance().
*
* @param p1
* @param p2
* @return -1 if one of the following three conditions holds:
* a) p1 and referencePoint are the same point but p2 is a different point;
* b) neither p1 nor p2 equals referencePoint, and the polar angle of
* p1 with respect to referencePoint is less than that of p2;
* c) neither p1 nor p2 equals referencePoint, p1 and p2 have the same polar
* angle w.r.t. referencePoint, and p1 is closer to referencePoint than p2.
* 0 if p1 and p2 are the same point
* 1 if one of the following three conditions holds:
* a) p2 and referencePoint are the same point but p1 is a different point;
* b) neither p1 nor p2 equals referencePoint, and the polar angle of
* p1 with respect to referencePoint is greater than that of p2;
* c) neither p1 nor p2 equals referencePoint, p1 and p2 have the same polar
* angle w.r.t. referencePoint, and p1 is further to referencePoint than p2.
*
*/
public int compare(Point p1, Point p2){
if(p1 == referencePoint && p2 != referencePoint){
return -1;
} else if(p1 == p2){
return 0;
} else {
}
return 0;
}
/**
* Compare the polar angles of two points p1 and p2 with respect to referencePoint. Use
* cross products. Do not use trigonometric functions.
*
* Precondition: p1 and p2 are distinct points.
*
* @param p1
* @param p2
* @return -1 if p1 equals referencePoint or its polar angle with respect to referencePoint
* is less than that of p2.
* 0 if p1 and p2 have the same polar angle.
* 1 if p2 equals referencePoint or its polar angle with respect to referencePoint
* is less than that of p1.
*/
public int comparePolarAngle(Point p1, Point p2){
// TODO
return 0;
}
/**
* Compare the distances of two points p1 and p2 to referencePoint. Use dot products.
* Do not take square roots.
*
* @param p1
* @param p2
* @return -1 if p1 is closer to referencePoint
* 0 if p1 and p2 are equidistant to referencePoint
* 1 if p2 is closer to referencePoint
*/
public int compareDistance(Point p1, Point p2){
int distance = 0;
return distance;
}
それがすべてです。行き詰まる前に、比較メソッドでちょっとしたことをしました。
quickSort と partition メソッドは非常に標準的なものですが、これらを追加して、皆さんがすべてを幅広く見ることができるようにします。
/**
* Sort the array points[] in the increasing order of polar angle with respect to lowestPoint.
* Use quickSort. Construct an object of the pointComparator class with lowestPoint as the
* argument for point comparison.
*
* Ought to be private, but is made public for testing convenience.
*/
public void quickSort(){
// TODO
}
/**
* Operates on the subarray of points[] with indices between first and last.
*
* @param first starting index of the subarray
* @param last ending index of the subarray
*/
private void quickSortRec(int first, int last){
// TODO
}
/**
* Operates on the subarray of points[] with indices between first and last.
*
* @param first
* @param last
* @return
*/
private int partition(int first, int last){
// TODO
return 0;
}
クイックソートメソッドを実行する前に、基本的に Compare クラスを起動して実行する必要があることはわかっていますが、ドット/クロス比較の使用方法さえまったくわからないので、本当に迷っています。
誰かが喜んで助けてくれるなら、私はとても感謝しています！ご覧いただきありがとうございます。素晴らしい夜をお過ごしください。