Что делает эта функция(вычислительная геометрия, Си)?

Question

[Clean Coder]

Здравствуйте. Здесь https://rosettacode.org/wiki/Sutherland-Hodgman_po... приведена программа для обрезания многоугольника(subject) прямоугольником(clipper). В ней полигон задан структурой:
typedef struct { int len, alloc; vec v; } poly_t, *poly;

Далее есть функция:
void poly_append(poly p, vec v)
{
if (p->len >= p->alloc) {
p->alloc *= 2;
if (!p->alloc) p->alloc = 4;
p->v = (vec)realloc(p->v, sizeof(vec_t) * p->alloc);
}
p->v[p->len++] = *v;
}

Насколько я понимаю, она нужна для добавления к многоугольнику новой вершины. Но вот смысл этого условия:
if (p->len >= p->alloc) {
p->alloc *= 2;
if (!p->alloc) p->alloc = 4;
p->v = (vec)realloc(p->v, sizeof(vec_t) * p->alloc);
}
от меня как-то ускользает. То есть понимаю, что это для выделения памяти, но почему именно так, зачем умножается на 2, присваивается 4, мне не очень понятно.

Answer 1

[Rsa97]

Это просто один из методов выделения памяти.
Если мало n байт, выделим 2n. Если и этого мало, то 4n, 8n, ... 2^kn.
А 4 - это стартовое значение, оно используется если p->alloc ещё нулевое.

Comments

[Clean Coder]

Спасибо. Если я правильно понял, то alloc - это объем памяти для заданного полигона, а size - количество его вершин. Нельзя ли было ограничиться одной size для выделения памяти?

[Rsa97]

HustleCoder, Не вижу тут size, тут только len. Но если, скажем, ромб, имеющий четыре вершины, после обрезки превратится в восьмиугольник, то где размещать дополнительные вершины?
Ваша функция как раз добавляет вершину в уже имеющийся многоугольник, при этом количество вершин и размер массива увеличиваются.

[Clean Coder]

Rsa97, ой, да, len, что-то меня переклинило) Ну, насколько я понял, эта функция добавляет только одну вершину в полигон, на что указывает, например, p->len++.

[Rsa97]

HustleCoder, Да, в полигон добавляется только одна вершина. Но, если для неё нет места, то размер массива вершин перед этим удваивается. Реаллокация памяти - достаточно затратная операция, связанная с копированием участка памяти, её накладно проводить для каждой новой вершины. Именно поэтому используется стратегия удвоения.

[Clean Coder]

Rsa97, теперь все более менее понятно. Спасибо!