Page - 175 - in Proceedings - OAGM & ARW Joint Workshop 2016 on "Computer Vision and Robotics“

New  Algorithm  to  Speed  up  the  Computation  of  a  Visibility  M.  Zauner1,  R.  Edlinger2,  W.  Rokitansky1 1  FH  OÖ  Studienbetriebs  GmbH,  A­ 4600  Wels,  Stelzhamerstraße  23 2  FH  OÖ  Forschungs  &  Entwicklungs  GmbH,  A­ 4600  Wels,  Stelzhamerstraße  23 {michael.zauner,  raimund.edlinger,  walter.rokitansky}@fh­ wels.at Abstract This  poster  describes  a  new  algorithm  called  B#  which  is  needed  to  find  the  visibility  graph  of  a polygonal  region  with  obstacles  defined  by  simple  polygons.  It  focuses  on  finding  the  entire visibility  graph  among  polygonal  obstacles  which  has  been  tuned  in  a  variety  of  test  cases.  The obstacles  are  restricted  to  simple  cases,  i.e.  where  no  edge  intersects  any  other  edges.  The  visibility graph  problem  itself  has  long  been  studied  and  has  been  applied  to  a  variety  of  areas.  A  common use  for  it  has  been  for  finding  the  shortest  path.  The  B#  algorithm  has  been  implemented adjustments   made   and   experimental   comparisons   via   time   measurements   carried   out.   A comparison  between  “Naïve  algorithm”  and  “Naive  algorithm  with  B#”  was  performed  with different  numbers  of  vertices.  The  B#  algorithm  by  itself  doesn’t  calculate  the  visibility  graph.  It selects  the  next  best  obstacle  where  the  calculation  should  proceed. 175