Visibility graph

  • 3 Replies
  • 1985 Views
*

Marcus Vilain

  • Roomba
  • *
  • 11
Visibility graph
« 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

*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1721
    • mind-child
Re: Visibility graph
« Reply #1 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 or traveling salesman solution?

*

AndyGoode

  • Guest
Re: Visibility graph
« Reply #2 on: March 06, 2019, 01:08:46 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.  ;)

*

8pla.net

  • Trusty Member
  • ***********
  • Eve
  • *
  • 1299
  • TV News. Pub. UAL (PhD). Robitron Mod. LPC Judge.
    • 8pla.net
Re: Visibility graph
« Reply #3 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...



Citation (and recommended... Ray Tracer is 99 lines of C++ is really worth checking out.):
http://www.kevinbeason.com
My Very Enormous Monster Just Stopped Using Nine

 


OpenAI Speech-to-Speech Reasoning Demo
by MikeB (AI News )
March 15, 2024, 08:14:02 am
Google Bard report
by ivan.moony (AI News )
February 14, 2024, 04:42:23 pm
Elon Musk's xAI Grok Chatbot
by MikeB (AI News )
December 11, 2023, 06:26:33 am
Nvidia Hype
by 8pla.net (AI News )
December 06, 2023, 10:04:52 pm
How will the OpenAI CEO being Fired affect ChatGPT?
by 8pla.net (AI News )
December 06, 2023, 09:54:25 pm
Independent AI sovereignties
by WriterOfMinds (AI News )
November 08, 2023, 04:51:21 am
LLaMA2 Meta's chatbot released
by 8pla.net (AI News )
October 18, 2023, 11:41:21 pm
AI-Generated Art Cannot Receive Copyrights
by frankinstien (AI News )
August 24, 2023, 08:49:45 am

Users Online

142 Guests, 0 Users

Most Online Today: 248. Most Online Ever: 2369 (November 21, 2020, 04:08:13 pm)

Articles