Polylineあれやこれや

Polyline : List<Vector2D>の末尾とindex[0]が繋がっていないもの
Polygon : 繋がってるもの

GetLength

ポリラインの長さを求める

float GetLength(ArrayList<PVector> polyline)
{
 float sum = 0;  
 for(int i = 0; i<polyline.size()-1; i++)
 {
   PVector sv = polyline.get(i).copy();
   PVector ev = polyline.get(i+1).copy();
   PVector lv = ev.sub(sv);
   sum+=lv.mag();
 }
 return sum;
}

Vector2D Polyline(t)

ポリライン全体長をt[0-1]で表した時、tを入力してポリライン上の座標を得る。

//入力t[0-1]->出力Vector2D
PVector Get_t(ArrayList<PVector> polyline, float t)
{
 float total_length = GetLength(polyline);
 if(total_length<=0){return null;}
 float accum_length = 0;  

 for(int i = 0; i<polyline.size()-1; i++)
 {
   PVector v0 = polyline.get(i);
   PVector v1 = polyline.get(i+1);
   PVector lv = v1.copy().sub(v0);    
       
   float prev_accum_length = accum_length;    
   accum_length += lv.mag();
       
   //目的のt値を通り抜けたら    
   if(t<accum_length/total_length)
   {      
     //当該lv区間は全体t[0-1]のうち、どれだけのt値を割り当てられるか
     //例えば等距離5区間ならばsection_t=0.2
     //この値で除することでpolyline[0-1]からlv[0-1]にt値を直す
     //いいかえるなら全体polylineと区間lvの長さの比
     float section_t = lv.mag()/total_length;
     if(section_t<=0){return null;}
     
     //目的のtから直前座標v0までのtを減算
     float frac_t = t-(prev_accum_length/total_length);
     
     PVector p = v0.copy().add(lv.copy().mult(frac_t/section_t));
     return p;
   }    
 }  
 return null;
}

多分同じこと

PVector Get_t(ArrayList<PVector> polyline, float t)
{
 float total_length = GetLength(polyline);  
 float current_length = 0;
 float prev_t = 0;
 float current_t = 0;  
 
 for(int i = 0; i<polyline.size()-1; i++)
 {
   PVector sv = polyline.get(i);
   PVector ev = polyline.get(i+1);
   PVector lv = ev.copy().sub(sv);
   current_length += lv.mag();    
   prev_t = current_t;
   current_t = current_length/total_length;
   
   if(t<current_t)
   {
     PVector coordinate = sv.copy().add(lv.copy().normalize().mult(total_length*(t-prev_t)));
     return coordinate;
   }
 }  
 return null;
}

Vector2D Polyline(index, t)

ポリラインの座標区間各々をt[0-1]とする場合。

PVector Get_IndexT(ArrayList<PVector> polyline, int index, float t)
{
 if(0<=index&&index<polyline.size()-1)
 {
   PVector v0 = polyline.get(index);
   PVector v1 = polyline.get(index+1);
   PVector lv = v1.copy().sub(v0);
   return v0.copy().add(lv.mult(t));
 }
 return null;
}

NearestOnSegments : 最近接点

PVector NearestOnPolyline(ArrayList<PVector> polyline, PVector vertex)
{
 return NearestOnSegments(polyline,vertex);
}

PVector NearestOnSegments(ArrayList<PVector> vectors, PVector v)
{
 float min_distance = Float.MAX_VALUE;
 PVector ret = vectors.get(0);
 for(int i = 0; i<vectors.size()-1; i++)
 {
   PVector v0 = vectors.get(i);
   PVector v1 = vectors.get(i+1);
   PVector near = NearestOnSegment(v0,v1,v);
   
   PVector n2v = PVector.sub(v, near);
   float d = n2v.mag();
   if( d<min_distance)
   {
     min_distance = d;
     ret = near;
   }
 }
 return ret;
}

PVector NearestOnSegment(PVector sv, PVector ev, PVector v)
{
PVector lv = PVector.sub(ev,sv);
PVector toV = PVector.sub(v,sv);
float t = Dot(toV,lv)/Dot(lv,lv);
if(t<0){t=0;}
if(1<t){t=1;}
return PVector.add(sv, lv.mult(t));
}

NearestOnPolyline : 最近接点のt[0-1]値

float NearestOnPolyline_t(ArrayList<PVector> polyline, PVector vertex)
{
 float total_length = GetLength(polyline);
 if(total_length<=0){return 0;}
 float accum_length = 0;
  
 float min_distance = Float.MAX_VALUE;//更新用最近接距離  
 PVector nearest = polyline.get(0);//更新用最近接点  
 int nearest_segment_index = 0;//更新用SegmentIndex
 
 float t = 0;
 
 for(int i = 0; i<polyline.size()-1; i++)
 {
   PVector v0 = polyline.get(i);
   PVector v1 = polyline.get(i+1);
   PVector lv = v1.copy().sub(v0);
     
   PVector temp_nearest = NearestOnSegment(v0,v1,vertex);//各線分上の最近接点      
   PVector near2vertex = PVector.sub(vertex, temp_nearest);//その距離
   float distance = near2vertex.mag();
   
   //最近接点の更新
   if( distance<min_distance)
   {
     min_distance = distance;//入力vertexから最近接点までの現在の最小距離
     nearest = temp_nearest;//その時の最近接点
     nearest_segment_index = i;//最近接点を有する線分のsvのindex
     
     PVector to_nearest = nearest.copy().sub(v0);
     float frac_length = to_nearest.mag();
     t = (accum_length + frac_length)/total_length;
     break;
   }
   accum_length += lv.mag();    
 }    
 return t;  
}

NearestOnPolyline : 最近接点の(index, t)値

PVector NearestOnPolyline_IndexT(ArrayList<PVector> polyline, PVector vertex)
{   
 float min_distance = Float.MAX_VALUE;//更新用最近接距離  
 PVector nearest = polyline.get(0);//更新用最近接点  
 int nearest_segment_index = 0;//更新用SegmentIndex
 
 float t = 0;
 
 for(int i = 0; i<polyline.size()-1; i++)
 {
   PVector v0 = polyline.get(i);
   PVector v1 = polyline.get(i+1);
   PVector lv = v1.copy().sub(v0);
     
   PVector temp_nearest = NearestOnSegment(v0,v1,vertex);//各線分上の最近接点      
   PVector near2vertex = PVector.sub(vertex, temp_nearest);//その距離
   float distance = near2vertex.mag();
   
   //最近接点の更新
   if( distance<min_distance)
   {
     min_distance = distance;//入力vertexから最近接点までの現在の最小距離
     nearest = temp_nearest;//その時の最近接点
     nearest_segment_index = i;//最近接点を有する線分のsvのindex
     
     PVector to_nearest = nearest.copy().sub(v0);
     float frac_length = to_nearest.mag();
     t = frac_length/lv.mag();
     break;
   }    
 }    
 return new PVector(nearest_segment_index, t);  
}

ポリライン交点

PVector GetIntersectionPolyline(ArrayList<PVector> polyline1, ArrayList<PVector> polyline2)
{
 if(polyline1==null){return null;}
 if(polyline2==null){return null;}
 for(int i = 0; i<polyline1.size()-1; i++)
 {
   PVector sv1 = polyline1.get(i);
   PVector ev1 = polyline1.get(i+1);    
   PVector intersection = GetIntersectionSeg2Polyline(sv1,ev1,polyline2);
   if(intersection!=null){return intersection;}
 }
 return null;
}

//発見した最初の交点を返す
PVector GetIntersectionSeg2Polyline(PVector sv, PVector ev, ArrayList<PVector> polyline)
{    
   //交点追加
   for(int i = 0; i<polyline.size()-1; i++)
   {
     PVector other_sv = polyline.get(i);
     PVector other_ev = polyline.get(i+1);        
     PVector intersection = GetIntersectionSeg2Seg(sv,ev,other_sv,other_ev);
     if(intersection!=null){return intersection;}      
   }
   return null;
}

PVector GetIntersectionSeg2Seg(PVector sv1, PVector ev1, PVector sv2, PVector ev2)
{
 return GetIntersectionSeg2Seg(new VectorLine2D(sv1,ev1), new VectorLine2D(sv2, ev2));
}

PVector GetIntersectionSeg2Seg(VectorLine2D seg1, VectorLine2D seg2)
{      
 if(IsIntersectSeg2Seg(seg1,seg2))
 {
  PVector lv1 = GetLV(seg1);
  PVector lv2 = GetLV(seg2);
  
   //toSeg2
   PVector v = PVector.sub(seg2.SV, seg1.SV);
   
   //lv1の交点までのt
   float t1 = (float)(Cross(v, lv2)/ Cross(lv1, lv2));    
   //lv2の交点までのt
   //float t2 = (float)(Cross(v, lv1)/ Cross(lv1, lv2));

   return PVector.add(seg1.SV, PVector.mult(lv1, t1));
 }
 return null;
}

//線分は交差するか、端点も判定する
boolean IsIntersectSeg2Seg(VectorLine2D seg1, VectorLine2D seg2)
{
 if (IsOnStraddle(seg1, seg2))
 {
   if (IsOnStraddle(seg2, seg1))
   {
     return true;
   }
 }
 return false;
}

//線分が直線を跨ぐ(直線から線分を見る)
//お互いにお互いを見ると, 平行でない限り必ずどこかで跨ぐ
//線分の両端点が直線を挟んで反対の領域にある
boolean IsOnStraddle(VectorLine2D line, VectorLine2D seg)
{
 PVector lv1 = GetLV(line);
 PVector L1SVtoSegSV = PVector.sub(seg.SV, line.SV);
 PVector L1SVtoSegEV = PVector.sub(seg.EV, line.SV);

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

GetPolylineIntersection_t : 交点のt[0-1]値

//交点位置をt[0-1]で返す
float GetPolylineIntersection_t(ArrayList<PVector> polyline, ArrayList<PVector> clipper)
{
 float total_length = GetLength(polyline);
 if(total_length<=0){return 0;}
 float accum_length = 0;   
 float total_t = 0;
 
 for(int i = 0; i<polyline.size()-1; i++)
 {
   PVector spline_sv = polyline.get(i).copy();
   PVector spline_ev = polyline.get(i+1).copy();
   //区間LV
   PVector spline_lv = spline_ev.copy().sub(spline_sv);    

   for(int j = 0; j<clipper.size()-1; j++)
   {
     PVector clipper_sv = clipper.get(j).copy();
     PVector clipper_ev = clipper.get(j+1).copy();      
     
     PVector intersection = GetIntersectionSeg2Seg(spline_sv,spline_ev,clipper_sv,clipper_ev);
     if(intersection==null){continue;}      
     
     PVector to_intersection = intersection.copy().sub(spline_sv);      
     total_t = (to_intersection.mag()+accum_length)/total_length;
     return total_t;
   }
   accum_length+=spline_lv.mag();
 }
 return total_t;
}

GetPolylineIntersection_tt : 交点のt[0-1]値

Polyline側の交点位置のt
及びClipper側の交点位置のtもとる

//全体を1として、交点位置を0-1のtで返す(spline,clipper共に)
PVector GetPolylineIntersection_tt(ArrayList<PVector> polyline, ArrayList<PVector> clipper)
{
 float total_length = GetLength(polyline);
 float accum_length = 0;
 float clipper_total_length = GetLength(clipper);
 float clipper_accum_length = 0;
 
 for(int i = 0; i<polyline.size()-1; i++)
 {
   PVector spline_sv = polyline.get(i).copy();
   PVector spline_ev = polyline.get(i+1).copy();  
   PVector spline_lv = spline_ev.copy().sub(spline_sv);   
   
   for(int j = 0; j<clipper.size()-1; j++)
   {
     PVector clipper_sv = clipper.get(j).copy();
     PVector clipper_ev = clipper.get(j+1).copy();         
     PVector clipper_lv = clipper_ev.copy().sub(clipper_sv);

     PVector intersection = GetIntersectionSeg2Seg(spline_sv,spline_ev,clipper_sv,clipper_ev);
     if(intersection==null||Float.isNaN(intersection.x)||Float.isNaN(intersection.y))
     {
       clipper_accum_length+=clipper_lv.mag();
       continue;
     }    
     
     //交差した
     PVector to_intersection = intersection.copy().sub(spline_sv);
     PVector clipper_to_intersection = intersection.copy().sub(clipper_sv);
     
     accum_length += to_intersection.mag();
     clipper_accum_length += clipper_to_intersection.mag();
     return  new PVector( accum_length/total_length, clipper_accum_length/clipper_total_length);
   }    
   //Clipperと交差しない->長さ累積            
   accum_length+=spline_lv.mag();   
   clipper_accum_length = 0;
 }
 return null;
}

GetPolylineIntersection_t : 交点の(index, t)値

//(index,t)交点手前のIndexと区間tで返す
PVector GetPolylineIntersection_IndexT(ArrayList<PVector> polyline, ArrayList<PVector> clipper)
{
 int spline_index = -1;
 float index_t = 0;
 
 for(int i = 0; i<polyline.size()-1; i++)
 {
   PVector spline_sv = polyline.get(i).copy();
   PVector spline_ev = polyline.get(i+1).copy();
   for(int j = 0; j<clipper.size()-1; j++)
   {
     PVector clipper_sv = clipper.get(j).copy();
     PVector clipper_ev = clipper.get(j+1).copy();      
     
     PVector intersection = GetIntersectionSeg2Seg(spline_sv,spline_ev,clipper_sv,clipper_ev);
     if(intersection==null){continue;}      
     spline_index = i;//交点手前のindex 
     
     //区間LV
     PVector spline_lv = spline_ev.copy().sub(spline_sv);
     
     PVector to_intersection = intersection.copy().sub(spline_sv);      
     index_t = (to_intersection.mag())/(spline_lv.mag());
     return new PVector(spline_index,index_t);
   }
 }
 return new PVector(spline_index,index_t);
}

Polyline切断

Polyline同士の交点でポリラインを切断する
To : 交点まで
From : 交点から

//clipperまでを返す(ToClipper)
ArrayList<PVector>ClippingPolylineTo(ArrayList<PVector> polyline, ArrayList<PVector> clipper)
{  
 //(index,t)
 PVector index_t = GetPolylineIntersection_IndexT(polyline,clipper);
 int index = (int)(index_t.x);
 float t = index_t.y;  

 if(index_t.x<0){return null;}  
 ArrayList<PVector> ret = new ArrayList<PVector>();
 
 for(int i = 0; i<index; i++)
 {
   ret.add(polyline.get(i).copy());    
 }
 
 PVector sv = polyline.get(index).copy();
 PVector ev = polyline.get(index+1).copy();
 PVector lv = ev.copy().sub(sv);
 lv.mult(t);  
 PVector intersection = sv.copy().add(lv); 
 
 ret.add(intersection);  
 return ret;  
}

ArrayList<PVector>ClippingPolylineFrom(ArrayList<PVector> polyline, ArrayList<PVector> clipper)
{  
 //(index,t)
 PVector index_t = GetPolylineIntersection_IndexT(polyline,clipper);
 int index = (int)(index_t.x);
 float t = index_t.y;  

 if(index_t.x<0){return null;}  
 
 ArrayList<PVector> ret = new ArrayList<PVector>();
 PVector sv = polyline.get(index).copy();
 PVector ev = polyline.get(index+1).copy();
 PVector lv = ev.copy().sub(sv);
 lv.mult(t);  
 PVector intersection = sv.copy().add(lv);   
 ret.add(intersection); 
 
 for(int i = index+1; i<polyline.size(); i++)
 {
   ret.add(polyline.get(i).copy());    
 } 
 return ret;  
}

Polyline切断(t[0-1]値)

Polylineをt[0-1]値で切断, t地点の座標は記録する

//tまで
ArrayList<PVector> ToPolyline_t(ArrayList<PVector> polyline, float t)
{
 float total_length = GetLength(polyline);
 if(total_length<=0){return null;}
 float accum_length = 0;  
 
 ArrayList<PVector> ret = new ArrayList<PVector>();
 ret.add(polyline.get(0));
 for(int i = 0; i<polyline.size()-1; i++)
 {
   PVector v0 = polyline.get(i);
   PVector v1 = polyline.get(i+1);
   PVector lv = v1.copy().sub(v0);    
       
   float prev_accum_length = accum_length;    
   accum_length += lv.mag();
       
   if(t<accum_length/total_length)
   {
     //ここまで記録
     
     //区間はt[0-1]のうち、どれだけのt値を使用するか
     //例えば等距離5区間ならばinter_t=0.2
     //この値で除することでpolyline[0-1]からlv[0-1]にt値を直す
     float inter_t = lv.mag()/total_length;
     float frac_t = t-(prev_accum_length/total_length);
     PVector p = v0.copy().add(lv.copy().mult(frac_t/inter_t));
     ret.add(p);
     break;//離脱
   }    
   ret.add(polyline.get(i).copy());
 }  
 if(ret.size()<=0){return null;}
 return ret;  
}

//tから
ArrayList<PVector> FromPolyline_t(ArrayList<PVector> polyline, float t)
{
 float total_length = GetLength(polyline);
 if(total_length<=0){return null;}
 float accum_length = 0;  

 
 ArrayList<PVector> ret = new ArrayList<PVector>();
 int rec_start_index = -1;
 for(int i = 0; i<polyline.size()-1; i++)
 {
   PVector v0 = polyline.get(i);
   PVector v1 = polyline.get(i+1);
   PVector lv = v1.copy().sub(v0);    
       
   float prev_accum_length = accum_length;    
   accum_length += lv.mag();
       
   if(t<accum_length/total_length)
   {
     //ここから記録開始
     
     //区間はt[0-1]のうち、どれだけのt値を使用するか
     //例えば等距離5区間ならばinter_t=0.2
     //この値で除することでpolyline[0-1]からlv[0-1]にt値を直す
     float inter_t = lv.mag()/total_length;
     
     float frac_t = t-(prev_accum_length/total_length);
     PVector p = v0.copy().add(lv.copy().mult(frac_t/inter_t));
     ret.add(p);
     rec_start_index = i+1;
     break;//離脱
   }    
 }  
 
 if(rec_start_index<0){return null;}
 
 for(int i = rec_start_index; i<polyline.size(); i++)
 {
   ret.add(polyline.get(i).copy());
 }
 return ret;
}

UnionPolyline

Polyline同士を切ったり貼ったりする

//ToTo
ArrayList<PVector> UnionPolylineTT(ArrayList<PVector> polyline1, ArrayList<PVector> polyline2)
{
 ArrayList<PVector> ret = new ArrayList<PVector>();
 PVector intersection_tt = GetPolylineIntersection_tt(polyline1,polyline2);
 if(intersection_tt==null){return null;}
 
 ArrayList<PVector> f1 = ToPolyline_t(polyline1, intersection_tt.x);
 ArrayList<PVector> f2 = ToPolyline_t(polyline2, intersection_tt.y); 
 
 if(f1!=null&&0<f1.size())
 {    
   ret.addAll(f1);
 }
 if(f2!=null&&0<f2.size())
 {
   Collections.reverse(f2);
   ret.addAll(f2);
 }
 return ret;
}

//ToFrom
ArrayList<PVector> UnionPolylineTF(ArrayList<PVector> polyline1, ArrayList<PVector> polyline2)
{
 ArrayList<PVector> ret = new ArrayList<PVector>();
 PVector intersection_tt = GetPolylineIntersection_tt(polyline1,polyline2);
 if(intersection_tt==null){return null;}
 
 ArrayList<PVector> f1 = ToPolyline_t(polyline1, intersection_tt.x);
 ArrayList<PVector> f2 = FromPolyline_t(polyline2, intersection_tt.y); 
 
 if(f1!=null&&0<f1.size())
 {    
   ret.addAll(f1);
 }
 if(f2!=null&&0<f2.size())
 {
   ret.addAll(f2);
 }
 return ret;
}

//FromFrom
ArrayList<PVector> UnionPolylineFF(ArrayList<PVector> polyline1, ArrayList<PVector> polyline2)
{
 ArrayList<PVector> ret = new ArrayList<PVector>();
 PVector intersection_tt = GetPolylineIntersection_tt(polyline1,polyline2);
 if(intersection_tt==null){return null;}
 
 ArrayList<PVector> f1 = FromPolyline_t(polyline1, intersection_tt.x);
 ArrayList<PVector> f2 = FromPolyline_t(polyline2, intersection_tt.y); 
 
 if(f1!=null&&0<f1.size())
 {
   Collections.reverse(f1);
   ret.addAll(f1);
 }
 if(f2!=null&&0<f2.size())
 {
   ret.addAll(f2);
 }
 return ret;
}

UnionSpline

一度低精度でスプラインを補間し、交点のt値を計算。それを高精度のスプライン側に強引に反映する。

//ToTo
ArrayList<PVector> UnionSplineTT(ArrayList<PVector> cp1, ArrayList<PVector> cp2, int degree, float resolution, float low_resolution)
{
 ArrayList<PVector> low_sp1 = CalcuOpenSpline(cp1, degree, low_resolution);
 ArrayList<PVector> low_sp2 = CalcuOpenSpline(cp2, degree, low_resolution);
 PVector intersection_tt = GetPolylineIntersection_tt(low_sp1,low_sp2);
 if(intersection_tt==null){return null;}
 
 ArrayList<PVector> sp1 = CalcuOpenSpline(cp1, degree, resolution);
 ArrayList<PVector> sp2 = CalcuOpenSpline(cp2, degree, resolution);  
 ArrayList<PVector> f1 = ToPolyline_t(sp1, intersection_tt.x);
 ArrayList<PVector> f2 = ToPolyline_t(sp2, intersection_tt.y);   
 
 ArrayList<PVector> ret = new ArrayList<PVector>();
 if(f1!=null&&0<f1.size())
 {
   ret.addAll(f1);
 }
 if(f2!=null&&0<f2.size())
 {
   Collections.reverse(f2);
   ret.addAll(f2);
 }
 return ret;  
}

//ToFrom
ArrayList<PVector> UnionSplineTF(ArrayList<PVector> cp1, ArrayList<PVector> cp2, int degree, float resolution, float low_resolution)
{
 ArrayList<PVector> low_sp1 = CalcuOpenSpline(cp1, degree, low_resolution);
 ArrayList<PVector> low_sp2 = CalcuOpenSpline(cp2, degree, low_resolution);
 PVector intersection_tt = GetPolylineIntersection_tt(low_sp1,low_sp2);
 if(intersection_tt==null){return null;}
 
 ArrayList<PVector> sp1 = CalcuOpenSpline(cp1, degree, resolution);
 ArrayList<PVector> sp2 = CalcuOpenSpline(cp2, degree, resolution);  
 ArrayList<PVector> f1 = ToPolyline_t(sp1, intersection_tt.x);
 ArrayList<PVector> f2 = FromPolyline_t(sp2, intersection_tt.y);   
 
 ArrayList<PVector> ret = new ArrayList<PVector>();
 if(f1!=null&&0<f1.size())
 {
   ret.addAll(f1);
 }
 if(f2!=null&&0<f2.size()){ret.addAll(f2);}
 return ret;  
}

//FromFrom
ArrayList<PVector> UnionSplineFF(ArrayList<PVector> cp1, ArrayList<PVector> cp2, int degree, float resolution, float low_resolution)
{
 ArrayList<PVector> low_sp1 = CalcuOpenSpline(cp1, degree, low_resolution);
 ArrayList<PVector> low_sp2 = CalcuOpenSpline(cp2, degree, low_resolution);
 PVector intersection_tt = GetPolylineIntersection_tt(low_sp1,low_sp2);
 if(intersection_tt==null){return null;}
 
 ArrayList<PVector> sp1 = CalcuOpenSpline(cp1, degree, resolution);
 ArrayList<PVector> sp2 = CalcuOpenSpline(cp2, degree, resolution);  
 ArrayList<PVector> f1 = FromPolyline_t(sp1, intersection_tt.x);
 ArrayList<PVector> f2 = FromPolyline_t(sp2, intersection_tt.y);   
 
 ArrayList<PVector> ret = new ArrayList<PVector>();
 if(f1!=null&&0<f1.size())
 {
   Collections.reverse(f1);
   ret.addAll(f1);
 }
 if(f2!=null&&0<f2.size()){ret.addAll(f2);}
 return ret;  
}