Đa giác lồi trong C ++

Giả sử chúng ta có một danh sách các điểm tạo thành một đa giác khi nối một cách tuần tự, chúng ta phải tìm xem đa giác này có phải là lồi hay không (Định nghĩa đa giác lồi). Chúng ta phải ghi nhớ rằng có ít nhất 3 và nhiều nhất là 10.000 điểm. Và tọa độ nằm trong khoảng -10.000 đến 10.000.

Chúng ta có thể giả sử đa giác được tạo thành bởi các điểm đã cho luôn là một đa giác đơn giản, nói cách khác, chúng ta đảm bảo rằng có chính xác hai cạnh cắt nhau tại mỗi đỉnh và các cạnh đó không cắt nhau. Vì vậy, nếu đầu vào là:[[0,0], [0,1], [1,1], [1,0]] thì nó là lồi, vì vậy giá trị trả về sẽ là true.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định phương thức calc (), phương thức này sẽ nhận ax, ay, bx, by, cx, cy, phương thức này sẽ hoạt động như sau -

• BAx:=ax - bx, BAy:=ay - by, BCx:=cx - bx, BCy:=cy - by

• Từ phương thức chính, hãy làm như sau

• neg:=false và pos:=false, n:=kích thước của mảng điểm

• cho tôi trong phạm vi từ 0 đến n - 1

  • a:=i, b:=(i + 1) mod n và 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])

  • nếu cross_prod <0 thì neg:=true, ngược lại khi cross_prod> 0 thì pos:=true

  • nếu neg và pos là true, thì trả về false

• trả về true

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

1