algorithm - 查找由矩形和直线形成的二维多边形的面积

Question

我正在使用 Unity 制作游戏。有一个被直线相交的矩形。我需要找到 rect 的哪一部分更大以及有多少。有谁知道算法如何做到这一点？

矩形和直线用点设置(矩形为 4 个，直线为 2 个)

Answer 1

直线的隐式方程为

S(x,y) = (x - x0) (y1 - y0) - (y - y0) (x1 - x0) = 0

当您插入一个角的坐标时，S(x, y) 的符号会告诉您您位于直线的哪一侧。更好的是，如果您计算两个角处的 Sa 和 Sb 并且它们具有不同的符号，则交点位于分数 Sa/(Sa - Sb) 沿着 ab 的方向。

现在，按顺时针顺序依次处理所有四个边。对于每条边，如果为正，则保留起始角，如果有交点，则保留交点。最后，您将获得 0 到 5 个点来定义正域中的凸多边形。

该区域由 shoelace 找到公式。