How to efficiently find common polygon segments?

Question

Cartography

I am developing a mapping engine for nautical charts. The standard states that if line segments overlap each other (have common segments), then the line segment with the lowest priority (each geometry has priority) should be hidden. I can't figure out how to express it algorithmically. First of all, I tried to go through all the lines and delete common points, which is fundamentally wrong, because the remaining points were connected and the geometry of the lines itself changed. Plus, the performance is terrible: for each line, we go through all the lines and points ... One such line can contain 4 thousand points. And there can be more than a thousand lines on the screen.

Simply put, you need to find and hide the common segments of polygonal geometry and do it quite efficiently.

In a similar proprietary software, such functionality is implemented and works quite quickly. Surely there are some generally accepted solutions to this problem.

Below is a clipping from the standard.


Below is a screenshot showing how the line denoting a dangerous area (in the form of a purple pattern with an exclamation point) has common edges with the coastline and the pier line. Since these lines have a higher priority, the line denoting the boundaries of the area must be hidden in these segments.

Answer 1

Postgis (a GIS extension for postgres) does this very efficiently. Look at the source, they are open. I also see no reason to reinvent the dendrofecal bicycle when there is GDAL .
The task is not trivial. The lines of your geometry may differ slightly, may not lie on the same sets of points, may be in different directions, which is sometimes important.

Answer 2

In this case, there is a spatial index. Where you quickly get a list of the points included in it using bbox and then go through only them, and not all 4k.
https://blog.mapbox.com/a-dive-into-spatial-search...