ぬの部屋(仮)
nu-no-he-ya
  •     123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
       1234
    567891011
    12131415161718
    19202122232425
    26272829   
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728     
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
     123456
    78910111213
    14151617181920
    21222324252627
    28      
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
    1234567
    891011121314
    15161718192021
    22232425262728
           
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
         12
    3456789
    10111213141516
    17181920212223
    242526272829 
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
        123
    45678910
    11121314151617
    18192021222324
    25262728   
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    15161718192021
    293031    
           
         12
    3456789
    10111213141516
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728     
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
          1
    2345678
    9101112131415
    16171819202122
    232425262728 
           
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
  • 線分の交差判定するコード

    線分の交差判定を行う。二次元画像の場合、結果がピクセル単位になるため座標の四捨五入が必要。

    LineCross.hpp

    #pragma once
    
    
    template<typename ScalarT>
    struct Point {
      ScalarT x, y; 
      Point(const ScalarT X, const ScalarT Y) :x(X), y(Y) {}
    
      template<typename T>
      Point(const Point<T>& src) {
        x = src.x;
        y = src.y;
      }
      Point() {}
    
    };
    
    template<typename ScalarT>
    struct LineSegment { 
      Point<ScalarT> s, e;
    
      template<typename T>
      LineSegment(const Point<T>& S, const Point<T>& E) :s(S), e(E) {}
      template<typename T>
      LineSegment(const LineSegment<T>& LS):s(LS.s),e(LS.e){}
      LineSegment() {}
    };
    using Pointd = Point<double>;
    using LineSegmentd = LineSegment<double>;
    
    
    //! @brief 線分の交点を求める
    //! @param [out] cross 交点座標の格納先
    //! @param [in] L1 線分1
    //! @param [in] L2 線分2
    //! @retval true 交差している
    //! @retval false 交差していない
    bool isCross(Pointd* cross, const LineSegmentd& L1, const LineSegmentd& L2) {
      const double Ax = L1.s.x;
      const double Ay = L1.s.y;
      const double Bx = L1.e.x;
      const double By = L1.e.y;
      const double Cx = L2.s.x;
      const double Cy = L2.s.y;
      const double Dx = L2.e.x;
      const double Dy = L2.e.y;
    
      //分子
      const double  s_numerator = (Cx - Ax)*(Dy - Cy) - (Cy - Ay)*(Dx - Cx);
      //分母
      const double s_denominator = (Bx - Ax)*(Dy - Cy) - (By - Ay)*(Dx - Cx);
    
      //分子
      const double t_numerator = (Ax - Cx)*(By - Ay) - (Ay - Cy)*(Bx - Ax);
      //分母
      const double t_denominator = (Dx - Cx)*(By - Ay) - (Dy - Cy)*(Bx - Ax);
    
    
      const double s = s_numerator / s_denominator;
      const double t = t_numerator / t_denominator;
    
      if (
        0 <= s && s <= 1
        &&
        0 <= t && t <= 1
        ) {
    
        cross->x = Ax + s * (Bx - Ax);
        cross->y = Ay + s * (By - Ay);
    
        return true;
      }
    
      return false;
    
    }
    using Pointi = Point<int>;
    using LineSegmenti = LineSegment<int>;
    
    
    //! @brief ピクセル単位を想定して線分の交差判定を行う
    bool isCrossPixel(Pointi* P, const LineSegmenti a, const LineSegmenti b) {
    
      LineSegmentd da(a);
      LineSegmentd db(b);
      Pointd c;
      if (isCross(&c, da, db) == false)
        return false;
    
      P->x = (int)round(c.x);// 四捨五入
      P->y = (int)round(c.y);// 四捨五入
    
      return true;
    
    }
    

    テストコード

    以前書いたBresenhamとデータ用にNByteDataを使用している。

    #pragma warning(disable:4996)
    
    #include <iostream>
    #include <vector>
    #include <random> // 乱数用
    
    #include "Bresenham.hpp"
    #include "NByteData.hpp"
    #include "LineCross.hpp"
    
    
    void ppmP3_write(
      const char* const fname,
      const int width,
      const int height,
      const unsigned char* const p,
      const int vmax
    );
    
    
    int main()
    {
      using ucrgb = NByteData<3>;
    
      int width = 200;
      int height = 200;
      std::vector<ucrgb> image;
    
      ucrgb Black = ucrgb{ 0,0,0 };
      ucrgb White = ucrgb{ 255,255,255 };
      ucrgb Red = ucrgb{ 255,0,0 };
      ucrgb Blue = ucrgb{ 0,0,255 };
    
      image.resize(width*height, White);
    
    
      // 疑似乱数
      std::mt19937 mt(2);
      // 0~5の範囲の一様乱数作成用
      // float型が欲しいなら std::uniform_real_distribution<> 
      std::uniform_int_distribution<> idistriW(0, width-1);
      std::uniform_int_distribution<> idistriH(0, height-1);
    
      //赤い線分
      const LineSegmenti A( Pointi(20,80),Pointi(190,123) );
      Bresenham(image.data(), width, height, A.s.x, A.s.y, A.e.x, A.e.y, Red);
    
      for (size_t i = 0; i < 10; i++) {
        int x1 = idistriW(mt);
        int y1 = idistriH(mt);
        int x2 = idistriW(mt);
        int y2 = idistriH(mt);
    
        //黒い線分
        LineSegmenti B(Pointi(x1,y1), Pointi(x2,y2) );
        Bresenham(image.data(), width, height, B.s.x, B.s.y, B.e.x, B.e.y, Black);
    
        //交点があれば着色
        Pointi c;
        if (isCrossPixel(&c, A, B) == true) {
          image[c.y*width + c.x] = Blue;
        }
    
      }
    
      //ファイル保存
      char fname[100];
      sprintf(fname, R"(C:\test\ret.ppm)", 10);
      ppmP3_write(fname, width, height, image.data()->data(), 255);
    
    }
    //! @brief PPM(RGB各1byte,カラー,テキスト)を書き込む
    //! @param [in] fname ファイル名
    //! @param [in] width 画像の幅
    //! @param [in] height 画像の高さ
    //! @param [in] p 画像のメモリへのアドレス
    //! @param [in] vmax 全てのRGBの中の最大値。普通の画像なら255
    //! @details RGBRGBRGB....のメモリを渡すと、RGBテキストでファイル名fnameで書き込む
    void ppmP3_write(
      const char* const fname,
      const int width,
      const int height,
      const unsigned char* const p,
      const int vmax
    ) {
    
      FILE* fp = fopen(fname, "wb");
      fprintf(fp, "P3\n%d %d\n%d\n", width, height, vmax);
    
      size_t k = 0;
      for (size_t i = 0; i < (size_t)height; i++) {
        for (size_t j = 0; j < (size_t)width; j++) {
          fprintf(fp, "%d %d %d ",
            p[k * 3 + 0],
            p[k * 3 + 1],
            p[k * 3 + 2]
          );
          k++;
        }
        fprintf(fp, "\n");
      }
    
      fclose(fp);
    }