计算几何~三角形面积、点在三角形内、线段相交代码笔记

多边形面积的基本公式：

鞋带公式 。强调多边形点集是按顺序存储；

三角形面积基本公式：

海伦公式；

向量叉积公式；

拓扑关系判断：

判断点是否在三角形内；

判断两条线段是否相交；

代码笔记：

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

struct Point2D {
	double x;
	double y;
	Point2D(double x, double y) : x(x), y(y) {}
	bool operator ==(const Point2D& p) {
		if (x == p.x && y == p.y) return true;
		return false;
	}
};

// 鞋带公式  注意多边形点集是按顺序存储
double computeArea(const std::vector<Point2D> &points)
{
	int n = points.size();
	double area = 0.00;
	for (int i = 0; i < n; ++i) {
		int j = (i + 1) % n;
		area += (points[i].x * points[j].y - points[j].x * points[i].y);
	}
	return abs(area * 0.5);
}

double distance2(const Point2D& p1, const Point2D& p2)
{
	double dx = p1.x - p2.x;
	double dy = p1.y - p2.y;
	return std::sqrt(dx*dx + dy*dy);
}

// 三角形海伦公式
double computeTriangleArea(const std::vector<Point2D> &points)
{
	int n = points.size();
	if (n != 3) { return 0.0; }
	double a = distance2(points[0], points[1]);
	double b = distance2(points[1], points[2]);
	double c = distance2(points[0], points[2]);
	double s = (a + b + c)* 0.5;
	return sqrt(s *(s - a) * (s - b) * (s - c));
}

// 三角形面积 S = 0.5*|(x2-x1)(y3-y1)-(x3-x1)(y2-y1)|
double computeTriangleArea2(const std::vector<Point2D> &points)
{
	int n = points.size();
	if (n != 3) { return 0.0; }
	return 0.5 * abs((points[1].x - points[0].x) * (points[2].y - points[0].y) - (points[2].x - points[0].x) * (points[1].y - points[0].y));
}

// 判断点是否在三角形内:1.面积法；2.同向法（向量叉乘符号相同);3.射线法；4.重心坐标法(a+b+c=1)
double crossProduct(const Point2D& o,const Point2D& p1, const Point2D& p2)
{
	return (p1.x-o.x) * (p2.y-o.y) - (p1.y-o.y) * (p2.x-o.x);
}

bool point2DInTriangle(const Point2D& p, const Point2D& a, const Point2D& b, const Point2D& c)
{
	double crossAB_AP = crossProduct(a,b,p);
	double crossBC_BP = crossProduct(b,c,p);
	double crossCA_CP = crossProduct(c,a,p);
	return (crossAB_AP >= 0 && crossBC_BP >= 0 && crossCA_CP >= 0) ||
		(crossAB_AP <= 0 && crossBC_BP <= 0 && crossCA_CP <= 0);
}

// 判断两条线段AB与CD是否相交
bool segmentIntersect(const Point2D& a, const Point2D& b, const Point2D& c, const Point2D& d)
{
	double crossAB_AC = crossProduct(a, b, c);
	double crossAB_AD = crossProduct(a, b, d);
	double crossCD_CA = crossProduct(c, d, a);
	double crossCD_CB = crossProduct(c, d, b);
	return (crossAB_AC * crossAB_AD <= 0) && (crossCD_CA * crossCD_CB <= 0);
}