std::pair<WCPointCloud<double>::WCPoint, WCPointCloud<double>::WCPoint> WCPPID::PR3DCluster::get_highest_lowest_wcps(
    int flag)
{
    ToyPointCloud* temp_point_cloud = point_cloud;
    if (flag == 2) {
        temp_point_cloud = point_cloud_steiner;
    }

    WCP::WCPointCloud<double>& cloud = temp_point_cloud->get_cloud();
    WCPointCloud<double>::WCPoint highest_wcp = cloud.pts[0];
    WCPointCloud<double>::WCPoint lowest_wcp = cloud.pts[0];

    bool flag_init = false;

    for (size_t i = 0; i < cloud.pts.size(); i++) {
        if (excluded_points.find(i) != excluded_points.end()) continue;
        if (!flag_init) {
            highest_wcp = cloud.pts[i];
            lowest_wcp = cloud.pts[i];
            flag_init = true;
        }
        else {
            if (cloud.pts[i].y > highest_wcp.y) highest_wcp = cloud.pts[i];
            if (cloud.pts[i].y < lowest_wcp.y) lowest_wcp = cloud.pts[i];
        }
    }
    return std::make_pair(highest_wcp, lowest_wcp);
}

std::pair<WCPointCloud<double>::WCPoint, WCPointCloud<double>::WCPoint> WCPPID::PR3DCluster::get_front_back_wcps(
    int flag)
{
    ToyPointCloud* temp_point_cloud = point_cloud;
    if (flag == 2) {
        temp_point_cloud = point_cloud_steiner;
    }
    WCP::WCPointCloud<double>& cloud = temp_point_cloud->get_cloud();
    WCPointCloud<double>::WCPoint highest_wcp = cloud.pts[0];
    WCPointCloud<double>::WCPoint lowest_wcp = cloud.pts[0];
    bool flag_init = false;
    for (size_t i = 0; i < cloud.pts.size(); i++) {
        if (excluded_points.find(i) != excluded_points.end()) continue;
        if (!flag_init) {
            highest_wcp = cloud.pts[i];
            lowest_wcp = cloud.pts[i];
            flag_init = true;
        }
        else {
            if (cloud.pts[i].z > highest_wcp.z) highest_wcp = cloud.pts[i];
            if (cloud.pts[i].z < lowest_wcp.z) lowest_wcp = cloud.pts[i];
        }
    }
    return std::make_pair(highest_wcp, lowest_wcp);
}

std::pair<WCPointCloud<double>::WCPoint, WCPointCloud<double>::WCPoint> WCPPID::PR3DCluster::get_earliest_latest_wcps(
    int flag)
{
    ToyPointCloud* temp_point_cloud = point_cloud;
    if (flag == 2) {
        temp_point_cloud = point_cloud_steiner;
    }
    WCP::WCPointCloud<double>& cloud = temp_point_cloud->get_cloud();
    WCPointCloud<double>::WCPoint highest_wcp = cloud.pts[0];
    WCPointCloud<double>::WCPoint lowest_wcp = cloud.pts[0];
    bool flag_init = false;
    for (size_t i = 0; i < cloud.pts.size(); i++) {
        if (excluded_points.find(i) != excluded_points.end()) continue;
        if (!flag_init) {
            highest_wcp = cloud.pts[i];
            lowest_wcp = cloud.pts[i];
            flag_init = true;
        }
        else {
            if (cloud.pts[i].x > highest_wcp.x) highest_wcp = cloud.pts[i];
            if (cloud.pts[i].x < lowest_wcp.x) lowest_wcp = cloud.pts[i];
        }
    }
    return std::make_pair(lowest_wcp, highest_wcp);
}

std::vector<std::vector<WCPointCloud<double>::WCPoint>> WCPPID::PR3DCluster::get_extreme_wcps(
    int flag, std::map<int, SMGCSelection>* old_time_mcells_map)
{
    ToyPointCloud* temp_point_cloud = point_cloud;
    if (flag == 2) {
        temp_point_cloud = point_cloud_steiner;
    }
    WCP::WCPointCloud<double>& cloud = temp_point_cloud->get_cloud();

    std::vector<int> all_indices;
    if (old_time_mcells_map == 0) {
        for (size_t i = 0; i < cloud.pts.size(); i++) {
            all_indices.push_back(i);
        }
    }
    else {
        // scan
        for (size_t i = 0; i < cloud.pts.size(); i++) {
            int time_slice = cloud.pts[i].mcell->GetTimeSlice();
            bool flag_add = false;

            if (old_time_mcells_map->find(time_slice) != old_time_mcells_map->end()) {
                for (auto it1 = (*old_time_mcells_map)[time_slice].begin();
                     it1 != (*old_time_mcells_map)[time_slice].end(); it1++) {
                    SlimMergeGeomCell* mcell = *it1;
                    int u1_low_index = mcell->get_uwires().front()->index();
                    int u1_high_index = mcell->get_uwires().back()->index();

                    int v1_low_index = mcell->get_vwires().front()->index();
                    int v1_high_index = mcell->get_vwires().back()->index();

                    int w1_low_index = mcell->get_wwires().front()->index();
                    int w1_high_index = mcell->get_wwires().back()->index();

                    if (cloud.pts[i].index_u <= u1_high_index && cloud.pts[i].index_u >= u1_low_index &&
                        cloud.pts[i].index_v <= v1_high_index && cloud.pts[i].index_v >= v1_low_index &&
                        cloud.pts[i].index_w <= w1_high_index && cloud.pts[i].index_w >= w1_low_index) {
                        flag_add = true;
                        break;
                    }
                }
            }
            if (flag_add) {
                all_indices.push_back(i);
            }
        }
    }

    std::vector<std::vector<WCPointCloud<double>::WCPoint>> out_vec_wcps;
    if (all_indices.size() == 0) {
        return out_vec_wcps;
    }

    Calc_PCA();
    WCPointCloud<double>::WCPoint wcps[8];
    for (int i = 0; i != 8; i++) {
        wcps[i] = cloud.pts[all_indices.at(0)];
    }
    Vector main_axis = get_PCA_axis(0);
    if (main_axis.y < 0) {
        main_axis.x = -main_axis.x;
        main_axis.y = -main_axis.y;
        main_axis.z = -main_axis.z;
    }
    double high_value = wcps[0].x * main_axis.x + wcps[0].y * main_axis.y + wcps[0].z * main_axis.z;
    double low_value = wcps[1].x * main_axis.x + wcps[1].y * main_axis.y + wcps[1].z * main_axis.z;

    bool flag_init = false;

    for (size_t i = 0; i < all_indices.size(); i++) {
        if (excluded_points.find(all_indices.at(i)) != excluded_points.end()) continue;
        if (!flag_init) {
            for (int j = 0; j != 8; j++) {
                wcps[j] = cloud.pts[all_indices.at(i)];
            }
            high_value = wcps[0].x * main_axis.x + wcps[0].y * main_axis.y + wcps[0].z * main_axis.z;
            low_value = wcps[1].x * main_axis.x + wcps[1].y * main_axis.y + wcps[1].z * main_axis.z;
            flag_init = true;
        }
        else {
            double value = cloud.pts[all_indices.at(i)].x * main_axis.x + cloud.pts[all_indices.at(i)].y * main_axis.y +
                           cloud.pts[all_indices.at(i)].z * main_axis.z;
            if (value > high_value) {
                wcps[0] = cloud.pts[all_indices.at(i)];
                high_value = value;
            }
            if (value < low_value) {
                wcps[1] = cloud.pts[all_indices.at(i)];
                low_value = value;
            }
            // top down
            if (cloud.pts[all_indices.at(i)].y > wcps[2].y) wcps[2] = cloud.pts[all_indices.at(i)];
            if (cloud.pts[all_indices.at(i)].y < wcps[3].y) wcps[3] = cloud.pts[all_indices.at(i)];

            // front back
            if (cloud.pts[all_indices.at(i)].z > wcps[4].z) wcps[4] = cloud.pts[all_indices.at(i)];
            if (cloud.pts[all_indices.at(i)].z < wcps[5].z) wcps[5] = cloud.pts[all_indices.at(i)];

            // early late
            if (cloud.pts[all_indices.at(i)].x > wcps[6].x) wcps[6] = cloud.pts[all_indices.at(i)];
            if (cloud.pts[all_indices.at(i)].x < wcps[7].x) wcps[7] = cloud.pts[all_indices.at(i)];
        }
    }

    {
        // first extreme along the main axis
        std::vector<WCPointCloud<double>::WCPoint> saved_wcps;
        saved_wcps.push_back(wcps[0]);
        out_vec_wcps.push_back(saved_wcps);
    }

    {
        // second extreme along the main axis
        std::vector<WCPointCloud<double>::WCPoint> saved_wcps;
        saved_wcps.push_back(wcps[1]);
        out_vec_wcps.push_back(saved_wcps);
    }

    // std::cout << std::endl;
    for (int i = 2; i != 8; i++) {
        // if (cluster_id==16)
        // std::cout << i << " C " << wcps[i].x/units::cm << " " << wcps[i].y/units::cm << " " << wcps[i].z/units::cm <<
        // std::endl;

        bool flag_save = true;
        for (size_t j = 0; j != out_vec_wcps.size(); j++) {
            double dis =
                sqrt(pow(out_vec_wcps[j].at(0).x - wcps[i].x, 2) + pow(out_vec_wcps[j].at(0).y - wcps[i].y, 2) +
                     pow(out_vec_wcps[j].at(0).z - wcps[i].z, 2));
            if (dis < 5 * units::cm) {
                out_vec_wcps.at(j).push_back(wcps[i]);
                flag_save = false;
                break;
            }
        }

        if (flag_save) {
            std::vector<WCPointCloud<double>::WCPoint> saved_wcps;
            saved_wcps.push_back(wcps[i]);
            out_vec_wcps.push_back(saved_wcps);
        }
    }

    return out_vec_wcps;
}

std::pair<WCPointCloud<double>::WCPoint, WCPointCloud<double>::WCPoint> WCPPID::PR3DCluster::get_main_axis_wcps(
    int flag)
{
    ToyPointCloud* temp_point_cloud = point_cloud;
    if (flag == 2) {
        temp_point_cloud = point_cloud_steiner;
    }

    WCP::WCPointCloud<double>& cloud = temp_point_cloud->get_cloud();
    Calc_PCA();
    WCPointCloud<double>::WCPoint highest_wcp = cloud.pts[0];
    WCPointCloud<double>::WCPoint lowest_wcp = cloud.pts[0];
    Vector main_axis = get_PCA_axis(0);
    if (main_axis.y < 0) {
        main_axis.x = -main_axis.x;
        main_axis.y = -main_axis.y;
        main_axis.z = -main_axis.z;
    }

    double high_value = highest_wcp.x * main_axis.x + highest_wcp.y * main_axis.y + highest_wcp.z * main_axis.z;
    double low_value = lowest_wcp.x * main_axis.x + lowest_wcp.y * main_axis.y + lowest_wcp.z * main_axis.z;

    bool flag_init = false;

    for (size_t i = 0; i < cloud.pts.size(); i++) {
        if (excluded_points.find(i) != excluded_points.end()) continue;
        if (!flag_init) {
            highest_wcp = cloud.pts[i];
            lowest_wcp = cloud.pts[i];
            high_value = highest_wcp.x * main_axis.x + highest_wcp.y * main_axis.y + highest_wcp.z * main_axis.z;
            low_value = lowest_wcp.x * main_axis.x + lowest_wcp.y * main_axis.y + lowest_wcp.z * main_axis.z;
            flag_init = true;
        }
        else {
            double value = cloud.pts[i].x * main_axis.x + cloud.pts[i].y * main_axis.y + cloud.pts[i].z * main_axis.z;
            if (value > high_value) {
                highest_wcp = cloud.pts[i];
                high_value = value;
            }

            if (value < low_value) {
                lowest_wcp = cloud.pts[i];
                low_value = value;
            }
        }
    }
    return std::make_pair(highest_wcp, lowest_wcp);
}

WCP::WCPointCloud<double>::WCPoint WCPPID::PR3DCluster::get_local_extension(WCP::WCPointCloud<double>::WCPoint wcp,
                                                                            int flag)
{
    Create_point_cloud();

    ToyPointCloud* temp_point_cloud = point_cloud;
    if (flag == 2) {
        temp_point_cloud = point_cloud_steiner;
    }
    WCP::Point p(wcp.x, wcp.y, wcp.z);

    TVector3 dir1 = VHoughTrans(p, 10 * units::cm);
    dir1 *= (-1);
    TVector3 drift_dir(1, 0, 0);

    if (fabs(dir1.Angle(drift_dir) / 3.1415926 * 180. - 90) < 7.5) return wcp;

    double max_val = 0;
    std::vector<WCP::WCPointCloud<double>::WCPoint> wcps = temp_point_cloud->get_closest_wcpoints(p, 10 * units::cm);
    for (size_t i = 0; i != wcps.size(); i++) {
        double val =
            dir1.X() * (wcps.at(i).x - p.x) + dir1.Y() * (wcps.at(i).y - p.y) + dir1.Z() * (wcps.at(i).z - p.z);
        if (val > max_val) {
            max_val = val;
            wcp = wcps.at(i);
        }
    }

    return wcp;
}

int WCPPID::PR3DCluster::get_num_outside_range_points(int flag)
{
    Create_point_cloud();

    ToyPointCloud* temp_point_cloud = point_cloud;
    if (flag == 2) {
        temp_point_cloud = point_cloud_steiner;
    }
    //  std::cout << temp_point_cloud << std::endl;
    WCP::WCPointCloud<double>& cloud = temp_point_cloud->get_cloud();

    double min_x = 1e9, max_x = -1e9;
    double min_u = 1e9, max_u = -1e9;
    double min_v = 1e9, max_v = -1e9;
    double min_w = 1e9, max_w = -1e9;
    for (auto it = path_wcps.begin(); it != path_wcps.end(); it++) {
        if ((*it).x < min_x) min_x = (*it).x;
        if ((*it).x > max_x) max_x = (*it).x;
        if ((*it).index_u < min_u) min_u = (*it).index_u;
        if ((*it).index_u > max_u) max_u = (*it).index_u;
        if ((*it).index_v < min_v) min_v = (*it).index_v;
        if ((*it).index_v > max_v) max_v = (*it).index_v;
        if ((*it).index_w < min_w) min_w = (*it).index_w;
        if ((*it).index_w > max_w) max_w = (*it).index_w;
    }

    int num = 0;
    for (size_t i = 0; i < cloud.pts.size(); i++) {
        if (cloud.pts[i].index_u > max_u || cloud.pts[i].index_u < min_u || cloud.pts[i].index_v > max_v ||
            cloud.pts[i].index_v < min_v || cloud.pts[i].index_w > max_w || cloud.pts[i].index_w < min_w ||
            cloud.pts[i].x > max_x || cloud.pts[i].x < min_x)
            num++;
    }

    //  std::cout << min_u << " " << max_u << " " << min_x << " " << max_x << " " << min_v << " " << max_v << " " <<
    //  min_w << " " << max_w << std::endl;
    return num;
}

std::pair<WCP::WCPointCloud<double>::WCPoint, WCP::WCPointCloud<double>::WCPoint>
WCPPID::PR3DCluster::get_two_boundary_wcps(int flag, bool flag_cosmic)
{
    Create_point_cloud();

    ToyPointCloud* temp_point_cloud = point_cloud;
    if (flag == 2) {
        temp_point_cloud = point_cloud_steiner;
    }
    //  std::cout << temp_point_cloud << std::endl;
    WCP::WCPointCloud<double>& cloud = temp_point_cloud->get_cloud();
    if (cloud.pts.size() == 1) return std::make_pair(cloud.pts[0], cloud.pts[0]);
    // std::cout << cloud.pts.size() << " " << flag << std::endl;
    WCPointCloud<double>::WCPoint extreme_wcp[14];

    Calc_PCA();
    Vector main_axis = get_PCA_axis(0);
    Vector second_axis = get_PCA_axis(1);
    double values[4];

    bool flag_init = false;
    for (size_t i = 0; i < cloud.pts.size(); i++) {
        if (cloud.pts[i].mcell == 0) continue;
        if (cloud.pts[i].mcell->Estimate_total_charge() < 1500) continue;
        if (excluded_points.find(i) != excluded_points.end()) continue;
        if (!flag_init) {
            flag_init = true;
            for (int j = 0; j != 14; j++) {
                extreme_wcp[j] = cloud.pts[i];
            }
            values[0] =
                extreme_wcp[0].x * main_axis.x + extreme_wcp[0].y * main_axis.y + extreme_wcp[0].z * main_axis.z;
            values[1] =
                extreme_wcp[1].x * main_axis.x + extreme_wcp[1].y * main_axis.y + extreme_wcp[1].z * main_axis.z;
            values[2] =
                extreme_wcp[2].x * second_axis.x + extreme_wcp[2].y * second_axis.y + extreme_wcp[2].z * second_axis.z;
            values[3] =
                extreme_wcp[3].x * second_axis.x + extreme_wcp[3].y * second_axis.y + extreme_wcp[3].z * second_axis.z;
        }
        else {
            // main axis points
            double value = cloud.pts[i].x * main_axis.x + cloud.pts[i].y * main_axis.y + cloud.pts[i].z * main_axis.z;
            if (value > values[0]) {
                values[0] = value;
                extreme_wcp[0] = cloud.pts[i];
            }
            if (value < values[1]) {
                values[1] = value;
                extreme_wcp[1] = cloud.pts[i];
            }
            // second axis points
            value = cloud.pts[i].x * second_axis.x + cloud.pts[i].y * second_axis.y + cloud.pts[i].z * second_axis.z;
            if (value > values[2]) {
                values[2] = value;
                extreme_wcp[2] = cloud.pts[i];
            }
            if (value < values[3]) {
                values[3] = value;
                extreme_wcp[3] = cloud.pts[i];
            }
            // early-late  x
            if (cloud.pts[i].x > extreme_wcp[4].x) {
                extreme_wcp[4] = cloud.pts[i];
            }
            if (cloud.pts[i].x < extreme_wcp[5].x) {
                extreme_wcp[5] = cloud.pts[i];
            }
            // top-bottom  y
            if (cloud.pts[i].y > extreme_wcp[6].y) {
                extreme_wcp[6] = cloud.pts[i];
            }
            if (cloud.pts[i].y < extreme_wcp[7].y) {
                extreme_wcp[7] = cloud.pts[i];
            }
            // left-right  z or w
            if (cloud.pts[i].z > extreme_wcp[8].z) {
                extreme_wcp[8] = cloud.pts[i];
            }
            if (cloud.pts[i].z < extreme_wcp[9].z) {
                extreme_wcp[9] = cloud.pts[i];
            }
            // U range
            if (cloud.pts[i].index_u > extreme_wcp[10].index_u) {
                extreme_wcp[10] = cloud.pts[i];
            }
            if (cloud.pts[i].index_u < extreme_wcp[11].index_u) {
                extreme_wcp[11] = cloud.pts[i];
            }
            // V range
            if (cloud.pts[i].index_v > extreme_wcp[12].index_v) {
                extreme_wcp[12] = cloud.pts[i];
            }
            if (cloud.pts[i].index_v < extreme_wcp[13].index_v) {
                extreme_wcp[13] = cloud.pts[i];
            }
        }
    }

    if (!flag_init) {
        flag_init = true;
        for (int i = 0; i != 14; i++) {
            extreme_wcp[i] = cloud.pts[0];
        }
        extreme_wcp[1] = cloud.pts[1];
    }

    // count live channels
    std::set<int> live_u_index;
    std::set<int> live_v_index;
    std::set<int> live_w_index;
    for (auto it = mcells.begin(); it != mcells.end(); it++) {
        SlimMergeGeomCell* mcell = *it;
        GeomWireSelection& uwires = mcell->get_uwires();
        GeomWireSelection& vwires = mcell->get_vwires();
        GeomWireSelection& wwires = mcell->get_wwires();

        std::vector<WirePlaneType_t> bad_planes = mcell->get_bad_planes();

        if (find(bad_planes.begin(), bad_planes.end(), WirePlaneType_t(0)) == bad_planes.end()) {
            for (auto it1 = uwires.begin(); it1 != uwires.end(); it1++) {
                live_u_index.insert((*it1)->index());
            }
        }

        if (find(bad_planes.begin(), bad_planes.end(), WirePlaneType_t(1)) == bad_planes.end()) {
            for (auto it1 = vwires.begin(); it1 != vwires.end(); it1++) {
                live_v_index.insert((*it1)->index());
            }
        }

        if (find(bad_planes.begin(), bad_planes.end(), WirePlaneType_t(2)) == bad_planes.end()) {
            for (auto it1 = wwires.begin(); it1 != wwires.end(); it1++) {
                live_w_index.insert((*it1)->index());
            }
        }
        //    std::cout << live_u_index.size() << " " << live_v_index.size() << " " << live_w_index.size() << std::endl;
        /* for (auto it = bad_planes.begin(); it!=bad_planes.end(); it++){ */
        /*   std::cout << *it << std::endl; */
        /* } */
    }
    //  std::cout << live_u_index.size() << " " << live_v_index.size() << " " << live_w_index.size() << std::endl;

    std::pair<WCP::WCPointCloud<double>::WCPoint, WCP::WCPointCloud<double>::WCPoint> boundary_points;
    boundary_points.first = extreme_wcp[0];
    boundary_points.second = extreme_wcp[1];
    int ncount_live_u = 0;
    int ncount_live_v = 0;
    int ncount_live_w = 0;
    int temp_min_u, temp_max_u;
    int temp_min_v, temp_max_v;
    int temp_min_w, temp_max_w;
    if (boundary_points.first.index_u < boundary_points.second.index_u) {
        temp_min_u = boundary_points.first.index_u;
        temp_max_u = boundary_points.second.index_u;
    }
    else {
        temp_max_u = boundary_points.first.index_u;
        temp_min_u = boundary_points.second.index_u;
    }
    if (boundary_points.first.index_v < boundary_points.second.index_v) {
        temp_min_v = boundary_points.first.index_v;
        temp_max_v = boundary_points.second.index_v;
    }
    else {
        temp_max_v = boundary_points.first.index_v;
        temp_min_v = boundary_points.second.index_v;
    }
    if (boundary_points.first.index_w < boundary_points.second.index_w) {
        temp_min_w = boundary_points.first.index_w;
        temp_max_w = boundary_points.second.index_w;
    }
    else {
        temp_max_w = boundary_points.first.index_w;
        temp_min_w = boundary_points.second.index_w;
    }

    for (int temp_index = temp_min_u; temp_index <= temp_max_u; temp_index++) {
        if (live_u_index.find(temp_index) != live_u_index.end()) ncount_live_u++;
    }
    for (int temp_index = temp_min_v; temp_index <= temp_max_v; temp_index++) {
        if (live_v_index.find(temp_index) != live_v_index.end()) ncount_live_v++;
    }
    for (int temp_index = temp_min_w; temp_index <= temp_max_w; temp_index++) {
        if (live_w_index.find(temp_index) != live_w_index.end()) ncount_live_w++;
    }

    double boundary_value =
        fabs(boundary_points.first.x - boundary_points.second.x) / (2.22 * units::mm) +
        fabs(boundary_points.first.index_u - boundary_points.second.index_u) * 0.0 + ncount_live_u * 1.0 +
        fabs(boundary_points.first.index_v - boundary_points.second.index_v) * 0.0 + ncount_live_v * 1.0 +
        fabs(boundary_points.first.index_w - boundary_points.second.index_w) * 0.0 + ncount_live_w * 1.0;
    if (flag_cosmic)
        boundary_value =
            fabs(boundary_points.first.x - boundary_points.second.x) / (units::mm) +
            fabs(boundary_points.first.index_u - boundary_points.second.index_u) * 1.0 + ncount_live_u * 1. +
            fabs(boundary_points.first.index_v - boundary_points.second.index_v) * 1.0 + ncount_live_v * 1. +
            fabs(boundary_points.first.index_w - boundary_points.second.index_w) * 1.0 + ncount_live_w * 1. +
            sqrt(pow(boundary_points.first.x - boundary_points.second.x, 2) +
                 pow(boundary_points.first.y - boundary_points.second.y, 2) +
                 pow(boundary_points.first.z - boundary_points.second.z, 2)) /
                (units::mm);

    for (int i = 0; i < 14; i++) {
        for (int j = i + 1; j < 14; j++) {
            ncount_live_u = 0;
            ncount_live_v = 0;
            ncount_live_w = 0;

            if (extreme_wcp[i].index_u < extreme_wcp[j].index_u) {
                temp_min_u = extreme_wcp[i].index_u;
                temp_max_u = extreme_wcp[j].index_u;
            }
            else {
                temp_max_u = extreme_wcp[i].index_u;
                temp_min_u = extreme_wcp[j].index_u;
            }
            if (extreme_wcp[i].index_v < extreme_wcp[j].index_v) {
                temp_min_v = extreme_wcp[i].index_v;
                temp_max_v = extreme_wcp[j].index_v;
            }
            else {
                temp_max_v = extreme_wcp[i].index_v;
                temp_min_v = extreme_wcp[j].index_v;
            }
            if (extreme_wcp[i].index_w < extreme_wcp[j].index_w) {
                temp_min_w = extreme_wcp[i].index_w;
                temp_max_w = extreme_wcp[j].index_w;
            }
            else {
                temp_max_w = extreme_wcp[i].index_w;
                temp_min_w = extreme_wcp[j].index_w;
            }

            for (int temp_index = temp_min_u; temp_index <= temp_max_u; temp_index++) {
                if (live_u_index.find(temp_index) != live_u_index.end()) ncount_live_u++;
            }
            for (int temp_index = temp_min_v; temp_index <= temp_max_v; temp_index++) {
                if (live_v_index.find(temp_index) != live_v_index.end()) ncount_live_v++;
            }
            for (int temp_index = temp_min_w; temp_index <= temp_max_w; temp_index++) {
                if (live_w_index.find(temp_index) != live_w_index.end()) ncount_live_w++;
            }

            double value = fabs(extreme_wcp[i].x - extreme_wcp[j].x) / (2.22 * units::mm) +
                           fabs(extreme_wcp[i].index_u - extreme_wcp[j].index_u) * 0 + ncount_live_u * 1.0 +
                           fabs(extreme_wcp[i].index_v - extreme_wcp[j].index_v) * 0 + ncount_live_v * 1.0 +
                           fabs(extreme_wcp[i].index_w - extreme_wcp[j].index_w) * 0 + ncount_live_w * 1.0;

            if (flag_cosmic)
                value = fabs(extreme_wcp[i].x - extreme_wcp[j].x) / (units::mm) +
                        fabs(extreme_wcp[i].index_u - extreme_wcp[j].index_u) * 1.0 + ncount_live_u * 1. +
                        fabs(extreme_wcp[i].index_v - extreme_wcp[j].index_v) * 1.0 + ncount_live_v * 1. +
                        fabs(extreme_wcp[i].index_w - extreme_wcp[j].index_w) * 1.0 + ncount_live_w * 1. +
                        sqrt(pow(extreme_wcp[i].x - extreme_wcp[j].x, 2) + pow(extreme_wcp[i].y - extreme_wcp[j].y, 2) +
                             pow(extreme_wcp[i].z - extreme_wcp[j].z, 2)) /
                            (units::mm) *1;

            if (value > boundary_value) {
                /* if (cluster_id==28&& value > 275) */

                /* std::cout << extreme_wcp[i].x/units::cm << " " << extreme_wcp[i].y/units::cm << " " <<
                 * extreme_wcp[i].z/units::cm << " " */
                /* 	  << extreme_wcp[j].x/units::cm << " " << extreme_wcp[j].y/units::cm << " " <<
                 * extreme_wcp[j].z/units::cm << " " << value << " " << ncount_live_u << " " << ncount_live_v << " " <<
                 * ncount_live_w << std::endl; */

                boundary_value = value;
                if (extreme_wcp[i].y > extreme_wcp[j].y) {
                    boundary_points.first = extreme_wcp[i];
                    boundary_points.second = extreme_wcp[j];
                }
                else {
                    boundary_points.first = extreme_wcp[j];
                    boundary_points.second = extreme_wcp[i];
                }
            }
        }
    }

    if (boundary_points.first.y < boundary_points.second.y) {
        WCP::WCPointCloud<double>::WCPoint temp_wcp = boundary_points.first;
        boundary_points.first = boundary_points.second;
        boundary_points.second = temp_wcp;
    }

    return boundary_points;
}

std::pair<Point, Point> WCPPID::PR3DCluster::get_two_extreme_points(int flag)
{
    Create_point_cloud();
    ToyPointCloud* temp_point_cloud = point_cloud;
    if (flag == 2) {
        temp_point_cloud = point_cloud_steiner;
    }
    WCP::WCPointCloud<double>& cloud = temp_point_cloud->get_cloud();
    WCPointCloud<double>::WCPoint extreme_wcp[6];
    for (int i = 0; i != 6; i++) {
        extreme_wcp[i] = cloud.pts[0];
    }

    bool flag_init = false;

    for (size_t i = 0; i < cloud.pts.size(); i++) {
        if (excluded_points.find(i) != excluded_points.end()) continue;
        if (!flag_init) {
            flag_init = true;
            for (int j = 0; j != 6; j++) {
                extreme_wcp[j] = cloud.pts[i];
            }
        }
        else {
            if (cloud.pts[i].y > extreme_wcp[0].y) extreme_wcp[0] = cloud.pts[i];
            if (cloud.pts[i].y < extreme_wcp[1].y) extreme_wcp[1] = cloud.pts[i];

            if (cloud.pts[i].x > extreme_wcp[2].x) extreme_wcp[2] = cloud.pts[i];
            if (cloud.pts[i].x < extreme_wcp[3].x) extreme_wcp[3] = cloud.pts[i];

            if (cloud.pts[i].z > extreme_wcp[4].z) extreme_wcp[4] = cloud.pts[i];
            if (cloud.pts[i].z < extreme_wcp[5].z) extreme_wcp[5] = cloud.pts[i];
        }
    }

    double max_dis = -1;
    WCPointCloud<double>::WCPoint wcp1, wcp2;
    for (int i = 0; i != 6; i++) {
        for (int j = i + 1; j != 6; j++) {
            double dis =
                sqrt(pow(extreme_wcp[i].x - extreme_wcp[j].x, 2) + pow(extreme_wcp[i].y - extreme_wcp[j].y, 2) +
                     pow(extreme_wcp[i].z - extreme_wcp[j].z, 2));
            if (dis > max_dis) {
                max_dis = dis;
                wcp1 = extreme_wcp[i];
                wcp2 = extreme_wcp[j];
            }
        }
    }
    Point p1(wcp1.x, wcp1.y, wcp1.z);
    Point p2(wcp2.x, wcp2.y, wcp2.z);
    p1 = calc_ave_pos(p1, 5 * units::cm);
    p2 = calc_ave_pos(p2, 5 * units::cm);

    return std::make_pair(p1, p2);
}

void WCPPID::PR3DCluster::dijkstra_shortest_paths(WCPointCloud<double>::WCPoint& wcp, int flag)
{
    if (graph == (MCUGraph*) 0) Create_graph();

    //  if (wcp.index==source_wcp_index)
    //  return;
    source_wcp_index = wcp.index;
    parents.clear();
    distances.clear();

    if (flag == 1) {
        parents.resize(num_vertices(*graph));
        distances.resize(num_vertices(*graph));

        //    if (num_vertices(*graph)>1){
        auto v0 = vertex(wcp.index, *graph);
        boost::dijkstra_shortest_paths(
            *graph, v0, weight_map(get(edge_weight, *graph)).predecessor_map(&parents[0]).distance_map(&distances[0]));
        //}
    }
    else if (flag == 2) {
        parents.resize(num_vertices(*graph_steiner));
        distances.resize(num_vertices(*graph_steiner));

        //    if (num_vertices(*graph_steiner)>1){
        auto v0 = vertex(wcp.index, *graph_steiner);
        boost::dijkstra_shortest_paths(
            *graph_steiner, v0,
            weight_map(get(edge_weight, *graph_steiner)).predecessor_map(&parents[0]).distance_map(&distances[0]));
        //}
    }
}

void WCPPID::PR3DCluster::cal_shortest_path(WCPointCloud<double>::WCPoint& wcp_target, int flag)
{
    dest_wcp_index = wcp_target.index;
    path_wcps.clear();
    path_mcells.clear();

    ToyPointCloud* temp_point_cloud = point_cloud;
    if (flag == 2) {
        temp_point_cloud = point_cloud_steiner;
    }

    WCP::WCPointCloud<double>& cloud = temp_point_cloud->get_cloud();
    //  std::cout << dest_wcp_index << " " << source_wcp_index << std::endl;
    //  if ( dest_wcp_index != source_wcp_index && cloud.pts.size()>1){
    int prev_i = -1;
    for (int i = dest_wcp_index; i != source_wcp_index; i = parents[i]) {
        if (path_wcps.size() == 0) {
            path_wcps.push_front(cloud.pts[i]);
            path_mcells.push_front(cloud.pts[i].mcell);
        }
        else {
            path_wcps.push_front(cloud.pts[i]);
            if (cloud.pts[i].mcell != path_mcells.front()) path_mcells.push_front(cloud.pts[i].mcell);
        }
        if (i == prev_i) break;
        prev_i = i;
    }
    path_wcps.push_front(cloud.pts[source_wcp_index]);
    if (cloud.pts[source_wcp_index].mcell != path_mcells.front())
        path_mcells.push_front(cloud.pts[source_wcp_index].mcell);
    //}else{
    //  path_wcps.push_front(cloud.pts[source_wcp_index]);
    //  path_mcells.push_front(cloud.pts[source_wcp_index].mcell);
    // }
    parents.clear();
    distances.clear();
}
