search

noinia / hgeometry

HGeometry is a library for computing with geometric objects in Haskell. It defines basic geometric types and primitives, and it implements some geometric data structures and algorithms.
122 stars 41 forks source link

Faster sssp' equivalent? #253

Open shamazmazum opened 3 weeks ago

shamazmazum commented 3 weeks ago

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 commented 3 weeks ago

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 commented 3 weeks ago

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 commented 3 weeks ago

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