我有一个四边形类型，定义为：
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 内绘制的四边形。
如果这样做的唯一原因是绘制生成的多边形，为什么不使用 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
嘿 presto，交叉多边形！
如果您将自己限制在 OpenGL 4 并使用各种可用的着色器，您可能会提高效率。
不是一个完整的实现，但是：
编写一个例程找到两条线段的交点，intersect_segment
bool segments_intersect(
point_t a0, point_t a1,
point_t b0, point_t b1,
/*out*/ point_t* intersection
)
在 quad 例程中写一个点，point_in_quad
bool point_in_quad(point_t p, quad_t q)
应用于segments_intersect每对分段，其中第一个在红色四边形中，第二个在紫色中（总共 16 次测试）
point_t temp;
if(segments_intersect(red.p1, red.p2, purple.p1, purple.p2, &temp)))
found_point(temp);
if(segments_intersect(red.p1, red.p2, purple.p2, purple.p3, &temp))
found_point(temp);
if(segments_intersect(red.p1, red.p2, purple.p3, purple.p4, &temp))
found_point(temp);
//10 more
if(segments_intersect(red.p4, red.p1, purple.p2, purple.p3, &temp))
found_point(temp);
if(segments_intersect(red.p4, red.p1, purple.p3, purple.p4, &temp))
found_point(temp);
if(segments_intersect(red.p4, red.p1, purple.p4, purple.p1, &temp))
found_point(temp);
应用于point_in_quad测试紫色四边形的红色四边形中的每个点：
if(point_in_quad(red.p1, purple)) found_point(red.p1);
if(point_in_quad(red.p2, purple)) found_point(red.p2);
if(point_in_quad(red.p3, purple)) found_point(red.p3);
if(point_in_quad(red.p4, purple)) found_point(red.p4);
应用于point_in_quad测试红色四边形的紫色四边形中的每个点：
if(point_in_quad(purple.p1, red)) found_point(purple.p1);
if(point_in_quad(purple.p2, red)) found_point(purple.p2);
if(point_in_quad(purple.p3, red)) found_point(purple.p3);
if(point_in_quad(purple.p4, red)) found_point(purple.p4);
如果它们是凸的，那么我相信任何相交都会产生一个最多有八个顶点的多边形。如果它们可能不是凸的，则最终可以得到两个分离的多边形作为交集。
假设是凸的，我相信（但尚未验证）结果中的顶点集将是线交点集加上包含在另一个输入四边形中的任一输入四边形的顶点集。然后，交点将成为这些顶点的（凸）外壳。
在这一点上，这只是有效地获得这些集合的问题。