21 #include "RStarTree/RStarBoundingBox.h" 57 Visitor() : count(0), vResult(), sResult(), ContinueVisiting(true){};
60 vResult.push_back(leaf->leaf);
61 sResult.insert(leaf->leaf);
80 c[0] = (m_bound.edges[0].second + m_bound.edges[0].first) / 2.0;
81 c[1] = (m_bound.edges[1].second + m_bound.edges[1].first) / 2.0;
82 d[0] = (m_bound.edges[0].second - m_bound.edges[0].first) / 2.0;
83 d[1] = (m_bound.edges[1].second - m_bound.edges[1].first) / 2.0;
88 return m_bound.overlaps(node->bound);
94 C[0] = (leaf->bound.edges[0].second + leaf->bound.edges[0].first) / 2.0;
95 C[1] = (leaf->bound.edges[1].second + leaf->bound.edges[1].first) / 2.0;
96 D[0] = (leaf->bound.edges[0].second - leaf->bound.edges[0].first) / 2.0;
97 D[1] = (leaf->bound.edges[1].second - leaf->bound.edges[1].first) / 2.0;
99 for (
int i = 0; i < 2; ++i) {
102 t += ((c[i] - C[i]) * (c[i] - C[i])) / ((d[i] + D[i]) * (d[i] + D[i]));
113 c[0] = (m_bound.edges[0].second - m_bound.edges[0].first) / 2.0;
114 c[1] = (m_bound.edges[1].second - m_bound.edges[1].first) / 2.0;
142 std::vector<unsigned int>& badWireSum)
143 : fBound(b), fEps(), fMaxWidth(maxWidth), fWireDist(wireDist), fBadWireSum(badWireSum)
152 c.edges[0].first = c.edges[0].second = (b.edges[0].first + b.edges[0].second) / 2.0;
153 c.edges[1].first = c.edges[1].second = (b.edges[1].first + b.edges[1].second) / 2.0;
162 double bCenter0 = center(b).edges[0].first;
163 double bCenter1 = center(b).edges[1].first;
164 double tCenter0 = center().edges[0].first;
165 double tCenter1 = center().edges[1].first;
167 double bWidth =
std::abs(b.edges[1].second - b.edges[1].first);
168 double tWidth =
std::abs(fBound.edges[1].second - fBound.edges[1].first);
170 unsigned int wire1 = (
unsigned int)(tCenter0 / fWireDist + 0.5);
171 unsigned int wire2 = (
unsigned int)(bCenter0 / fWireDist + 0.5);
174 if (wire1 < fBadWireSum.size()) wire1 = fBadWireSum.size();
175 if (wire2 < fBadWireSum.size()) wire2 = fBadWireSum.size();
179 unsigned int wirestobridge =
lar::util::absDiff(fBadWireSum[wire1], fBadWireSum[wire2]);
180 double cmtobridge = wirestobridge * fWireDist;
182 double sim =
std::abs(tCenter0 - bCenter0) - cmtobridge;
185 if (
std::abs(tCenter0 - bCenter0) > 1
e-10) {
186 cmtobridge *=
std::abs((tCenter1 - bCenter1) / (tCenter0 - bCenter0));
188 double sim2 =
std::abs(tCenter1 - bCenter1) - cmtobridge;
192 double WFactor = (exp(4.6 * ((tWidth * tWidth) + (bWidth * bWidth)))) * k;
194 if (WFactor < 1.0) WFactor = 1.0;
195 if (WFactor > 6.25) WFactor = 6.25;
198 return (((sim) / (fEps[0] * fEps[0])) + ((sim2) / (fEps[1] * fEps[1] * (WFactor))) <= 1);
204 for (
int i = 0; i < 2; ++i) {
207 if (b.edges[i].first > c.edges[i].second) {
209 n.edges[i].first = n.edges[i].second = b.edges[i].first;
211 else if (b.edges[0].second < c.edges[0].first) {
213 n.edges[i].first = n.edges[i].second = b.edges[i].second;
217 n.edges[i].first = n.edges[i].second = c.edges[i].first;
221 n.edges[1].first -= fMaxWidth / 2.0;
222 n.edges[1].second += fMaxWidth / 2.0;
228 if (fBound.overlaps(node->bound))
return true;
232 return isNear(nearestPoint(node->bound));
234 bool operator()(
const RTree::Leaf*
const leaf)
const {
return isNear(leaf->bound); }
247 fEps = p.
get<
double>(
"eps");
248 fEps2 = p.
get<
double>(
"epstwo");
249 fMinPts = p.
get<
int>(
"minPts");
250 fClusterMethod = p.
get<
int>(
"Method");
251 fDistanceMetric = p.
get<
int>(
"Metric");
258 std::set<uint32_t> badChannels,
259 const std::vector<geo::WireID>& wireids)
261 if (wireids.size() && wireids.size() != allhits.size()) {
262 throw cet::exception(
"DBScanAlg") <<
"allhits size = " << allhits.size()
263 <<
" wireids size = " << wireids.size() <<
" do not match\n";
267 fpointId_to_clusterId.clear();
276 fBadChannels = badChannels;
280 fRTree.Remove(RTree::AcceptAny(), RTree::RemoveLeaf());
291 fWirePitch.push_back(plane.WirePitch());
294 if (fClusterMethod) {
296 unsigned int count = 0;
297 for (
unsigned int i = 0; i < fBadWireSum.size(); ++i) {
298 count += fBadChannels.count(i);
299 fBadWireSum[i] = count;
306 for (
unsigned int j = 0; j < allhits.size(); ++j) {
308 std::vector<double> p(dims);
313 p[0] = (allhits[j]->
WireID().Wire) * fWirePitch[allhits[j]->
WireID().Plane];
315 p[0] = (wireids[j].Wire) * fWirePitch[allhits[j]->
WireID().Plane];
316 p[1] = allhits[j]->PeakTime() * tickToDist;
317 p[2] = 2. * allhits[j]->RMS() * tickToDist;
320 if (p[2] > fMaxWidth) fMaxWidth = p[2];
324 if (fClusterMethod) {
326 dbsPoint pp(p[0], p[1], 0.0, p[2] / 2.0);
327 fRTree.Insert(j, pp.
bounds());
333 fpointId_to_clusterId.resize(fps.size(),
kNO_CLUSTER);
334 fnoise.resize(fps.size(),
false);
335 fvisited.resize(fps.size(),
false);
337 if (fClusterMethod) {
339 mf::LogInfo(
"DBscan") <<
"InitScan: hits RTree loaded with " << visitor.
count <<
" items.";
341 mf::LogInfo(
"DBscan") <<
"InitScan: hits vector size is " << fps.size();
359 double wire_dist = fWirePitch[0];
362 (
unsigned int)(v1[0] / wire_dist + 0.5);
363 unsigned int wire2 = (
unsigned int)(v2[0] / wire_dist + 0.5);
364 int wirestobridge = 0;
367 unsigned int wire = wire1;
372 for (
unsigned int i = wire1; i < wire2; i++) {
373 if (fBadChannels.find(i) != fBadChannels.end()) wirestobridge++;
376 double cmtobridge = wirestobridge * wire_dist;
378 return ((
std::abs(v2[0] - v1[0]) - cmtobridge) *
379 (
std::abs(v2[0] - v1[0]) - cmtobridge));
384 const std::vector<double> v2)
392 double wire_dist = fWirePitch[0];
395 (
unsigned int)(v1[0] / wire_dist + 0.5);
396 unsigned int wire2 = (
unsigned int)(v2[0] / wire_dist + 0.5);
397 int wirestobridge = 0;
400 unsigned int wire = wire1;
405 for (
unsigned int i = wire1; i < wire2; i++) {
406 if (fBadChannels.find(i) != fBadChannels.end()) wirestobridge++;
409 double cmtobridge = wirestobridge * wire_dist;
412 cmtobridge *=
std::abs((v2[1] - v1[1]) / (v2[0] - v1[0]));
417 return ((
std::abs(v2[1] - v1[1]) - cmtobridge) *
418 (
std::abs(v2[1] - v1[1]) - cmtobridge));
423 const std::vector<double> v2)
434 double WFactor = (exp(4.6 * ((v1[2] * v1[2]) + (v2[2] * v2[2])))) * k;
455 std::vector<unsigned int> ne;
457 for (
int unsigned j = 0; j < fsim.size(); j++) {
459 (((fsim[pid][j]) / (threshold * threshold)) +
460 ((fsim2[pid][j]) / (threshold2 * threshold2 * (fsim3[pid][j])))) < 1) {
471 int size = fps.size();
472 fsim.resize(size, std::vector<double>(size));
473 for (
int i = 0; i <
size; i++) {
474 for (
int j = i + 1; j <
size; j++) {
475 fsim[j][i] = fsim[i][j] = getSimilarity(fps[i], fps[j]);
483 int size = fps.size();
484 fsim2.resize(size, std::vector<double>(size));
485 for (
int i = 0; i <
size; i++) {
486 for (
int j = i + 1; j <
size; j++) {
487 fsim2[j][i] = fsim2[i][j] = getSimilarity2(fps[i], fps[j]);
495 int size = fps.size();
496 fsim3.resize(size, std::vector<double>(size));
498 for (
int i = 0; i <
size; i++) {
499 for (
int j = i + 1; j <
size; j++) {
500 fsim3[j][i] = fsim3[i][j] = getWidthFactor(fps[i], fps[j]);
511 switch (fClusterMethod) {
512 case 2:
return run_dbscan_cluster();
513 case 1:
return run_FN_cluster();
516 computeSimilarity2();
517 computeWidthFactor();
518 return run_FN_naive_cluster();
529 unsigned int cid = 0;
531 for (
size_t pid = 0;
pid < fps.size();
pid++) {
534 if (ExpandCluster(
pid, cid)) { cid++; }
541 fclusters.resize(cid);
542 for (
size_t y = 0;
y < fpointId_to_clusterId.size(); ++
y) {
551 unsigned int c = fpointId_to_clusterId[
y];
553 mf::LogWarning(
"DBscan") <<
"Point in cluster " << c <<
" when only " << cid
554 <<
" clusters wer found [0-" << cid - 1 <<
"]";
556 fclusters[c].push_back(
y);
559 mf::LogInfo(
"DBscan") <<
"DWM (R*-tree): Found " << cid <<
" clusters...";
560 for (
unsigned int c = 0; c < cid; ++c) {
562 <<
"Cluster " << c <<
":\t" << fclusters[c].size();
565 <<
"...and " << noise <<
" noise points.";
596 std::vector<unsigned int>& v = visitor.
vResult;
600 v.erase(std::remove(v.begin(), v.end(), point), v.end());
609 std::set<unsigned int>
seeds = RegionQuery(point);
612 if (seeds.size() < fMinPts) {
618 fpointId_to_clusterId[point] = clusterID;
620 fpointId_to_clusterId[*itr] = clusterID;
623 while (!seeds.empty()) {
624 unsigned int currentP = *(seeds.begin());
625 std::set<unsigned int> result = RegionQuery(currentP);
627 if (result.size() >= fMinPts) {
629 unsigned int resultP = *itr;
631 if (fpointId_to_clusterId[resultP] ==
kNO_CLUSTER ||
633 if (fpointId_to_clusterId[resultP] ==
kNO_CLUSTER) { seeds.insert(resultP); }
634 fpointId_to_clusterId[resultP] = clusterID;
638 seeds.erase(currentP);
653 unsigned int cid = 0;
655 for (
size_t pid = 0;
pid < fps.size();
pid++) {
657 if (!fvisited[
pid]) {
659 fvisited[pid] =
true;
661 std::vector<unsigned int> ne = RegionQuery_vector(pid);
664 if (ne.size() < fMinPts) { fnoise[pid] =
true; }
668 std::vector<unsigned int> c;
671 fpointId_to_clusterId[pid] = cid;
673 for (
size_t i = 0; i < ne.size(); ++i) {
674 unsigned int nPid = ne[i];
677 if (!fvisited[nPid]) {
678 fvisited[nPid] =
true;
680 std::vector<unsigned int> ne1 = RegionQuery_vector(nPid);
682 if (ne1.size() >= fMinPts) {
686 for (
size_t i = 0; i < ne1.size(); ++i) {
688 ne.push_back(ne1[i]);
696 fpointId_to_clusterId[nPid] = cid;
700 fclusters.push_back(c);
710 for (
size_t y = 0;
y < fpointId_to_clusterId.size(); ++
y) {
713 mf::LogInfo(
"DBscan") <<
"FindNeighbors (R*-tree): Found " << cid <<
" clusters...";
714 for (
unsigned int c = 0; c < cid; ++c) {
716 <<
"Cluster " << c <<
":\t" << fclusters[c].size();
719 <<
"...and " << noise <<
" noise points.";
730 unsigned int cid = 0;
732 for (
size_t pid = 0;
pid < fps.size(); ++
pid) {
734 if (!fvisited[
pid]) {
736 fvisited[pid] =
true;
738 std::vector<unsigned int> ne = findNeighbors(pid, fEps, fEps2);
741 if (ne.size() < fMinPts) { fnoise[pid] =
true; }
745 std::vector<unsigned int> c;
748 fpointId_to_clusterId[pid] = cid;
750 for (
size_t i = 0; i < ne.size(); ++i) {
751 unsigned int nPid = ne[i];
754 if (!fvisited[nPid]) {
755 fvisited[nPid] =
true;
757 std::vector<unsigned int> ne1 = findNeighbors(nPid, fEps, fEps2);
759 if (ne1.size() >= fMinPts) {
763 for (
unsigned int i = 0; i < ne1.size(); i++) {
765 ne.push_back(ne1[i]);
773 fpointId_to_clusterId[nPid] = cid;
777 fclusters.push_back(c);
786 for (
size_t y = 0;
y < fpointId_to_clusterId.size(); ++
y) {
789 mf::LogInfo(
"DBscan") <<
"FindNeighbors (naive): Found " << cid <<
" clusters...";
790 for (
unsigned int c = 0; c < cid; ++c) {
792 <<
"Cluster " << c <<
":\t" << fclusters[c].size() <<
" points";
795 <<
"...and " << noise <<
" noise points.";
details::range_type< T > Iterate() const
Initializes the specified ID with the ID of the first cryostat.
MaybeLogger_< ELseverityLevel::ELsev_info, true > LogVerbatim
double getSimilarity(const std::vector< double > v1, const std::vector< double > v2)
const unsigned int kNO_CLUSTER
Functions to help with numbers.
Utilities related to art service access.
void computeWidthFactor()
MaybeLogger_< ELseverityLevel::ELsev_info, false > LogInfo
bool operator()(const RTree::Leaf *const leaf) const
Declaration of signal hit object.
AcceptFindNeighbors(const BoundingBox &b, double eps, double eps2, double maxWidth, double wireDist, std::vector< unsigned int > &badWireSum)
double Temperature() const
In kelvin.
std::vector< unsigned int > & fBadWireSum
static const BoundingBox EmptyBoundingBox
constexpr auto abs(T v)
Returns the absolute value of the argument.
Cluster finding and building.
void run_dbscan_cluster()
std::set< unsigned int > RegionQuery(unsigned int point)
void run_FN_naive_cluster()
bool isNear(const BoundingBox &b) const
unsigned int Nchannels() const
Returns the number of TPC readout channels in the detector.
double Efield(unsigned int planegap=0) const
kV/cm
bool operator()(const RTree::Leaf *const leaf) const
decltype(auto) constexpr size(T &&obj)
ADL-aware version of std::size.
auto vector(Vector const &v)
Returns a manipulator which will print the specified array.
const unsigned int kNOISE_CLUSTER
IDparameter< geo::WireID > WireID
Member type of validated geo::WireID parameter.
RTree::BoundingBox BoundingBox
std::set< unsigned int > sResult
const BoundingBox & fBound
void operator()(const RTree::Leaf *const leaf)
BoundingBox bounds() const
T get(std::string const &key) const
Geometry information for a single wire plane.The plane is represented in the geometry by a solid whic...
const BoundingBox & m_bound
BoundingBox center(const BoundingBox &b) const
bool operator()(const RTree::Node *const node) const
std::vector< unsigned int > vResult
double DriftVelocity(double efield=0., double temperature=0.) const
cm/us
The data type to uniquely identify a TPC.
DBScanAlg(fhicl::ParameterSet const &pset)
double getWidthFactor(const std::vector< double > v1, const std::vector< double > v2)
bool operator()(const RTree::Node *const node) const
void computeSimilarity2()
std::vector< unsigned int > findNeighbors(unsigned int pid, double threshold, double threshold2)
AcceptEllipse(const BoundingBox &b, double r1, double r2)
std::vector< TrajPoint > seeds
std::vector< unsigned int > RegionQuery_vector(unsigned int point)
void InitScan(const detinfo::DetectorClocksData &clockData, const detinfo::DetectorPropertiesData &detProp, const std::vector< art::Ptr< recob::Hit >> &allhits, std::set< uint32_t > badChannels, const std::vector< geo::WireID > &wireids=std::vector< geo::WireID >())
bool ExpandCluster(unsigned int point, unsigned int clusterID)
Contains all timing reference information for the detector.
constexpr auto absDiff(A const &a, B const &b)
Returns the absolute value of the difference between two values.
MaybeLogger_< ELseverityLevel::ELsev_warning, false > LogWarning
double getSimilarity2(const std::vector< double > v1, const std::vector< double > v2)
double sampling_rate(DetectorClocksData const &data)
Returns the period of the TPC readout electronics clock.
BoundingBox center() const
art framework interface to geometry description
cet::coded_exception< error, detail::translate > exception
const bool ContinueVisiting
BoundingBox nearestPoint(const BoundingBox &b) const