自己交差を回避するランダムウォーク

※非整数ブラウン運動とは関係ありません。

線分の交差判定
この辺の詳細は最下部に歳の割には頭の賢いYoutuberへの動画リンクを張っとくため、ご覧召されよ。

注意すること
線分の端点の扱いをおろそかにすると、ずっとヒット判定だしたり、線分の繋ぎ目をすり抜けたりすることがある。

//線分は交差するか
public boolean IsIntersect(PVector sv0, PVector ev0, ArrayList<PVector> vertex)
{
 VectorLine2D line = new VectorLine2D(sv0,ev0);
 
 for(int i = 0; i<vertex.size()-1; i++)
 {
   PVector sv = vertex.get(i);
   PVector ev = vertex.get(i+1);
   
   if(IsOnIntersect(line,new VectorLine2D(sv,ev)))
   {
     return true;
   }
 }
 return false;
}

//自己交差判定用
//最後の要素を判定しない : vertex.size()-2
public boolean IsIntersect_1(PVector sv0, PVector ev0, ArrayList<PVector> vertex)
{
 VectorLine2D line = new VectorLine2D(sv0,ev0);
 
 for(int i = 0; i<vertex.size()-2; i++)
 {
   PVector sv = vertex.get(i);
   PVector ev = vertex.get(i+1);
   
   if(IsOnIntersect(line,new VectorLine2D(sv,ev)))
   {
     return true;
   }
 }
 return false;
}

//線分は交差するか,OnLineをとる
public boolean IsOnIntersect(VectorLine2D l1, VectorLine2D l2)
{
 if (IsOnStraddle(l1, l2))
 {
   if (IsOnStraddle(l2, l1))
   {
     return true;
   }
 }
 return false;
}

//線分は交差するか,OnLineをとらない
public boolean IsOffIntersect(VectorLine2D l1, VectorLine2D l2)
{
 if (IsStraddle(l1, l2))
 {
   if (IsStraddle(l2, l1))
   {
     return true;
   }
 }
 return false;
}

//線分が直線を跨ぐ(直線から線分を見る)
//お互いにお互いを見ると, 平行でない限り必ずどこかで跨ぐ
public boolean IsOnStraddle(VectorLine2D l1, VectorLine2D l2)
{
 PVector lv1 = l1.LV();
 PVector l1SVtol2SV = PVector.sub(l2.SV, l1.SV);
 PVector l1SVtol2EV = PVector.sub(l2.EV, l1.SV);

 //OnLine(外積=0)を入念にとる
 if ((int)Cross(lv1, l1SVtol2SV) == 0 || (int)Cross(lv1, l1SVtol2EV) == 0)
 {
   return true;
 }
 //片方がプラマイどちらかで、片方が外積ゼロだと反応しないケースがでる気がする(未確認)
 if (((int)Cross(lv1, l1SVtol2SV) ^ (int)Cross(lv1, l1SVtol2EV)) < 0)
 {
   return true;
 }
 return false;
}

//線分が直線を跨ぐ(直線から線分を見る)
//お互いにお互いを見ると, 平行でない限り必ずどこかで跨ぐ
public boolean IsStraddle(VectorLine2D l1, VectorLine2D l2)
{
 PVector lv1 = l1.LV();
 PVector l1SVtol2SV = PVector.sub(l2.SV, l1.SV);
 PVector l1SVtol2EV = PVector.sub(l2.EV, l1.SV);

 //OnLineはとらない
 if ((int)Cross(lv1, l1SVtol2SV) == 0 || (int)Cross(lv1, l1SVtol2EV) == 0)
 {
   return false;
 }
 //これだけだとOnLineをとってしまうことがある
 if (((int)Cross(lv1, l1SVtol2SV) ^ (int)Cross(lv1, l1SVtol2EV)) < 0)
 {
   return true;
 }
 return false;
}

ランダムウォークする本体。

class ArrowLine
{
 PVector origin;
 
 PVector pprev;
 PVector prev;
 PVector current;
 
 ArrayList<PVector> Rails = new ArrayList<PVector>();
 
 //コンストラクタ
 ArrowLine(float x, float y)
 {
   origin = new PVector(x,y);
   Rails.add(origin.copy());
   current = origin.copy();
 }
 
 void update()
 {
   pprev = prev;
   prev = current;
   current = CalcuNext();
   
   //絶対座標で返ってくる場合
   Rails.add(current);
   
   if(ResetCondition()){Reset();}
   if(StopCondition()){Stop();}
 }
 
 void draw()
 {   
   for(int i = 0; i<this.Rails.size()-1; i++)
   {
     PVector sv = this.Rails.get(i);
     PVector ev = this.Rails.get(i+1);

     line(sv.x, sv.y, ev.x, ev.y);
   }
   
   //beginShape();
   //for(int i = 0; i<this.Rails.size()-1; i++)
   //{
   //  //skip
   //  //if(!(i%3==0)){continue;}
     
   //  PVector v = this.Rails.get(i);
   //  curveVertex(v.x, v.y);
   //}
   //endShape();
 }
   
 PVector CalcuNext()
 {
   return RandLimitStep();
 }

 //可能な限り自己交差しないようにする
 int _count = 0;
 PVector RandLimitStep()
 {
   _count = 0;
   if(!(2<this.Rails.size()))
   {
     return PVector.add(current, new PVector(random(-10,10),random(-10,10)));      
   }
   
   while(true)
   {      
     PVector end_v = this.Rails.get(this.Rails.size()-1);      
     PVector new_v = PVector.add(new PVector(random(-10,10),random(-10,10)), current);
     
     //生成されたベクトルが短すぎる場合
     //if(new_v.mag()<10)
     //{
     //  continue;
     //}
     
     //生成されたベクトルが画面外
     if(new_v.x<0||width<new_v.x)
     {
       continue;
     }
     if(new_v.y<0||height<new_v.y)
     {
       continue;
     }
     
     //railsと新しく作った点は自己交差するか
     //rails末端を含むと常に交差判定を出すので含まないようにする
     if(!IsIntersect_1(end_v, new_v, this.Rails))
     {
       return new_v;
     }
     
     _count++;
     if(100<_count)
     {
       //rollback
       current = prev;
       prev = pprev;
       this.Rails.remove(this.Rails.size()-1);
       
       if(10000<_count)
       {
         //error        
         Reset();
       }
     }
   }
 }
 
 boolean StopCondition()
 {
   return false;
 }
 void Stop()
 {
 }
 boolean ResetCondition()
 {
   return false;    
 }
 void Reset()
 {
   this.Rails.clear();
   this.Rails.add(origin.copy());
 }
}

他

int window_width = 500;
int window_height = 500;

int ww;
int wh;

void settings()
{
 size(window_width, window_height);
}

PVector pprev;
PVector prev;
PVector current;
PVector dv = new PVector(0,0);
void mousePressed() 
{
 pprev = new PVector(mouseX,mouseY);
 prev = new PVector(mouseX,mouseY);
 current = new PVector(mouseX,mouseY);
}

void mouseDragged()
{          
 pprev = prev.copy();
 prev = current.copy();
 current.x = mouseX;
 current.y = mouseY;  
 dv = PVector.sub(current,prev);
}

void mouseReleased()
{   
 pprev = null;
 prev = null;
 current = null; 
}

void setup()
{
 ww = window_width;
 wh = window_height;
 
 //画面中央
 arrow1 = new ArrowLine(width/2,height/2);
}

ArrowLine arrow1;
void draw() 
{
 background(255);
 
 stroke(0);
 arrow1.update();
 arrow1.draw();
}


 

以下、年の割には頭の賢いYoutuber