| 66 | } |
| 67 | |
| 68 | std::vector<std::pair<Arrangement2::ElementType, int>> Arrangement2::query( |
| 69 | const Matrix2Fr& pts) { |
| 70 | using Point_location_result = CGAL::Arr_point_location_result<Arrangement_2>; |
| 71 | using Query_result = std::pair<Point_2, Point_location_result::Type>; |
| 72 | |
| 73 | const size_t num_pts = pts.rows(); |
| 74 | auto less_than = [&pts](size_t i, size_t j) { |
| 75 | if (pts(i,0) < pts(j,0)) return true; |
| 76 | else if (pts(i,0) > pts(j,0)) return false; |
| 77 | else if (pts(i,1) < pts(j,1)) return true; |
| 78 | else if (pts(i,1) > pts(j,1)) return false; |
| 79 | else return false; |
| 80 | }; |
| 81 | std::vector<size_t> indices(num_pts); |
| 82 | for (size_t i=0; i<num_pts; i++) { |
| 83 | indices[i] = i; |
| 84 | } |
| 85 | std::sort(indices.begin(), indices.end(), less_than); |
| 86 | |
| 87 | std::vector<Point_2> query_pts; |
| 88 | query_pts.reserve(num_pts); |
| 89 | for (size_t i=0; i<num_pts; i++) { |
| 90 | query_pts.emplace_back(pts(i,0), pts(i,1)); |
| 91 | } |
| 92 | std::vector<Query_result> query_results; |
| 93 | |
| 94 | CGAL::locate(m_arrangement, query_pts.begin(), query_pts.end(), |
| 95 | std::back_inserter(query_results)); |
| 96 | assert(query_results.size() == num_pts); |
| 97 | |
| 98 | std::vector<std::pair<ElementType, int>> results(num_pts); |
| 99 | |
| 100 | for (size_t i=0; i<num_pts; i++) { |
| 101 | const auto& r = query_results[i]; |
| 102 | |
| 103 | const auto v = boost::get<Arrangement_2::Vertex_const_handle>(&(r.second)); |
| 104 | const auto e = boost::get<Arrangement_2::Halfedge_const_handle>(&(r.second)); |
| 105 | const auto f = boost::get<Arrangement_2::Face_const_handle>(&(r.second)); |
| 106 | |
| 107 | size_t index = indices[i]; |
| 108 | if (f) { |
| 109 | results[index] = {CELL, (*f)->data()}; |
| 110 | } else if (e) { |
| 111 | results[index] = {SEGMENT, (*e)->data()}; |
| 112 | } else if (v) { |
| 113 | results[index] = {POINT, (*v)->data()}; |
| 114 | } else { |
| 115 | throw NotImplementedError("Unknown CGAL query result type."); |
| 116 | } |
| 117 | } |
| 118 | |
| 119 | |
| 120 | return results; |
| 121 | } |
| 122 | |
| 123 | #endif |