Исправление кода для алгоритма отсечения строки
Алгоритм деления средней точки [page-93 (104)] работает на основе разделения линии на более мелкие сегменты и проверяет каждый сегмент, чтобы определить, находятся ли они в пределах видимой границы области отсечения или нет.
В алгоритме двоичного поиска мы находим средний элемент и затем выбираем правую или левую часть.
Но здесь, как показано на следующем рисунке, после первой сегментации мы обнаруживаем, что оба подраздела фактически оспариваются. Итак, оба они являются кандидатами на дальнейшие подразделения. Таким образом, мы не можем продолжать как бинарный поиск.
Я использую итерационный метод. Но следующий код не работает:
Line2d GetClippedLine()
{
Line2d clippingCandidate = this->line;
std::vector<Line2d> lines = clippingCandidate.GetMidpointSubLines();
while(lines[0] != lines[1])
{
lines = clippingCandidate.GetMidpointSubLines();
Line2d one = lines[0];
Line2d two = lines[1];
if(one.IsClippingCandidate(rectangle))
{
clippingCandidate = one;
}
if(two.IsClippingCandidate(rectangle))
{
clippingCandidate = two;
}
if(one.IsVisible(rectangle))
{
Coordinates2d::Draw(one, Yellow);
}
if(two.IsVisible(rectangle))
{
Coordinates2d::Draw(two, Yellow);
}
clippingCandidate.Show();
//std::cout<<"++";
//two.Show();
std::cout<<"\n";
}
return clippingCandidate;
}
Решение
Вы совершенно правильно спросить. Появились объяснения подразделения средней точки, которые являются очень неряшливыми или просто неправильными. Похоже, ваш код основан на одном из этих плохих источников.
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.
Другие решения
Работая в геометрическом моделировании в течение нескольких лет, я всегда осуществлял все алгоритмы подразделения рекурсивным способом. Кодировать и понимать намного проще, и я уверен, что это не медленнее, чем итеративное решение.
Общий случай
Если отсечение является вогнутым, то ответ может состоять из произвольного числа сегментов. В этом случае вам нужен стек (замена стека кода из рекурсии). Вот пример реализации:
vector<Line> result; //ordered array of line segments = clipping result
stack<Line> pieces; //stack of pieces that are not processed yet
pieces.push(inputLine);
while (!pieces.empty()) {
auto curr = pieces.top();
pieces.pop();
if (GetLength(curr) < eps) //hard stop criterion
continue;
auto relative = GetSegmentPositionRelativeToRegion(curr, clippingRegion);
if (relative == FULLY_INSIDE)
result.push_back(curr);
else if (relative == INTERSECTS) { //not fully inside, not fully outside
Line left, right; //halves of the curr line segment
SplitAtMiddle(curr, left, right);
pieces.push(left);
pieces.push(right);
}
}
Выпуклый корпус
Если ваш регион отсечения гарантированно будет выпуклым, то в результате будет ровно один отрезок. В этом случае процесс подразделения имеет очень простую структуру. Предположим, что входной сегмент не полностью внутри или вне области отсечения (т.е. это пересекается).
Сначала вы подразделяете сегмент так, чтобы одна половина была вне а другой пересекается с отсечения. Это означает, что вы всегда можете запомнить только один рабочий отрезок.
В какой-то момент это правило нарушается, и после этого появляются две ветви подразделения. В левой ветке может быть два случая деления сегмента 🙁пересекается + внутри) или же (вне + пересекается). На правой стороне это отражается 🙁внутри + пересекается) или же (пересекается + вне). Во всех случаях только один подсегмент пересекается, поэтому остается только один рабочий сегмент. Вы можете написать отдельный код для каждой из ветвей в цикле.
Постскриптум Конечно, это описание игнорирует особые случаи, когда область отсечения проходит точно через среднюю точку. Что касается меня, реализация этого алгоритма не стоит хлопот.
Вам просто нужно подразделить любой фрагмент линии, который не полностью внутри или снаружи прямоугольника.
Что я не понимаю, так это то, для чего этот алгоритм хорош. По крайней мере, глядя на ваш код, было бы намного быстрее просто вычислить пересечения с прямоугольником.
Я думаю, что причина этого — hw реализации. Не думайте об этом как обрыв. Думайте об этом как об упражнении по сортировке линий (или более поздних проецируемых треугольников) в квадродерево. В конце вы можете обрезать до половины узлов, пока каждый узел не станет шириной всего в один пиксель. Не рассматривайте ваши внешние части как особые. Они просто очень большие четверки.