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;
}
この記事が気に入ったらサポートをしてみませんか?