VisibilityGraph - Maple Help

GraphTheory[GeometricGraphs]

 VisibilityGraph
 construct a visibility graph

 Calling Sequence VisibilityGraph( P, opts )

Parameters

 P - Matrix or list of lists representing vertices of a polygon opts - (optional) one or more options as specified below

Options

 • norm : positive real or one of Euclidean or infinity.
 Specifies the norm to be used in computing distances. The default is 2, the Euclidean norm.
 • weighted : true or false
 If weighted=true, the result is a weighted graph whose edge weights correspond to the distance between points using the specified norm. Default is false.

Description

 • The VisibilityGraph(P, opts) command returns a visibility graph for the polygon P.
 • The parameter P must be a Matrix or list of lists representing a list of points.

Definition

 • Given a 2-D polygon P, the visibility graph of P is the graph whose vertices correspond to the vertices of P and in which an edge exists between vertices if the line segment between their associated points lies entirely within the polygon P.
 • If the input polygon is convex, the visibility graph will be a complete graph.

Examples

Generate a visibility graph for a polygon.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{GeometricGraphs}\right):$
 > $P≔\left[\left[391,374\right],\left[240,431\right],\left[252,340\right],\left[374,320\right],\left[289,214\right],\left[134,390\right],\left[68,186\right],\left[154,259\right],\left[161,107\right],\left[435,108\right],\left[208,148\right],\left[295,160\right],\left[421,212\right],\left[441,303\right]\right]$
 ${P}{≔}\left[\left[{391}{,}{374}\right]{,}\left[{240}{,}{431}\right]{,}\left[{252}{,}{340}\right]{,}\left[{374}{,}{320}\right]{,}\left[{289}{,}{214}\right]{,}\left[{134}{,}{390}\right]{,}\left[{68}{,}{186}\right]{,}\left[{154}{,}{259}\right]{,}\left[{161}{,}{107}\right]{,}\left[{435}{,}{108}\right]{,}\left[{208}{,}{148}\right]{,}\left[{295}{,}{160}\right]{,}\left[{421}{,}{212}\right]{,}\left[{441}{,}{303}\right]\right]$ (1)
 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{plottools}:-\mathrm{polygon}\left(P,\mathrm{style}=\mathrm{line}\right)\right)$
 > $\mathrm{VG}≔\mathrm{VisibilityGraph}\left(P\right)$
 ${\mathrm{VG}}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 14 vertices and 36 edge\left(s\right)}}$ (2)
 > $\mathrm{DrawGraph}\left(\mathrm{VG}\right)$

References

 Lozano-Pérez, Tomás; Wesley, Michael A. (1979), "An algorithm for planning collision-free paths among polyhedral obstacles", Communications of the ACM, 22(10): 560–570. doi:10.1145/359156.359164.

Compatibility

 • The GraphTheory[GeometricGraphs][VisibilityGraph] command was introduced in Maple 2020.