| 211 | } |
| 212 | |
| 213 | std::vector<std::size_t> LocationDependentData::GetPropertyIndexes(const point_t &point) const |
| 214 | { |
| 215 | std::vector<std::size_t> result; |
| 216 | auto inserter = [this, &result](const rtree_t::value_type &rtree_entry) |
| 217 | { |
| 218 | const auto properties_index = polygons[rtree_entry.second].second; |
| 219 | result.push_back(properties_index); |
| 220 | }; |
| 221 | |
| 222 | // Search the R-tree and collect a Lua table of tags that correspond to the location |
| 223 | rtree.query( |
| 224 | boost::geometry::index::intersects(point) && |
| 225 | boost::geometry::index::satisfies( |
| 226 | [this, &point](const rtree_t::value_type &v) |
| 227 | { |
| 228 | // Simple point-in-polygon algorithm adapted from |
| 229 | // https://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html |
| 230 | |
| 231 | const auto &envelop = v.first; |
| 232 | const auto &bands = polygons[v.second].first; |
| 233 | |
| 234 | const auto y_min = envelop.min_corner().y(); |
| 235 | const auto y_max = envelop.max_corner().y(); |
| 236 | const auto dy = (y_max - y_min) / bands.size(); |
| 237 | |
| 238 | std::size_t band = (point.y() - y_min) / dy; |
| 239 | if (band >= bands.size()) |
| 240 | { |
| 241 | band = bands.size() - 1; |
| 242 | } |
| 243 | |
| 244 | bool inside = false; |
| 245 | |
| 246 | for (const auto &segment : bands[band]) |
| 247 | { |
| 248 | const auto point_x = point.x(), point_y = point.y(); |
| 249 | const auto from_x = segment.first.x(), from_y = segment.first.y(); |
| 250 | const auto to_x = segment.second.x(), to_y = segment.second.y(); |
| 251 | |
| 252 | if (to_y == from_y) |
| 253 | { // handle horizontal segments: check if on boundary or skip |
| 254 | if ((to_y == point_y) && |
| 255 | (from_x == point_x || (to_x > point_x) != (from_x > point_x))) |
| 256 | return true; |
| 257 | continue; |
| 258 | } |
| 259 | |
| 260 | if ((to_y > point_y) != (from_y > point_y)) |
| 261 | { |
| 262 | const auto ax = to_x - from_x; |
| 263 | const auto ay = to_y - from_y; |
| 264 | const auto tx = point_x - from_x; |
| 265 | const auto ty = point_y - from_y; |
| 266 | |
| 267 | const auto cross_product = tx * ay - ax * ty; |
| 268 | |
| 269 | if (cross_product == 0) |
| 270 | return true; |