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.
 For more information on norms, see LinearAlgebra[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.
 • For more information on Maple 2020 changes, see Updates in Maple 2020.