//lines between a1 and b1, a2 and b2
// intersection: interpolation parameter t=0...1 on line 1
// t<0 or t>1 means there is no intersection.
float intersectionAt(Vector a1,Vector b1,Vector a2,Vector b2){
if ((max(a1.x,b1.x)<min(a2.x,b2.x))||min(a1.x,b1.x)>max(a2.x,b2.x)) return -1; // check intersection of bounding rectangles
if ((max(a1.y,b1.y)<min(a2.y,b2.y))||min(a1.y,b1.y)>max(a2.y,b2.y)) return -1;
Vector direction=sub(b2,a2);
float aDistance=direction.cross(sub(a1,a2));
float bDistance=direction.cross(sub(b1,a2));
if((aDistance>0)&&(bDistance>0))return -1; // check if that really crosses
if((aDistance<0)&&(bDistance<0))return -1;
float t=aDistance/(aDistance-bDistance); // intersection parameter
if((t>1)||(t<0)) return -1; // is intersection on line 1 between endpoints ?
Vector inter=interpolate(t,a1,b1); // is intersection between endpoints of line 2 ?
if((inter.x<max(a2.x,b2.x))&&(inter.x>min(a2.x,b2.x))) return t; // yes, if inside bounding rectangle
if((inter.y<max(a2.y,b2.y))&&(inter.y>min(a2.y,b2.y))) return t; // attention of vertical or horizontal lines
return -1;
}
// intersections between line a1-b1 and set of lines, put line pieces into Grid gridCombi
void intersections(Grid gridCombi, Line one,Line[] lines){
Vector a1=one.endPointA.vec;
Vector b1=one.endPointB.vec;
float t;
float[] times=new float[0];
for (int i=0;i<lines.length;i++){
t=intersectionAt(a1,b1,lines[i].endPointA.vec,lines[i].endPointB.vec);
if(t>0) times=append(times,t);
}
times=sort(times);
times=append(times,1.); // add endpoint
Vector start,end=a1;
for (int i=0;i<times.length;i++){
start=end;
end=interpolate(times[i],a1,b1);
if(!start.equal(end)) gridCombi.addGridLine(start,end); // we need two different endpoints
}
}
// intersections between gridOne and gridTwo - lines of gridTwo are cut up by lines of gridOne
void cutup(Grid gridCombi,Line[] gridOneLines, Line[] gridTwoLines){
for(int i=0;i<gridOneLines.length;i++){
intersections(gridCombi,gridOneLines[i],gridTwoLines);
}
}
// combination of two grids to get a new grid
Grid combination(Grid gridOne,Grid gridTwo){
Grid gridCombi=new Grid();
Line[] gridOneLines=gridOne.gridLines.lines;
Line[] gridTwoLines=gridTwo.gridLines.lines;
cutup(gridCombi,gridOneLines,gridTwoLines);
cutup(gridCombi,gridTwoLines,gridOneLines);
return gridCombi;
}
Like this:
Like Loading...
Related
Problem patched the 17th november:
There may be a bug somewhere here. Sometimes this tries to generate lines with the same “start” and “end” Vectors, crashing the program. To get results I now have it check that they are different before creating a line segment using
if(!start.equal(end)) gridCombi.addGridLine(start,end); // we need two different endpoints
in “void intersections(…”