This problem can be solved by using a greedy selection algorithm which combines information from both criteria mentioned above to select tracts.
Two class definitions are used to hold information associated with tracts and triangles:
struct Tract {
glm::vec3 start;
glm::vec3 end;
uint32_t startTriangleInd;
uint32_t endTriangleInd;
// any other necessary information
};
struct Triangle {
std::vector<uint32_t> vertexInds;
// any other necessary information
};
Imagine that all tracts and triangles information are put inside vectors respectively:
std::vector<Tract> allTracts;
std::vector<Triangle> allTriangles;
Here is the general scheme of algorithm which may suit your needs:
std::set<uint32_t> coveredTriangles;
std::vector<Tract> selectedTracts;
std::priority_queue<std::pair<double, uint32_t>> pq; // priority queue for selection based on criterion
// Initialise the priority queue with tract indices ranked by their impact on coverage and dispersion
for (size_t i = 0; i < allTracts.size(); ++i) {
double priority = calculatePriority(allTracts[i], allTriangles);
pq.push({priority, i});
}
// Selection process
while (!pq.empty() && selectedTracts.size() < desiredTractNum) {
uint32_t tractInd = pq.top().second;
pq.pop();
Tract& curTract = allTracts[tractInd];
// Check if adding this tract does not result in significant decrease of dispersion
if (isFulfillingDispersionCriterion(curTract, selectedTracts)) {
selectedTracts.push_back(curTract);
// consider its start and end triangle as covered
coveredTriangles.insert(curTract.startTriangleInd);
coveredTriangles.insert(curTract.endTriangleInd);
}
}
The calculatePriority
function should calculate the ranking of a tract according to both criteria A and B (e.g., by counting the number of uncovered triangles that the given tract would cover and considering the dispersion). The isFulfillingDispersionCriterion
function should check if the selected tract provides a maximum dispersion for the selected set of tracts.
While this algorithm is easy to follow and implement, it might not always produce the optimal solution, because the initial ranking might not be ideal for maintaining the dispersion criterion. However, trying to satisfy both criterium as the same time is a complex problem which might not have an efficient exact solution, and heuristics or approximations are often used in practice.