Implement flow maps

[Willem3141]

• Compute spiral tree without obstacles
• Compute spiral tree with obstacles
  • Implement sweep circle data structure
    • maintain edges and intervals
    • implement queries
      • interval at φ
      • edges at φ
    • implement operations
      • split from interval
      • split from edge
      • switch edge
      • merge to interval
      • merge to edge
    • properly handle edges moving over the φ = π ray (‘switch events’)
      • reinsert such edges
      • handle join events associated with such edges
  • Implement first phase: computing reachable area
    • implement vertex events
      • near
      • far
      • left
      • right
    • implement join events
      • reachable/reachable
      • reachable/obstacle
  • Implement second phase: computing spiral tree (Flow maps: implement second sweep #19)
    • implement node events
    • implement vertex events
      • near
      • far
      • left
      • right
    • implement join events
      • reachable/reachable
      • reachable/obstacle
    • create the tree
  • Implement demo application to test spiral trees
• Implement flow map optimization procedure (Implement flow map smoothing #28)
  • Implement flow map (smooth tree) data structure
  • Implement cost functions
    • obstacle cost
      • for polygon obstacles
      • for leaf obstacles
    • smoothing cost
    • angle restriction cost
    • balancing cost
    • straightening cost
  • Implement optimization
    • basic gradient descent
    • determine suitable time step
• Render the resulting flow map