Tôi nghĩ bạn có thể xem xét sử dụng thuật toán breadth first search.
Ý tưởng cơ bản là bạn lặp qua từng hàng và cột trong hình ảnh và nếu bạn chưa truy cập nút (nút là hàng và cột có pixel màu), thì bạn sẽ chạy chiều rộng tìm kiếm đầu tiên. Bạn sẽ ghé thăm mỗi nút bạn có thể có thể, và theo dõi các điểm tối đa và min cho đối tượng.
Dưới đây là một số mã C++ mẫu (chưa được kiểm tra):
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
// used to transition from given row, col to each of the
// 8 different directions
int dr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dc[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
// WHITE or COLORED cells
const int WHITE = 0;
const int COLORED = 1;
// number of rows and columns
int nrows = 2000;
int ncols = 2000;
// assume G is the image
int G[2000][2000];
// the "visited array"
bool vis[2000][2000];
// get distance between 2 points
inline double getdist(double x1, double y1, double x2, double y2) {
double d1 = x1 - x2;
double d2 = y1 - y2;
return sqrt(d1*d1+d2*d2);
}
// this function performs the breadth first search
double bfs(int startRow, int startCol) {
queue<int> q;
q.push(startRow);
q.push(startCol);
vector< pair< int, int > > points;
while(!q.empty()) {
int r = q.front();
q.pop();
int c = q.front();
q.pop();
// already visited?
if (vis[r][c])
continue;
points.push_back(make_pair(r,c));
vis[r][c] = true;
// try all eight directions
for(int i = 0; i < 8; ++i) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr < 0 || nr >= nrows || nc < 0 || nc >= ncols)
continue; // out of bounds
// push next node on queue
q.push(nr);
q.push(nc);
}
}
// the distance is maximum difference between any 2 points encountered in the BFS
double diff = 0;
for(int i = 0; i < (int)points.size(); ++i) {
for(int j = i+1; j < (int)points.size(); ++j) {
diff = max(diff,getdist(points[i].first,points[i].second,points[j].first,points[j].second));
}
}
return diff;
}
int main() {
vector<double> lengths;
memset(vis,false,sizeof vis);
for(int r = 0; r < nrows; ++r) {
for(int c = 0; c < ncols; ++c) {
if (G[r][c] == WHITE)
continue; // we don't care about cells without objects
if (vis[r][c])
continue; // we've already processed this object
// find the length of this object
double len = bfs(r,c);
lengths.push_back(len);
}
}
return 0;
}
Vấn đề nhỏ gọn - trông giống như gạo? Hạt giống? –
Dung dịch cần phải nhanh như thế nào? Bạn cũng cần một giải pháp chính xác? – shuttle87
@Mark B. - gạo thực sự, @ shuttle87 - không phải chính xác 100%. – Jacek