Best data structure for storing adjacent polygons?

Question

Sorry, I have a lot of problems with the wording of this question.

I am fixated on a data structure (or a combination of data structures) that I must use to preserve the arrangement of polygons bordering each other (for example, any real-world map).

I have to clarify: I want to make the point move at a fixed speed through the map (landscape) of these polygons. The whole landscape is covered with polygons - the space is not classified; each point on the map belongs to a certain polygon. This means that all polygons on all sides border either another polygon or the edge of the map. The map is limited, but ideally it doesn’t matter how big the map is or how many polygons are represented. Each polygon has a name (this is important, since each point now belongs to at least two named polygons). A point moving along a 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 to another. (if any other explanation is needed, please comment.)

Is there an acceptable way to do this?

- EDIT -

Polygons are fixed. All points and edges must be precoded. Points and edges will never change unpredictably or randomly (if they change at all, it will be in response to a non-continuous fixed event).

Answer 1

A technical term that describes this flat, straight line graph for which a double-linked list of edges (DCEL) is a suitable representation.

One of the requirements of your data structure seems to be the ability to perform a (quick) query on the location of the points. (What polygon does this point belong to?) There are classical solutions, among which trapezoidal decomposition can be recommended.

I do not know a suitable solution for "borderline" requests, i.e. finding intersections with a (presumably) linear path. You can probably adapt from a point location problem, but these promises will be tricky.

In any case, if your polygons have a reasonable number of vertices, it is not difficult to find all the intersections with the given line by trying all the edges in turn. Using the DCEL view, 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 tree of a two-dimensional segment , where each 2D interval corresponds to the bounding box of the polygon, and the type of value corresponds to the polygon itself (a list of its edges).

After the agent has moved from p1 to p2, run the query window to the segment tree: find all two-dimensional intervals (bounding fields) that intersect with / contained in the rectangle defined by p1 and p2.

For each polygon inside these bounding fields, check to see if it contains p2.