Approach.
I suggest to interpret the input as a PSLG, G, which consists of vertices and edges. Then your question reduces to finding the face of G that is hit by the point p. This is done by shooting a ray from p to some direction to find an edge of the boundary of the face and traverse the boundary of the face in some direction. However, the first edge hit could be a face that is not hit by p, but itself enclosed by the face hit by p. Hence, we may need to keep search along the ray emanated by p.
Implementational details.
In the code below I shoot a ray to east direction and run around the face in clockwise direction, i.e., at each vertex I take the next counter-clockwise edge, until I end up at the first vertex again. The resulting face is returned as a sequence of vertices of G.
If you want to return a simple polygon then you have to clean-up the input graph G by pruning of trees in G such that only the simple faces remain.
def find_smallest_enclosing_polygon(G, p, simple=False):
"""Find face of PSLG G hit by point p. If simple is True
then the face forms a simple polygon, i.e., "trees"
attached to vertices are pruned."""
if simple:
# Make G comprise simple faces only, i.e., all vertices
# have degree >= 2.
done = False
while not done:
done = True
for v in [v in vertices if degree(v) <= 1]:
# Remove vertex v and all incident edges
G.remove(v)
done = False
# Shoot a ray from p to the east direction and get all edges.
ray = Ray(p, Vector(1, 0))
for e in G.iter_edges_hit(ray):
# There is no enclosing face; p is in the outer face of G
if e is None:
return None
# Let oriented edge (u, v) point clockwise around the face enclosing p
u, v = G.get_vertices(e)
if u.y < v.y
u, v = v, u
# Construct the enclosing face in clockwise direction
face = [u, v]
# While not closed
while face[-1] != face[0]:
# Get next counter-clockwise edge at last vertex at last edge.
# If face[-1] is of degree 1 then I assume to get e again.
e = G.get_next_ccw_edge(face[-2], face[-1])
face.append(G.get_opposite_vertex(e, face[-1]))
# Check whether face encloses p.
if contains(face, p):
return face
return None
Complexity.
Let n denote the number of vertices. Note that in a PSLG the number of edges are in O(n). The pruning part may take O(n^2) time the way it is implemented above. But it could be one in O(n) time by identifying the degree-1 vertices and keep traversing from those.
The ray intersection routine can be implemented trivially in O(n) time. Constructing the face takes O(m) time, where m is the size of the polygon constructed. We may need to test multiple polygons but the sum of sizes of all polygons is still in O(n). The test contains(face, p) could be done by checking whether face contains an uneven number of edges returned by G.iter_edges_hit(ray), i.e., in O(m) time.
With some preprocessing you can build up a data structure that finds the face hit by p in O(log n) time by classical point location algorithms in computational geometry and you can store the resulting polygons upfront, for the simple and/or non-simple cases.