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

 • metric = positive number or one of the symbols Euclidean, Manhattan, discrete, geographical, or infinity.
 Specifies the metric to be used in computing distances. The default is 2, the metric induced by the Euclidean norm.
 • norm = positive real or one of Euclidean, Manhattan, or infinity.
 An alias for the metric option.
 • 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 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.
 • The GraphTheory[GeometricGraphs][VisibilityGraph] command was updated in Maple 2023.
 • The metric option was introduced in Maple 2023.