रेखा रास्टरराइजेशन/4-कनेक्टेड ब्रेसनहेम

Question

टकराव परीक्षण के लिए मुझे एक पंक्ति रास्टर करने की आवश्यकता है। bresenham एल्गोरिथ्म लगभग के रूप में वांछित काम करता है, लेकिन दोष यह है कि तरह की एक पंक्ति का उत्पादन किया है:

और मैं की जरूरत है:

मेरे वर्तमान कार्यान्वयन (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; 
} 

वहाँ एक दूसरी लाइन रैस्टराइज़ेशन एल्गोरिथ्म मैं इस्तेमाल कर सकते हैं, या किसी को भी कैसे bresenham संशोधित पता है?

Answer 1

धन्यवाद कोआन, कभी कभी तुम सिर्फ कीवर्ड खोजने के लिए की कमी है, Algorithm for drawing a 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; 
} 

Answer 2

शायद यह उपयोगी हो जाएगा, गैर पूर्णांक अंत अंक के लिए मेरे संस्करण है। यह GridMap वर्ग का एक तरीका है जिसे मैं 2 डी मानचित्र में टकराव का पता लगाने के लिए ज्यामितीय आकारों के विशाल इंडेक्सिंग के लिए उपयोग करता हूं।

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); 
    } 
};