Simple area graph construction

[abyrd]

Outside of elevation, visibility calculations are one of the slowest parts of graph building. The code is not really maintained. Rather than just skipping visibility calculations (as I now often do) I would rather have some faster code that just makes edges between area centroids, concave vertices of the areas, and intersections with other ways. Not sure if this would significantly degrade routing results in urban areas.

[abyrd]

For the time being these can be disabled completely with the --skipVisibility switch.

[laurentg]

Problem is that area centroid can be outside of the area, and/or have edges between it and concave vertices and in/out intersections crossing holes or outer shell.

A minor modification to this would be to create edges between every pair of intersections and concave vertices (including holes), removing all edges that intersect with the area. But if concave vertices are numerous (round shape for example) that can amount to a lot of superfluous edges.

Another idea: use a convex polygon decomposition and for each convex sub-polygon, create edges for every pair of intersections and points on shared edges (for example the middle, or both end points).

Again another idea: simply add the straight skeleton of the polygon.

[abyrd]

@laurentg All of your ideas are interesting ingredients and would probably give paths that are for all practical purposes as good as precise visibility graphs. Personally I'm not sure I care much whether there's occasionally a centroid or a centroid-edge passing outside the area. It would serve as a decent stopgap measure because it's very fast and would give vaguely correct results, whereas I have just discovered that currently we're not including any edges at all when visibility graph construction is turned off.

[abyrd]

When visibility graph construction is turned off, no edges are added at all for areas. This really breaks routing. We need to always add at least something to the graph for areas.