C++の凸多角形

順番に結合したときにポリゴンを形成するポイントのリストがあるとすると、このポリゴンが凸面であるかどうかを確認する必要があります（凸多角形の定義）。少なくとも3つ、最大で10,000ポイントあることに注意する必要があります。また、座標は-10,000〜10,000の範囲です。

与えられた点によって形成されるポリゴンは常に単純なポリゴンであると想定できます。つまり、各頂点で正確に2つのエッジが交差し、それ以外の場合はエッジが互いに交差しないようにします。したがって、入力が[[0,0]、[0,1]、[1,1]、[1,0]]の場合、凸型であるため、戻り値はtrueになります。

これを解決するには、次の手順に従います-

• メソッドcalc（）を定義します。これは、ax、ay、bx、by、cx、cyを取ります。これは、次のように機能します-

• BAx：=ax – bx、BAy：=ay – by、BCx：=cx – bx、BCy：=cy-by

• メインの方法から次のようにします

• neg：=falseおよびpos：=false、n：=ポイント配列のサイズ

• 0からn–1の範囲のiの場合

  • a：=i、b：=（i + 1）mod nおよびc：=（i + 2）mod n

  • cross_prod：=calc（p [a、0]、p [a、1]、p [b、0]、p [b、1]、p [c、0]、p [c、1]）

    >

  • cross_prod <0の場合、neg：=true、それ以外の場合、cross_prod> 0の場合、pos：=true

  • negおよびposがtrueの場合、falseを返します

• trueを返す

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool isConvex(vector<vector<int>>& points) {
      bool neg = false;
      bool pos = false;
      int n = points.size();
      for(int i = 0; i < n; i++){
         int a = i;
         int b = (i + 1) % n;
         int c = (i + 2) % n;
         int crossProduct = calc(points[a][0], points[a][1], points[b][0], points[b][1], points[c][0], points[c][1]);
         if(crossProduct < 0) neg = true;
         else if(crossProduct > 0) pos = true;
         if(neg && pos) return false;
      }
      return true;
   }
   int calc(int ax, int ay, int bx, int by, int cx, int cy){
      int BAx = ax - bx;
      int BAy = ay - by;
      int BCx = cx - bx;
      int BCy = cy - by;
      return (BAx * BCy - BAy * BCx);
   }
};
main(){
   vector<vector<int>> v = {{0,0},{0,1},{1,1},{1,0}};
   Solution ob;
   cout << (ob.isConvex(v));
}

入力

[[0,0],[0,1],[1,1],[1,0]]

出力

1