C ++を使用して、指定されたポイントから可能な四辺形の数を見つけます

四辺形は、ユークリッド平面幾何学で4つの頂点と4つのエッジを持つポリゴンを形成します。名前4-gonなど。四辺形の他の名前に含まれ、正方形、表示スタイルなどとしても知られています。

この記事では、与えられた点から可能な四辺形の数を見つけるためのアプローチを説明します。この問題では、デカルト平面に提供された4つの点（x、y）を使用して作成できる四辺形の数を調べる必要があります。だからここに与えられた問題の例があります-

Input : A( -2, 8 ), B( -2, 0 ), C( 6, -1 ), D( 0, 8 )
Output : 1
Explanation : One quadrilateral can be formed ( ABCD )

Input : A( 1, 8 ), B( 0, 1 ), C( 4, 0 ), D( 1, 2 )
Output : 3
Explanation : 3 quadrilaterals can be formed (ABCD), (ABDC) and (ADBC).

解決策を見つけるためのアプローチ

• 最初に、4つのポイントのうち3つが同一線上にあるかどうかを確認し、同一線上にある場合は、ポイントで四辺形を形成できません。 。

• その後、4点中2点が同じかどうかを確認し、同じ場合は四辺形を形成できません 。

• 次に、対角線が交差するかどうかを確認します。はいの場合、形成できる四辺形は1つだけです。 凸四角形と呼ばれます 。

交差点の総数=1

対角線が交差しない場合、凹四角形と呼ばれる3つの可能な四角形を形成できます。

交差点の総数=0

例

#include <iostream>
using namespace std;
struct Point{ // points
    int x;
    int y;
};
int check_orientation(Point i, Point j, Point k){
    int val = (j.y - i.y) * (k.x - j.x) - (j.x - i.x) * (k.y - j.y);
    if (val == 0)
       return 0;
    return (val > 0) ? 1 : 2;
}
// checking whether line segments intersect
bool check_Intersect(Point A, Point B, Point C, Point D){
    int o1 = check_orientation(A, B, C);
    int o2 = check_orientation(A, B, D);
    int o3 = check_orientation(C, D, A);
    int o4 = check_orientation(C, D, B);
    if (o1 != o2 && o3 != o4)
       return true;
    return false;
}
// checking whether 2 points are same
bool check_similar(Point A, Point B){
   // If found similiar then we are returning false that means no quad. can be formed
    if (A.x == B.x && A.y == B.y)
       return false;
   // returning true for not found similiar
    return true;
}
// Checking collinearity of three points
bool check_collinear(Point A, Point B, Point C){
    int x1 = A.x, y1 = A.y;
    int x2 = B.x, y2 = B.y;
    int x3 = C.x, y3 = C.y;
    if ((y3 - y2) * (x2 - x1) == (y2 - y1) * (x3 - x2))
       return false;
    else
       return true;
}
// main function
int main(){
   struct Point A,B,C,D;
   A.x = -2, A.y = 8;// A(-2, 8)
   B.x = -2, B.y = 0;// B(-2, 0)
   C.x = 6, C.y = -1;// C(6, -1)
   D.x = 0, D.y = 8;// D(0, 8)
   // Checking whether any 3 points are collinear
   bool flag = true;
   flag = flag & check_collinear(A, B, C);
   flag = flag & check_collinear(A, B, D);
   flag = flag & check_collinear(A, C, D);
   flag = flag & check_collinear(B, C, D);
   // If points found collinear
   if (flag == false){
       cout << "Number of quadrilaterals possible from the given points: 0";
       return 0;
   }
   // Checking if 2 points are same.
   bool same = true;
   same = same & check_similar(A, B);
   same = same & check_similar(A, C);
   same = same & check_similar(B, D);
   same = same & check_similar(C, D);
   same = same & check_similar(A, D);
   same = same & check_similar(B, C);
   // If similiar point exist
   if (same == false){
       cout << "Number of quadrilaterals possible from the given points: 0";
   return 0;
   }
   // checking whether diagonal intersect or not
    flag = true;
   if (check_Intersect(A, B, C, D))
       flag = false;
   if (check_Intersect(A, C, B, D))
       flag = false;
   if (check_Intersect(A, B, D, C))
       flag = false;
   if (flag == true)
       cout << "Number of quadrilaterals possible from the given points: 3";
   else
       cout << "Number of quadrilaterals possible from the given points: 1";
   return 0;
}

出力

Number of quadrilaterals possible from the given points : 1

上記のコードの説明

このコードは、次の手順で理解できます-

• 3つのポイントが同一線上にあるかどうかを確認し、同一線上にある場合は、クワッドの数を確認します。 ：0

• 2つのポイントが類似しているかどうかを確認し、類似している場合はクワッドの数を確認します。 ：0

• 線分が交差しているかどうかの確認：

  • はいの場合、クワッドの数。 ：1

  • いいえの場合、クワッドの数。 ：3

結論

この記事では、与えられた4つのポイントから形成できるすべての可能な四辺形を見つけることを解決しました。四辺形の数が共線性、交差、および方向にどのように依存するかを理解しています。同じためのC++プログラムも作成しており、このプログラムはC、Java、Pythonなどの他の言語で作成できます。