Исправление кода для алгоритма отсечения строки

Вы совершенно правильно спросить. Появились объяснения подразделения средней точки, которые являются очень неряшливыми или просто неправильными. Похоже, ваш код основан на одном из этих плохих источников.

M-S полезен только для поиска пересечений когда вы уже знаете, что сегмент пересекает границу отсечения (одна конечная точка на каждой стороне), и это обычно реализуется с целыми числами. Первоначально он использовался в качестве подпрограммы в вариации полного алгоритма отсечения Коэна и Сазерленда.

Увидеть статья в Википедии если вы не знакомы с C-S. «Исходящие коды» направляют последовательное обрезание бесконечных линий, содержащих границы области просмотра. В этом псевдокоде вы бы заменили математику с плавающей точкой на M-S.

Скажем, вы обрезаете левую границу в точке x = C, и отрезок, который ее охватывает P0(x0,y0)---P1(x1,y1), Скажи также x0<C<=x1, так P0 как известно, за пределами границы. Тогда алгоритм M-S:

tx1 = x1; // don't modify P1; it's inside the boundary
ty1 = y1;
while (x0 < C) {
xm = (x0 + tx1 + 1) >> 1;
ym = (y0 + ty1 + 1) >> 1;
if (xm <= C) { // the midpoint is on or outside the boundary
x0 = xm;     //   move P0
y0 = ym;
} else {       // the midpoint is strictly inside
tx1 = xm;    //   move P1
ty1 = ym;
}
}
// The clipped segment is (x0,x1)--(y0,y1).

Вам нужно 3 других незначительных варианта этого для 3 других границ.

Условия расторжения сложны. + 1необходимо избегать зацикливания в случае x0 = C-1 а также tx1 = C: (C + C - 1 + 1) >> 1 == C, так что следующая итерация закончится.

Сказав это, подразделение средней точки в значительной степени устарело. Это было полезно с процессорами, которые имели только целочисленную арифметику (часто это происходило по крайней мере до середины 90-х; я реализовал это на ассемблере 8088 в 1984 году). Нахождение средней точки требует только деления на 2, что является целочисленным смещением вправо, поэтому можно было обрезать не более потолка (log_2 n) быстрых итераций для координат максимального размера n. В наши дни, когда устройства с плавающей запятой работают со скоростью гигафлопа, вероятно, быстрее и, безусловно, легче обрезать с плавающей запятой.

прибавление
Просто для удовольствия, реализовано в C:

#include <stdio.h>
#include <stdlib.h>

typedef unsigned OUTCODE;
typedef int COORD;
typedef int BOOL;
#define TRUE 1
#define FALSE 0

#define XMIN 0
#define YMIN 0
#define XMAX 5000
#define YMAX 3000

// Not strictly portable, but usually fine.
#define SIGN_BIT (~(~0u >> 1))

#define LEFT SIGN_BIT
#define TOP (LEFT >> 1)
#define RIGHT (TOP >> 1)
#define BOTTOM (RIGHT >> 1)
#define ALL (LEFT | BOTTOM | RIGHT | TOP)

// Mask the sign bit.
#define M(X) ((X) & SIGN_BIT)

// Shift previous value and mask in the new sign bit.
#define SM(Prev, New) (((OUTCODE)(Prev) >> 1) | M(New))

__inline OUTCODE outcode(COORD x, COORD y) {
return SM(SM(SM(M(YMAX - y), XMAX - x), y - YMIN), x - XMIN);
}

// In the S-T coordinate system, pO is outside boundary C and will be moved
// to the boundary while pI doesn't move. I is the termination correction.
#define MOVE_TO_BOUNDARY(SO, TO, SI, TI, C, I, IS_OUTSIDE) do { \
COORD tsi = SI, tti = TI; \
while (SO IS_OUTSIDE C) { \
COORD sm = (tsi + SO + I) >> 1; \
COORD tm = (tti + TO + I) >> 1; \
if (sm IS_OUTSIDE ## = C) { \
SO = sm; \
TO = tm; \
} else { \
tsi = sm; \
tti = tm; \
} \
} \
} while (0)

BOOL clip(COORD *x0p, COORD *y0p, COORD *x1p, COORD *y1p) {
COORD x0 = *x0p, y0 = *y0p, x1 = *x1p, y1 = *y1p;
OUTCODE code0 = outcode(x0, y0);
OUTCODE code1 = outcode(x1, y1);
for (;;) {
if ((code0 | code1) == 0) {
*x0p = x0; *y0p = y0; *x1p = x1; *y1p = y1;
return TRUE;
} else if (code0 & code1) {
return FALSE;
} else if (code0) {
if (code0 & BOTTOM)     MOVE_TO_BOUNDARY(y0, x0, y1, x1, YMAX, 0, >);
else if (code0 & RIGHT) MOVE_TO_BOUNDARY(x0, y0, x1, y1, XMAX, 0, >);
else if (code0 & TOP)   MOVE_TO_BOUNDARY(y0, x0, y1, x1, YMIN, 1, <);
else /* LEFT */         MOVE_TO_BOUNDARY(x0, y0, x1, y1, XMIN, 1, <);
code0 = outcode(x0, y0);
} else {
if (code1 & BOTTOM)     MOVE_TO_BOUNDARY(y1, x1, y0, x0, YMAX, 0, >);
else if (code1 & RIGHT) MOVE_TO_BOUNDARY(x1, y1, x0, y0, XMAX, 0, >);
else if (code1 & TOP)   MOVE_TO_BOUNDARY(y1, x1, y0, x0, YMIN, 1, <);
else /* LEFT */         MOVE_TO_BOUNDARY(x1, y1, x0, y0, XMIN, 1, <);
code1 = outcode(x1, y1);
}
}
}

int main(void) {
int n = 0, margin = 2000;
for (;;) {
// Generate some random points around the viewport.
int x0 = rand() % (2 * margin + XMAX - XMIN) - margin;
int y0 = rand() % (2 * margin + YMAX - YMIN) - margin;
int x1 = rand() % (2 * margin + XMAX - XMIN) - margin;
int y1 = rand() % (2 * margin + YMAX - YMIN) - margin;
printf("a(%d, %d)--(%d, %d) %x--%x\n", x0, y0, x1, y1,
outcode(x0,y0) >> 28, outcode(x1,y1) >> 28);
BOOL r = clip(&x0, &y0, &x1, &y1);
printf("a(%d, %d)--(%d, %d): %d\n", x0, y0, x1, y1, r);
}
return 0;
}

На моем MacBook он обрезает миллиард сегментов за 90 секунд. Было бы интересно увидеть, как это сравнивается с плавающей точкой C-S.