Как преобразовать полилинию или полигон в код цепи?

Question

У меня есть открытая или замкнутая полилиния (многоугольник), состоящая из множества двумерных точек.

Мне нужно представить эту полилинию как цепочечный код. Если я правильно понимаю, мне нужно растеризовать сегменты полилинии, используя алгоритм Брешенема, и построить цепочечную форму растра. Но есть ли лучший алгоритм?

Каковы оптимальные алгоритмы преобразования полилинии (полигона) в цепной код?

Answer 1

Да, будет значительно быстрее просто нарисовать точки непосредственно в преобразовании Фурье. Пропустите растр и сделайте цепочку кодов от этого, ведь вам нужны точки правильно в порядке, в котором полилиния берет за то, что я предполагаю, алгоритмическое использование Kuhl-Giardiana 1982. Вы хотите, чтобы все пиксели были в правильном порядке, вы можете напрямую получить это, рисуя пиксели в самом алгоритме, а не растеризуя что-либо. Фактически, это в основном пропустит код цепи и растр.

---

Все линии собираются иметь вид у = х + Ь и самый быстрый способ сделать это будет Bresenham годов. Хотя, в зависимости от возможного использования, вы можете выбрать алгоритм Ву, чтобы можно было включить антиалиасинг, который, как правило, делает линии более четкими (и требует сохранения альфы). Предполагая, что вам нужен код цепи для чего-то конкретного, да, вам нужны фактические пиксели, которые будет вызывать эта строка, что означает использование алгоритма линейного рисования.

Большая часть вашего рисования apis даст вам растрированное изображение, а не цепочечный код. Существует возможность рисования полилинии на белом изображении с четким размером в черном и просмотра всего изображения и перечисления каждого черного пикселя. Было бы легко закодировать, хотя и медленное и ненужное, а в критически важных операциях было бы не стартером.

Код будет довольно простым, просто сделайте bresenham, а затем бросите точки, где он добавит точку в цепочный код.

public void plotLines(int[] twodshape, Chaincode chain) { 
    for (int i = 0, s = twodshape.length-4; i < s; i+=2) { 
     plotLine(twodshape[i],twodshape[i+1],twodshape[i+2],twodshape[i+3],chain); 
    } 
} 
public void plotLine(int x0, int y0, int x1, int y1, Chaincode chain) { 

    int dy = y1 - y0; //BRESENHAM LINE DRAW ALGORITHM 
    int dx = x1 - x0; 

    int stepx, stepy; 

    if (dy < 0) { 
     dy = -dy; 
     stepy = -1; 
    } else { 
     stepy = 1; 
    } 

    if (dx < 0) { 
     dx = -dx; 
     stepx = -1; 
    } else { 
     stepx = 1; 
    } 
    if (dx > dy) { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1; 
     int fraction = dy - (dx >> 1);       // same as 2*dy - dx 
     chain.add(x0,y0); 

     while (x0 != x1) { 
      if (fraction >= 0) { 
       y0 += stepy; 
       fraction -= dx;        // same as fraction -= 2*dx 
      } 
      x0 += stepx; 
      fraction += dy;         // same as fraction += 2*dy 
      chain.add(x0,y0); 
     } 
     chain.add(x0,y0); 
    } else { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1;             // dx is now 2*dx 
     int fraction = dx - (dy >> 1); 
     chain.add(x0,y0); 
     while (y0 != y1) { 
      if (fraction >= 0) { 
       x0 += stepx; 
       fraction -= dy; 
      } 
      y0 += stepy; 
      fraction += dx; 
      chain.add(x0,y0); 
     } 
     chain.add(x0,y0); 
    } 
} 

Обновление: я удалил рекурсивный бит, мне нужно, что для конкретной проблемы с линиями втягиваются от точки А до точки Б не гарантируется то же самое от В к А. В связи с округлением наклон. Например, если вы поднимаетесь на 1 пиксель и справа 5. Есть два одинаково допустимых способа сделать это, и это не дает мне последовательного ответа.

---

Если вы глубоко нуждается в chaincode:

public int convertToChaincode(int cx, int cy) { 
    if ((cx == 1) && (cy == 0)) return 0; 
    if ((cx == 1) && (cy == 1)) return 1; 
    if ((cx == 0) && (cy == 1)) return 2; 
    if ((cx == -1) && (cy == 1)) return 3; 
    if ((cx == -1) && (cy == 0)) return 4; 
    if ((cx == -1) && (cy == -1)) return 5; 
    if ((cx == 0) && (cy == -1)) return 6; 
    if ((cx == 1) && (cy == -1)) return 7; 
    return -1; //error. 
} 

public void plotLine(int x0, int y0, int x1, int y1, ChainCode chain) { 

    int dy = y1 - y0; //BRESENHAM LINE DRAW ALGORITHM 
    int dx = x1 - x0; 

    int stepx, stepy; 
    int cx = 0; 
    int cy = 0; 

    if (dy < 0) { 
     dy = -dy; 
     stepy = -1; 
    } else { 
     stepy = 1; 
    } 

    if (dx < 0) { 
     dx = -dx; 
     stepx = -1; 
    } else { 
     stepx = 1; 
    } 
    if (dx > dy) { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1; 
     int fraction = dy - (dx >> 1);       // same as 2*dy - dx 
     //typically set start point. 

     while (x0 != x1) { 
      if (fraction >= 0) { 
       y0 += stepy; 
       cy = stepy; 
       fraction -= dx;        // same as fraction -= 2*dx 
      } 
      x0 += stepx; 
      cx = stepx; 
      fraction += dy;         // same as fraction += 2*dy 
      chain.add(convertToChaincode(cx,cy)); 
     } 
    } else { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1;             // dx is now 2*dx 
     int fraction = dx - (dy >> 1); 
     //typically set start point 
     while (y0 != y1) { 
      if (fraction >= 0) { 
       x0 += stepx; 
       cx = stepx; 
       fraction -= dy; 
      } 
      y0 += stepy; 
      cy = stepy; 
      fraction += dx; 
      chain.add(convertToChaincode(cx,cy)); 
     } 
    } 
}