Ai Dreams Forum

Member's Experiments & Projects => AI Programming => Topic started by: Marcus Vilain on March 05, 2019, 12:50:09 am

Title: Visibility graph
Post by: Marcus Vilain on March 05, 2019, 12:50:09 am

Hi,

Does anyone knows if a c++ library that computes a reduced visibility graph exists ? It will be used to find the shortest path. Sorry if it’s not the right place to post this message.
Thanks for the help,
Marcus

Title: Re: Visibility graph
Post by: ivan.moony on March 05, 2019, 05:15:03 am

I'm not sure what reduced visibility graph represents. For shortest path finding, did you try searching algorithm A star (https://en.wikipedia.org/wiki/A*_search_algorithm) or traveling salesman solution (https://en.wikipedia.org/wiki/Travelling_salesman_problem)?

Title: Re: Visibility graph
Post by: AndyGoode on March 06, 2019, 01:08:46 am

Quote from: ivan.moony on March 05, 2019, 05:15:03 am

I'm not sure what reduced visibility graph represents.

I just looked this up. I'd never heard of such a graph before, but it's quite interesting (to me, at least). A visibility graph is another way of showing which points have a clear line of sight between them when there exist obstacles nearby that might block the line of sight. A reduced visibility graph is a visibility graph with unneeded edges removed from the diagram...

http://www.cs.kent.edu/~dragan/ST-Spring2016/visibility%20graphs.pdf

As for C++ libraries, I have no idea which libraries contain which functions. Maybe that's why I can't get a job as a C++ programmer.  ;)

Title: Re: Visibility graph
Post by: 8pla.net on March 07, 2019, 04:15:05 pm

A visibility graph reminds me of ray tracing. All credit to Kevin Beason, C++ source code listing:

Source code http://www.kevinbeason.com/smallpt/explicit.cpp compiled with:

                  g++ -O3 -fopenmp explicit.cpp -o explicit.o

Ran program with:  ./explicit.o ... It generates image.ppm in 10 seconds.

For discussion purposes and image compatibility, PPM image converted to scaled down, indexed PNG image...

(https://aidreams.co.uk/forum/proxy.php?request=http%3A%2F%2Fchatbot.altervista.org%2Fraytrace%2Ffor-discussion-purposes-only.png&hash=4f245c16e00c9b0787571fd41961a64377df22a9)

Citation (and recommended... Ray Tracer is 99 lines of C++ is really worth checking out.):
http://www.kevinbeason.com