GraphTheory[GeometricGraphs] - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GeometricGraphs : GraphTheory/GeometricGraphs/VisibilityGraph

GraphTheory[GeometricGraphs]

  

VisibilityGraph

  

construct a visibility graph

 

Calling Sequence

Parameters

Options

Description

Definition

Examples

References

Compatibility

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.

withGraphTheory:

withGeometricGraphs:

P391,374,240,431,252,340,374,320,289,214,134,390,68,186,154,259,161,107,435,108,208,148,295,160,421,212,441,303

P391,374,240,431,252,340,374,320,289,214,134,390,68,186,154,259,161,107,435,108,208,148,295,160,421,212,441,303

(1)

plots:-displayplottools:-polygonP,style=line

VGVisibilityGraphP

VGGraph 1: an undirected unweighted graph with 14 vertices and 36 edge(s)

(2)

DrawGraphVG

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.

See Also

ComputationalGeometry

GeometricGraphs