const point_type_fp& current,

const coordinate_type_fp& max_path_length,

const std::vector<point_type_fp>& vertices,

const PathFindingSurface* pfs) :

start(start),

goal(goal),

current(current),

max_path_length_squared(max_path_length),

vertices(vertices),

if (p == current) {

return false;

}

pfs->decrement_tries();

if (bg::distance(current, p) + bg::distance(p, goal) > max_path_length_squared) {

return false;

}

if (!pfs->in_surface(current, p)) {

return false;

}

return true;

auto ret = iterator(this, 0);

if (ret == end()) {

// Can't dereferfence the end.

return ret;

}

if (is_neighbor(*ret)) {

// This is a valid begin.

return ret;

} else {

// This position is invalid but we can increment to get to a valid one.

++ret;

return ret;

}

const vector<vector<std::reference_wrapper<const ring_type_fp>>>& all_rings) {

vector<pair<point_type_fp, point_type_fp>> ret;

for (const auto& x0 : all_rings) {

for (auto x1 : x0) {

for (size_t i = 0; i+1 < x1.get().size(); i++) {

ret.emplace_back(x1.get()[i], x1.get()[i+1]);

}

}

}

return ret;

vector<std::reference_wrapper<const ring_type_fp>> ret;

for (const auto& poly : mpolys) {

ret.push_back(poly.outer());

for (const auto& inner : poly.inners()) {

ret.push_back(inner);

}

}

return ret;

const nested_multipolygon_type_fp& mpolys) {

vector<vector<std::reference_wrapper<const ring_type_fp>>> ret;

for (const auto& poly : mpolys) {

ret.push_back(get_all_rings(poly.outer()));

for (const auto& inner: poly.inners()) {

ret.push_back(get_all_rings(inner));

}

}

return ret;

const multi_polygon_type_fp& keep_out,

const coordinate_type_fp tolerance) {

if (keep_in) {

multi_polygon_type_fp total_keep_in = *keep_in - keep_out;

total_keep_in_grown.emplace();

for (const auto& poly : total_keep_in) {

all_vertices.emplace_back();

all_vertices.back().emplace_back(poly.outer().cbegin(), poly.outer().cend());

total_keep_in_grown->emplace_back(bg_helpers::buffer_miter(poly.outer(), tolerance));

for (const auto& inner : poly.inners()) {

all_vertices.back().emplace_back(inner.cbegin(), inner.cend());

// Because the inner is reversed, we need to reverse it so

// that the buffer algorithm won't get confused.

auto temp_inner = inner;

bg::reverse(temp_inner);

// tolerance needs to be inverted because growing a shape

// shrinks the holes in it.

total_keep_in_grown->back().inners().push_back(bg_helpers::buffer_miter(temp_inner, -tolerance));

}

}

} else {

for (const auto& poly : keep_out){

all_vertices.emplace_back();

all_vertices.back().emplace_back(poly.outer().cbegin(), poly.outer().cend());

keep_out_shrunk.emplace_back(bg_helpers::buffer_miter(poly.outer(), -tolerance));

for (const auto& inner : poly.inners()) {

all_vertices.back().emplace_back(inner.cbegin(), inner.cend());

// Because the inner is reversed, we need to reverse it so

// that the buffer algorithm won't get confused.

auto temp_inner = inner;

bg::reverse(temp_inner);

// tolerance needs to be inverted because shrinking a shape

// grows the holes in it.

keep_out_shrunk.back().inners().push_back(bg_helpers::buffer_miter(temp_inner, tolerance));

}

}

}

const nested_multipolygon_type_fp& poly_to_search = total_keep_in_grown ? *total_keep_in_grown : keep_out_shrunk;

const vector<vector<std::reference_wrapper<const ring_type_fp>>>& all_rings = get_all_rings(poly_to_search);

const auto& all_segments = get_all_segments(all_rings);

segment_tree::SegmentTree x(all_segments);

tree = std::move(x);

for (auto av : all_vertices) {

sort(av.begin(), av.end());

av.erase(std::unique(av.begin(), av.end()), av.end());

}

const multi_polygon_type_fp& mp) {

for (size_t poly_index = 0; poly_index < mp.size(); poly_index++) {

const auto& poly = mp[poly_index];

if (point_in_ring(p, poly.outer())) {

// Might be part of this shape but only if the point isn't in

// the inners.

MPRingIndices ring_indices{{poly_index, {0}}};

for (size_t inner_index = 0; inner_index < poly.inners().size(); inner_index++) {

const auto& inner = poly.inners()[inner_index];

if (!point_in_ring(p, inner)) {

// We'll have to make sure not to cross this inner.

ring_indices.back().second.emplace_back(inner_index+1);

} else {

break; // We're inside one of the inners so give up.

}

}

if (ring_indices.back().second.size() == poly.inners().size() + 1) {

// We never hit the break so we're inside this shape so we're

// done.

return {ring_indices};

}

// We're inside the outer but also inside an inner! There might

// be another shape inside this hold so we'll ignore this one

// and keep searching.

}

}

return boost::none;

const multi_polygon_type_fp& mp) {

MPRingIndices ring_indices;

for (size_t poly_index = 0; poly_index < mp.size(); poly_index++) {

const auto& poly = mp[poly_index];

if (point_in_ring(p, poly.outer())) {

// We're inside the outer, maybe we're in an inner? If not, we

// aren't outside at all and we'll just give up.

bool in_any_inner = false;

for (size_t i = 0; i < poly.inners().size(); i++) {

const auto& inner = poly.inners()[i];

if (point_in_ring(p, inner)) {

in_any_inner = true;

ring_indices.emplace_back(poly_index, vector<size_t>{i+1});

break;

}

}

if (!in_any_inner) {

// We're inside the outer but not in any of the inners, so

// we're in the shape, but we want to be outside the shape, so

// we've failed.

return boost::none;

}

} else {

// We need to keep out of this outer.

ring_indices.emplace_back(poly_index, vector<size_t>{0});

// No need to examine the inners which we can't possibly be inside.

}

}

return {ring_indices};

const point_type_fp& p,

const nested_multipolygon_type_fp& mp) {

for (size_t poly_index = 0; poly_index < mp.size(); poly_index++) {

const auto& poly = mp[poly_index];

boost::optional<MPRingIndices> inside_mp = inside_multipolygon(p, poly.outer());

if (inside_mp) {

// Might be part of this shape but only if the point isn't in

// the inners.

RingIndices ring_indices{{poly_index, {{0, *inside_mp}}}};

for (size_t inner_index = 0; inner_index < poly.inners().size(); inner_index++) {

const auto& inner = poly.inners()[inner_index];

auto outside_mp = outside_multipolygon(p, inner);

if (outside_mp) {

// We'll have to make sure not to cross this inner.

ring_indices.back().second.emplace_back(inner_index+1, *outside_mp);

} else {

break; // We're inside one of the inners so give up.

}

}

if (ring_indices.back().second.size() == poly.inners().size() + 1) {

// We never hit the break so we're inside this shape so we're

// done.

return {ring_indices};

}

// We're inside the outer but also inside an inner! It might

// be an outer in an inner so we'll ignore this one and keep

// searching.

}

}

return boost::none;

const point_type_fp& p,

const nested_multipolygon_type_fp& mp) {

RingIndices ring_indices;

for (size_t poly_index = 0; poly_index < mp.size(); poly_index++) {

const auto& poly = mp[poly_index];

auto outside_mp = outside_multipolygon(p, poly.outer());

if (!outside_mp) {

// We're inside the outer, maybe we're in an inner? If not, we

// aren't outside at all and we'll just give up.

bool in_any_inner = false;

for (size_t inner_index = 0; inner_index < poly.inners().size(); inner_index++) {

const auto& inner = poly.inners()[inner_index];

auto inside_mp = inside_multipolygon(p, inner);

if (inside_mp) {

in_any_inner = true;

ring_indices.emplace_back(poly_index, vector<pair<size_t, MPRingIndices>>{{inner_index + 1, *inside_mp}});

break;

}

}

if (!in_any_inner) {

// We're inside the outer but not in any of the inners, so

// we're in the shape, but we want to be outside the shape, so

// we've failed.

return boost::none;

}

} else {

// We need to keep out of this outer.

ring_indices.emplace_back(poly_index, vector<pair<size_t, MPRingIndices>>{{0, *outside_mp}});

}

}

return {ring_indices};

if (tries) {

if (*tries == 0) {

throw GiveUp();

}

(*tries)--;

}

const point_type_fp& a, const point_type_fp& b) const {

if (b < a) {

return in_surface(b, a);

}

const auto key = make_pair(a, b);

auto memoized_result = edge_in_surface_memo.find(key);

if (memoized_result != edge_in_surface_memo.cend()) {

return memoized_result->second;

}

auto found_intersection = tree.intersects(a, b);

edge_in_surface_memo.emplace(key, !found_intersection);

return !found_intersection;

const coordinate_type_fp& max_path_length,

SearchKey search_key,

const point_type_fp& current) const {

return Neighbors(start, goal, current, max_path_length, vertices(search_key), this);

point_type_fp current,

const unordered_map<point_type_fp, point_type_fp>& came_from) {

linestring_type_fp result;

while (came_from.count(current)) {

result.push_back(current);

current = came_from.at(current);

}

result.push_back(current);

bg::reverse(result);

return result;

const point_type_fp& start, const point_type_fp& goal,

const coordinate_type_fp& max_path_length,

SearchKey search_key) const {

// Connect if a direct connection is possible. This also takes care

// of the case where start == goal.

try {

if (in_surface(start, goal)) {

decrement_tries();

if (bg::comparable_distance(start, goal) < max_path_length * max_path_length) {

// in_surface builds up some structures that are only efficient if

// we're doing many tries.

return {{start, goal}};

} else {

// If the straight line was too long then there is no way to connect.

return boost::none;

}

}

} catch (GiveUp g) {

return boost::none;

}

// Do astar.

priority_queue<pair<coordinate_type_fp, point_type_fp>,

vector<pair<coordinate_type_fp, point_type_fp>>,

std::greater<pair<coordinate_type_fp, point_type_fp>>> open_set;

open_set.emplace(bg::distance(start, goal), start);

unordered_set<point_type_fp> closed_set;

unordered_map<point_type_fp, point_type_fp> came_from;

unordered_map<point_type_fp, coordinate_type_fp> g_score; // Empty should be considered infinity.

g_score[start] = 0;

while (!open_set.empty()) {

const auto current = open_set.top().second;

open_set.pop();

if (current == goal) {

// We're done.

return make_optional(build_path(current, came_from));

}

if (closed_set.count(current) > 0) {

// Skip this because we already "removed it", sort of.

continue;

}

try {

const auto current_neighbors = neighbors(

start, goal,

max_path_length - g_score.at(current),

search_key,

current);

for (const auto& neighbor : current_neighbors) {

const auto tentative_g_score = g_score.at(current) + bg::distance(current, neighbor);

if (g_score.count(neighbor) == 0 || tentative_g_score < g_score.at(neighbor)) {

// This path to neighbor is better than any previous one.

came_from[neighbor] = current;

g_score[neighbor] = tentative_g_score;

open_set.emplace(tentative_g_score + bg::distance(neighbor, goal), neighbor);

}

}

} catch (GiveUp g) {

return boost::none;

}

// Because we can't delete from the open_set, we'll just marked

// items as closed and ignore them later.

closed_set.insert(current);

}

return boost::none;

const point_type_fp& start, const point_type_fp& goal,

const coordinate_type_fp& max_path_length,

const boost::optional<size_t>& max_tries,

SearchKey search_key) const {

if (max_tries) {

if (*max_tries == 0) {

return boost::none;

}

tries.emplace(*max_tries);

} else {

tries = boost::none;

}

return find_path(start, goal, max_path_length, search_key);

const point_type_fp& start, const point_type_fp& goal,

const coordinate_type_fp& max_path_length,

const boost::optional<size_t>& max_tries) const {

if (max_tries) {

if (*max_tries == 0) {

return boost::none;

}

tries.emplace(*max_tries);

} else {

tries = boost::none;

}

auto ring_indices = in_surface(start);

if (!ring_indices) {

// Start is not in the surface.

return boost::none;

}

if (ring_indices != in_surface(goal)) {

// Either goal is not in the surface or it's in a region unreachable by start.

return boost::none;

}

return find_path(start, goal, max_path_length, *ring_indices);