Линейная растеризация / 4-связный Брезенхэм

Для проверки столкновений мне нужно растрировать линию. Алгоритм Брезенхэма работает почти так, как хотелось бы, но имеет недостаток, заключающийся в том, что он выдает строку вида: Брезенхем.svg.png" alt="">

И мне нужно:

Моя текущая реализация (на основе http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Simplification):

public boolean isInsideLine(int x1, int y1, int x2, int y2) {
    final int dx = abs(x2 - x1), dy = abs(y2 - y1);
    final int sx = x1 < x2 ? 1 : -1, sy = y1 < y2 ? 1 : -1;
    int err = dx - dy;

    while (true) {
        if (isInside(x1, y1)) //Lookup in pixel array
            return true;
        if (x1 == x2 && y1 == y2)
            break;
        final int e2 = err << 1;
        if (e2 > -dy) {
            err -= dy;
            x1 += sx;
        }
        if (e2 < dx) {
            err += dx;
            y1 += sy;
        }
    }
    return false;
}

Есть ли другой алгоритм растеризации линий, который я мог бы использовать, или кто-нибудь знает, как изменить брезенхем?


java raster rasterizing bresenham
person DiddiZ    schedule 24.11.2012    source источник
comment
Мне кажется, что необработанный вывод Брезенхема 8-связный, но вам требуется 4-связный. Вы можете выполнить постобработку необработанного вывода, чтобы обнаружить диагональную связь, а затем решить, к какому пикселю линия ближе всего.   -  person koan    schedule 24.11.2012
comment
См. stackoverflow.com/questions/ 5186939/, похоже, на тот же вопрос.   -  person koan    schedule 24.11.2012
comment
Ради интереса: зачем нужно растрировать линию для обнаружения столкновений? Разве вы не можете просто вычислить пересечения?   -  person Axel    schedule 24.11.2012
comment
Это для (почти) точного пиксельного 2D-столкновения.   -  person DiddiZ    schedule 24.11.2012

Ответы (2)


arrow_upward
3
arrow_downward

Может будет полезно, есть моя версия для нецелочисленных конечных точек. Это метод класса GridMap, который я использую для пространственного индексирования геометрических фигур, чтобы ускорить обнаружение столкновений на 2D-карте.

int GridMap::insertLine( int lineId, double ax, double ay, double bx, double by ){
    // get index of endpoints in GridMap
    int ix    = getIx( ax ); 
    int iy    = getIy( ay );
    int ixb   = getIx( bx );
    int iyb   = getIy( by );
    // insert endpoints to GridMap
    insert( lineId, ix, iy   ); 
    insert( lineId, ixb, iyb );
    // raster central part of the line
    double dx = fabs( bx - ax );
    double dy = fabs( by - ay );
    int dix = ( ax < bx ) ? 1 : -1;
    int diy = ( ay < by ) ? 1 : -1;
    double x=0, y=0;
    while ( ( ix != ixb ) && ( iy != iyb  ) ) {
        if ( x < y ) {
            x  += dy;
            ix += dix;
        } else {
            y  += dx;
            iy += diy;
        }
        insert( lineId, ix, iy );
    }
};
person Prokop Hapala    schedule 31.12.2014
comment
Не работает. Во-первых, если начальная и конечная точки попадают в один и тот же квадрат сетки, линия будет добавлена ​​дважды в один и тот же квадрат сетки. Во-вторых, это не работает для горизонтальных/вертикальных линий: для горизонтальной линии iy будет равно iyb. Содержимое цикла while никогда не будет выполнено: потому что iy != iyb никогда не будет истинным. На самом деле это хуже, чем просто неработающие горизонтальные/вертикальные линии. Этот фрагмент кода просто неправильно рисует окончание любой линии, которая не является диагональю. Чем ближе к горизонтали/вертикали, тем больше пикселей будет не хватать. - person Jyaif; 26.07.2020

arrow_upward
1
arrow_downward

Спасибо, коан, иногда вам просто не хватает ключевых слов для поиска, алгоритм рисования 4 -connected line, похоже, решает эту проблему:

public boolean isInsideLine(int x1, int y1, int x2, int y2) {
    final int dx = abs(x2 - x1), dy = abs(y2 - y1);
    final int sx = x1 < x2 ? 1 : -1, sy = y1 < y2 ? 1 : -1;
    int err = dx - dy;

    while (true) {
        if (isInside(x1, y1)) //Lookup in pixel array
            return true;
        if (x1 == x2 && y1 == y2)
            break;
        final int e2 = err << 1;
        if (e2 > -dy) {
            err -= dy;
            x1 += sx;
        } else if (e2 < dx) { // else if instead of if
            err += dx;
            y1 += sy;
        }
    }
    return false;
}
person DiddiZ    schedule 24.11.2012