Best data structure to store contiguous polygons?

Question

I'm sorry, I'm having a lot of trouble wording this question.

I'm stuck on what data structure (or combination of data structures) I should use to store an arrangement of polygons bordering one another (like any real world map).

I should clarify: what I mean to do is have a point moving at a fixed speed through a map (a landscape) of these polygons. The entire landscape is covered in polygons - no space is unclassified; each point in the map belongs to some polygon. This means that all polygons border, on all sides, either another polygon or the edge of the map. The map is bounded, but ideally, it should not matter how large the map is or how many polygons are represented. Each polygon has a name (this is significant, as each point now belongs to at least two named polygons). The point moving through the map should always know the name of the polygon in which it is located, and the point should also be notified whenever it crosses a border from one polygon into another. (if any other clarifications are needed, please comment.)

Is there any accepted way to do this?

--EDIT--

The polygons are fixed. All points and edges will need to be hard-coded in beforehand. The points and edges will never change unpredictably or randomly (if they change at all, it will be in response to an infrequent fixed event).

Answer 1

The technical term describing this is a planar straight-line graph, for which a suitable representation is the doubly connected edge list (DCEL).

One of the requirements of your data structure seems to be the possibility to perform (fast) point location queries. (To what polygon does this point belong ?) There are classical solutions, among which one can recommend the trapezoidal decomposition.

I don't know of a suitable solution for the "border" queries, i.e. finding the intersections with a (presumably) linear trajectory. You can probably adapt from the point location problem, but this promises to be tricky.

Anyway, if your polygons have a reasonable number of vertices, it is not a big deal to find all intersections with a given straight line by trying all edges in turn. Using a DCEL representation, when you leave a polygon, you know which one you enter.

If I were you, I would start with a DCEL structure, a point-in-polygon algorithm, and a line-polygon intersection algorithm (which is essentially the same thing).

Answer 2

Build a 2D segment tree where each 2D interval corresponds to the bounding box of a polygon and the value type corresponds to the polygon itself (the list of its edges).

After the agent moved from p1 to p2, run a window-query against the segment tree: search for all 2D intervals (bounding boxes) that intersect with / contained in the rectangle defined by p1 and p2.

For each of the polygons within these bounding boxes, check if it contains p2.