寻找两个二维四边形交点的C算法？

Question

我将要翻译的内容如下：

我有一个四元组类型，它被定义为：

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内部的四边形。

- Kristina Brooks

---

你尝试过什么？ - Minion91

那么您想要找到重叠区域的顶点吗？点的顺序很重要吗？ - Eric

@DavidSchwartz说："那样做找不到图中的两个点。" - Eric

“我随后会用这些点来构建一个将要被绘制在A内部的四边形。”- 这句话是指要用这些点构建一个四边形。关于放置两个重叠的45度正方形的想法并未提及，因此无法确定其是否为正确解释。 - Eric

一个简单的多边形相交算法 - CAFxX

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并使用可用的各种着色器，那么您可能可以使其更加高效。

- Skizz

---

这个在OpenGL|es 1.1上能用吗？如果可以的话，那就太好了！ - Kristina Brooks

@TinaBrooks：我看不出为什么它不能在 ES 版本上运行。 - Skizz

Answer 2

这不是完整的实现，但是：

1. 编写一个例程来查找两条线段的交点，intersect_segment

   bool segments_intersect(
       point_t a0, point_t a1,
       point_t b0, b1，
       /*out*/ point_t* intersection
   )
   

2. 编写一个四边形中的点例程，point_in_quad

   bool point_in_quad(point_t p, quad_t q)
   

3. 将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);
   

4. 将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);
   

5. 将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);
   

- Eric

---

这不会非常低效吗？这段代码将运行很多次（基本上，对于每个层，可能会有很多层）。 - Kristina Brooks

@TinaBrooks：我很确定没有其他方法。 - Eric

注意：当输入的四边形是凹多边形时，此策略可能会失败。 - Thom Smith

@ThomSmith：这种策略只是生成了一个（无序）顶点列表。对于凹多边形情况，它仍然会这样做。但是假设在这种情况下的点对应于单个多边形已经变得无效。 - Eric

Answer 3

• 这些四边形是否保证不自相交？
• 这些四边形是否保证是凸的？

如果它们是凸的，那么我相信任何交集都会产生一个最多有八个顶点的单一多边形。如果它们可能不是凸的，则交集可能会分为两个分离的多边形。

假设是凸的，我相信（但尚未验证）结果中的顶点集将是线段交点集加上包含在另一个输入四边形中的任一输入四边形的顶点集。然后，交集将是这些顶点的（凸）包。

此时，只需要高效地获取这些集合即可。

- Thom Smith

---

是的，四边形是凸多边形。而且，它们不能自相交。 - Kristina Brooks

Answer 4

对于凸多边形，我建议：

1：使用分离轴方法检查交集（快速）

2：从O'Rourke书中的算法（提供C代码）中找到交集

- MBo