Faster sssp' equivalent?

[shamazmazum]

Hi! I need to find a shortest path inside a simple polygon between each pair of polygon's vertices. Currently, I have to call sssp . triangulate from Algorithms.Geometry.SSSP for a polygon, then rotate it by 1 to the right and repeat until all starting points are processed. This is extremely slow and at least triangulation step can be somehow avoided. I tried the following to "rotate" the triangulation:

moveRight ::
  PlaneGraph s Int PolygonEdgeType PolygonFaceData Rational ->
  PlaneGraph s Int PolygonEdgeType PolygonFaceData Rational
moveRight trias = fromAdjRep $ over (adjacencies' . traverse . vData') f gr where
  f vdata = (vdata + total - 1) `mod` total
  gr = toAdjRep trias
  total = PG.numVertices trias

This is faster but very GC expensive. Can I do the same without converting to adjrep and back? I cannot understand how PlaneGraph works, Gr seems to be easier to understand, this is why I used it. Or maybe I am doing it completely wrong?

[noinia]

Oh thanks for reporting this.

There shouldn't really be a need to retriangulate at all; i.e. it be possible to use the same triangulation for all starting points. It seems the current implementation also always just starts from a fixed vertex (thus forcing you to retriangulate to somehow select the right vertex). I still have to port the SSSP implementation to the new HGeometry 1 setup anway; that seems like a good time to try and fix this as well.

edit: updating the PlaneGraph representation directly may be more challenging (it's pretty specific so that we can do a lot of basic "query" operations in O(1) time. But it is a bit difficult to update it).

[shamazmazum]

Thanks! Adding an integer parameter to sssp is enough indeed. Like so:

sssp index trig =
    ssspFinger (PlaneGraph.numVertices trig) d
  where
    Just v0 = fst <$> V.find (\(_vid, VertexData _ idx) -> idx == index) (vertices trig)
    ...

[noinia]

Great! That was actually even simpler than I had expected (I didn't write that part of the code myself)