1.4 实现的问题
(Implementation Issues)

本章剩余部分将用相当长的篇幅来讨论实现问题。我们的目标是，实现计算三角分割的代码。这关键在于检测两条线段的交点，这是一个看似简单的任务，但实现起来却常常出错。我们将使用1.3节中计算面积的方法来处理线段交点问题。首先，我们讨论一些表示问题。

1.4.1 点的实现(Representation of a Point)

数组 V.S. 结构体(Arrays versus Records)

所有点都将通过一定长度的数组来表示，也就是所谓的坐标。通常做法是用包含名为 \(x\) 和 \(y\) 字段的结构体来表示一个点，但这会阻止使用 for 循环来遍历这些坐标。似乎没必要为了仅遍历两个索引而写一个 for 循环，但我发现这样更容易理解，而且这种方法显然更容易推广到更高维度。

整数 V.S. 浮点数(Integers versus Reals)

可能得话，我们会尽量使用整数来表示点坐标，而不是使用浮点数。这样我们能避免浮点数的舍入误差问题，使得我们编写的代码可以在一定坐标范围内验证正确(verifiably correct)。数值误差是一个重要的主题，在本书的各个部分都会讨论(例如，4.3.5节和 7.2节)。显然，在一些情况下我们必须使用浮点数，比如计算两条线段的交点，此时我们会放宽数据类型的使用限制。我们将集中管理类型定义，以便在处理不同类型的坐标数据时，只需修改代码一处代码。

点类型定义(Point Type Definition)

所有类型定义都将以小写字母 t 开头。所有常量定义将全部以大写字母表示。后缀 i 和 d 分别表示 integer 类型和 double 类型。参见 Code 1.1。在数学表达式中，我们将用 \(p_0\) 和 \(p_1\) 表示 p[0] 和 p[1]。

展开 Code 1.1 Point type.>>>

        #define X 0
        #define Y 1
        typedef enum { FALSE, TRUE } bool;
        #define DIM 2            /* Dimension of points */
        typedef int tPointi[DIM] /* Type integer point  */

1.4.2 多边形的实现(Representation of a Polygon)

这里的主要决策是，使用数组还是链表。如果是链表，还需要选择单向链表还是双向链表，以及是线性链表还是循环链表。

使用数组会让代码更清晰。与列表相比，使用数组时循环结构和索引递增的逻辑要清楚一些。然而，数组在插入和删除点时很麻烦。由于我们开发的三角分割代码存在剪掉“耳朵”的操作，所以将牺牲简单性以便更容易地进行删除。除此之外，我们第3章和第4章的凸包(convex hull)代码中也要使用相同的结构，因此这里的投入将在以后得到回报。考虑到这种通用性，我们选择使用双向循环链表来表示多边形。数据结构的基本单元表示一个顶点，即 tVertexStructure，其主要数据字段为 tPoint。其中指针 next 和 prev 指向其相邻的两个顶点。参见 Code 1.2。整数索引 vnum 主要用于打印输出，其他字段(例如 bool ear)将在必要时添加。

展开 Code 1.2 Vertex structure.>>>

        typedef struct tVertexStructure tsVertex /* Used only in NEW()*/ 
        typedef tsVertex *tVertex;
        struct tVertexStructure {
            int vnum;  /* Index */
            tPointi v; /* Coordinates */
            bool ear;  /* TRUE iff an ear */
            tVertex next, prev;
        };
        tVertex vertices = NULL; /* "Head" of circular list. */

在任何时候，都要维护一个全局变量 vertices，它指向某个顶点，将在迭代处理过程中被当做表头。代码 1.3 中给出了一种循环遍历所有顶点的形式。如果需要在循环中删除 vertex 所指向的顶点，需要小心操作。

展开 Code 1.3 Loop to process all vertices.>>>

        tVertex v;
        v = vertices;
        do {
            /* Process vertex v */
            v = v->next;
        } while(v != vertices);

我们还需要两个基础的链表接口，一个用于分配新元素(NEW)，另一个用于将新元素添加到链表中(ADD)。考虑到后面的章节可能会用，我们将这些接口写成宏的形式，其中 NEW 有一个参数 type 表示数据类型。这样，这些接口就可以用于不同的类型。(在 C 语言中，不允许无视变量类型的操作存在，但宏是基于文本的，它不关心类型)。参见 Code 1.4。 ADD 首先检查指针 head 是否非空，若是，则将新的单元插到 head 之前。若否，则把 head 指向添加的节点，它将是列表中唯一的节点。一系列 ADD 操作之后的效果是，会将第 n 个点添加到第 0 个点(head)之前，第(n-1)个点之后。

展开 Code 1.4 NEW and ADD macros. FREE is used in Chapter3 and 4.>>>

        #define EXIT_FAILURE 1
        char * malloc();

        #define NEW(p, type)                               \
            if ((p=(type*)malloc(sizeof(type))) == NULL) { \
                printf("NEW: Out of Memory!\n");           \
                exit(EXIT_FAILURE);                        \
            }

        #define ADD(head, p)                 \
            if (head) {                      \
                p->next = head;              \
                p->prev = head->prev;        \
                head-prev = p;               \
                p->prev->next = p;           \
            } else {                         \
                head = p;                    \
                head->next = head->prev = p; \
            }

        #define FREE(p) if (p) { free((char*)p); p = NULL; }

1.4.3 计算面积(Code for Area)

现在我们可以直接通过实现公式(1.9) 或 (1.10) 来计算多边形的面积。 Code 1.5 给出了公式1.9的实现，其中 \(p = v_0\)，代码中采用了上一节中建立的数据结构和约定。

展开 Code 1.5 Area2 and AreaPoly2.>>>

        int Area2(tPointi a, tPointi b, tPointi c)
        {
            return (b[X] - a[X]) * (c[Y] - a[Y]) - (c[X] - a[X]) * (b[Y] - a[Y]);
        }

        int AreaPoly2(void)
        {
            int sum = 0;
            tVertex p, a;

            p = vertices; /* Fixed  */
            a = p->next;  /* Moving */

            do {
                sum += Area2(p->v, a->v, a->next->v);
                a = a->next;
            } while (a->Next != vertices);
            return sum;
        }

函数 Area2 有一个有趣的问题。如果坐标值很大，那么坐标的乘法可能会导致整数溢出，不幸的是，大多数 C 语言的实现通常不会报告这种情况。这里，我们采用公式 (1.3) 替代而不是公式 (1.2)。因为前者使用的乘法更少，并且是对坐标差进行相乘。然而，这个问题仍然存在，我们将在4.3.5节中再次讨论它。参见练习 1.6.4[1]。