Twoim założeniem niekoniecznie jest znalezienie komórek, ale linie, które przecinają na tej siatce.
Na przykład robiąc zdjęcie nie możemy wyróżnić komórek, ale linie przecinającej się siatki:
To pokazuje, że jeśli przecina linię siatki, komórki po obu stronach tej linii są wypełnione.
Możesz użyć algorytmu przecięcia, aby sprawdzić, czy linia zmiennoprzecinkowa przecina je, skalując punkty do pikseli. Jeśli masz współczynnik pływających współrzędnych: pikseli wynoszący 1,0: 1, to jesteś posortowany i możesz po prostu przetłumaczyć go bezpośrednio. Za pomocą algorytmu przecięcia segmentu linii możesz sprawdzić, czy twoja lewa dolna linia (1,7) (2,7) przecina się z twoją linią (1.3,6.2) (6.51,2.9). http://alienryderflex.com/intersect/
Konieczne będzie tłumaczenie z c na C #, ale pomysł można uzyskać z tego artykułu. Wstawię poniższy kod na wypadek, gdyby link się zepsuł.
// public domain function by Darel Rex Finley, 2006
// Determines the intersection point of the line defined by points A and B with the
// line defined by points C and D.
//
// Returns YES if the intersection point was found, and stores that point in X,Y.
// Returns NO if there is no determinable intersection point, in which case X,Y will
// be unmodified.
bool lineIntersection(
double Ax, double Ay,
double Bx, double By,
double Cx, double Cy,
double Dx, double Dy,
double *X, double *Y) {
double distAB, theCos, theSin, newX, ABpos ;
// Fail if either line is undefined.
if (Ax==Bx && Ay==By || Cx==Dx && Cy==Dy) return NO;
// (1) Translate the system so that point A is on the origin.
Bx-=Ax; By-=Ay;
Cx-=Ax; Cy-=Ay;
Dx-=Ax; Dy-=Ay;
// Discover the length of segment A-B.
distAB=sqrt(Bx*Bx+By*By);
// (2) Rotate the system so that point B is on the positive X axis.
theCos=Bx/distAB;
theSin=By/distAB;
newX=Cx*theCos+Cy*theSin;
Cy =Cy*theCos-Cx*theSin; Cx=newX;
newX=Dx*theCos+Dy*theSin;
Dy =Dy*theCos-Dx*theSin; Dx=newX;
// Fail if the lines are parallel.
if (Cy==Dy) return NO;
// (3) Discover the position of the intersection point along line A-B.
ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy);
// (4) Apply the discovered position to line A-B in the original coordinate system.
*X=Ax+ABpos*theCos;
*Y=Ay+ABpos*theSin;
// Success.
return YES; }
Jeśli chcesz dowiedzieć się tylko, kiedy (i gdzie) przecinają się segmenty linii, możesz zmodyfikować funkcję w następujący sposób:
// public domain function by Darel Rex Finley, 2006
// Determines the intersection point of the line segment defined by points A and B
// with the line segment defined by points C and D.
//
// Returns YES if the intersection point was found, and stores that point in X,Y.
// Returns NO if there is no determinable intersection point, in which case X,Y will
// be unmodified.
bool lineSegmentIntersection(
double Ax, double Ay,
double Bx, double By,
double Cx, double Cy,
double Dx, double Dy,
double *X, double *Y) {
double distAB, theCos, theSin, newX, ABpos ;
// Fail if either line segment is zero-length.
if (Ax==Bx && Ay==By || Cx==Dx && Cy==Dy) return NO;
// Fail if the segments share an end-point.
if (Ax==Cx && Ay==Cy || Bx==Cx && By==Cy
|| Ax==Dx && Ay==Dy || Bx==Dx && By==Dy) {
return NO; }
// (1) Translate the system so that point A is on the origin.
Bx-=Ax; By-=Ay;
Cx-=Ax; Cy-=Ay;
Dx-=Ax; Dy-=Ay;
// Discover the length of segment A-B.
distAB=sqrt(Bx*Bx+By*By);
// (2) Rotate the system so that point B is on the positive X axis.
theCos=Bx/distAB;
theSin=By/distAB;
newX=Cx*theCos+Cy*theSin;
Cy =Cy*theCos-Cx*theSin; Cx=newX;
newX=Dx*theCos+Dy*theSin;
Dy =Dy*theCos-Dx*theSin; Dx=newX;
// Fail if segment C-D doesn't cross line A-B.
if (Cy<0. && Dy<0. || Cy>=0. && Dy>=0.) return NO;
// (3) Discover the position of the intersection point along line A-B.
ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy);
// Fail if segment C-D crosses line A-B outside of segment A-B.
if (ABpos<0. || ABpos>distAB) return NO;
// (4) Apply the discovered position to line A-B in the original coordinate system.
*X=Ax+ABpos*theCos;
*Y=Ay+ABpos*theSin;
// Success.
return YES; }