用于寻找两个2D四边形的交点的AC算法？

Question

我有一个quad类型,定义为:

typedef struct __point {
    float x;
    float y;
} point_t;

typedef struct __quad {
    point_t p1;
    point_t p2;
    point_t p3;
    point_t p4;
} quad_t;

如果我在同一平面上有两个这样的四边形,我希望能够计算出这些四边形的交点.例如,如果我们有四A和四B,如果B的任何一个点落在A之外,那么该算法应该产生一个带有点的四边形,如下图所示(A为红色,B为紫色):

编辑:点的排序并不重要,因为我稍后会使用这些点构建一个将在A中绘制的四边形.

Answer 1

如果这样做的唯一原因是绘制生成的多边形，为什么不使用 GPU 来为您完成这项工作 - 毕竟您正在使用 OpenGL。因此，不要费力去思考如何构建交叉路口，而是执行以下操作：-

Set Z values of Polygon A and Polygon B to some constant

Set Z test to no testing (always write Z regardless)

Disable Z test
Enable Z writes
Disable colour writes
Render Polygon A

Set Z test to z equal

Enable Z test
Disable Z write
Enable colour write
Render Polygon B

嘿，快点，交叉多边形！

如果您将自己限制在 OpenGL 4 上并使用各种可用的着色器，您可能会提高效率。