算法学习：计算几何找凸包及求点线面交点

你的名字 2021-09-30 09:48 358阅读 0赞

--------------------

**前置知识：**  
**计算几何基础**

--------------------

找**凸包**：

vector convex(vector l)
 {
 vector ans, s;
 P tmp(lim, lim);
 int pos = 0;
 for (int i = 0; i < l.size(); i++)
 if (l[i] < tmp)
 tmp = l[i], pos = i;
 for (int i = pos, cnt_ = 0; cnt_ < l.size(); cnt_++, i = (i + 1) % l.size())
 {
 while (s.size() >= 2 && sgn(cross(s[s.size() - 2], s[s.size() - 1], l[i])) <= 0)
 s.pop_back();
 s.push_back(l[i]);
 pos = i;
 }
 ans = s; s.clear();
 for (int i = pos, cnt_ = 0; cnt_ < l.size(); cnt_++, i = (i - 1) % l.size())
 {
 while (s.size() >= 2 && sgn(cross(s[s.size() - 2], s[s.size() - 1], l[i])) <= 0)
 s.pop_back();
 s.push_back(l[i]);
 pos = i;
 }
 for (int i = 1; i + 1 < s.size(); i++)
 ans.push_back(s[i]);
 return ans;
 }

找凸包

--------------------

求**点是否在多边形内**

通过计算点两边的边的个数是否相等，如果相等则说明点在多边形内

同时，计算点是否在直线上，查找点在直线上的情况

bool P_In_S(P a, vector b)
 {
 int cnt = b.size();
 int cnt_ = 0;
 b.push_back(b[0]);
 for (int i = 0; i < cnt; i++)
 {
 if (onL(a, L(b[i], b[i + 1]))) return true;
 int k = sgn(cross(a, b[i], b[i + 1]));
 int d1 = sgn(a.y - b[i].y),
 d2 = sgn(a.y - b[i + 1].y);
 if (k < 0 && d1 >= 0 && d2 < 0)cnt_++;
 if (k > 0 && d2 >= 0 && d1 < 0)cnt_--;
 }
 return cnt_ != 0;
 }

点是否在多边形内

求**两向量是否相交**

bool L_is_Inter(L a, L b)
 {
 int c1 = sgn(cross(a.s, a.t, b.s)),
 c2 = sgn(cross(a.s, a.t, b.t)),
 c3 = sgn(cross(b.s, b.t, a.s)),
 c4 = sgn(cross(b.s, b.t, a.t));
 if (c1*c2 < 0 && c3*c4 < 0)return true;
 if (!c1 && onL(b.s, a))return true;
 if (!c2 && onL(b.t, a))return true;
 if (!c3 && onL(a.s, a))return true;
 if (!c4 && onL(a.t, a))return true;
 return false;
 }

两线段是否相交

--------------------

通过以上两个知识点：

能够求**两个多边形是否相交**

bool IF_inter(vector a, vector b) { //printf("1\n");
 for (int i = 0; i < a.size(); i++) if (P_In_S(a[i], b)) return true; //printf("2\n");
 for (int i = 0; i < b.size(); i++) if (P_In_S(b[i], a)) return true; int cnt1 = a.size(), cnt2 = b.size(); a.push_back(a[0]), b.push_back(b[0]); //printf("3\n");
 for (int i = 0; i < cnt1; i++) for (int j = 0; j < cnt2; j++) if (L_is_Inter(L(a[i], a[i + 1]), L(b[j], b[j + 1]))) return true; return false; }

两多边形是否相交