Computational Geometry - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : System : Information : Updates : Maple 2018 : updates/Maple2018/ComputationalGeometry

Computational Geometry

Maple 2018 contains a new Computational Geometry package, based on Qhull (http://www.qhull.org). It contains functionality for programmers who intend to apply computational methods to polygons and clouds of points.

withComputationalGeometry

ConvexHull,DelaunayTriangulation,PolygonTriangulation,VoronoiDiagram

(1)

 

The VoronoiDiagram command computes and plots the Voronoi diagram of a set of input points.

mLinearAlgebra:-RandomMatrix40,2:

VoronoiDiagramm, showpoints, symbol=solidcircle, symbolsize=7,colorregions=ColorTools:-GetPaletteDalton;

 

The ConvexHull command can also compute with sets of points in higher dimensions. Here we pick some random points in 3-D, where the x-coordinates, y-coordinates, and z-coordinates are chosen according to different probability distributions: the x-coordinates are the absolute values of samples from Student's t-distribution; the y-coordinates are sampled from a standard normal distribution; and the z-coordinates come from a geometric distribution.

n  500:

s  Statistics:-Sample:

points   abs~sStudentT1, n%T | sNormal0, 1, n%T | sGeometric110, n%T

points 500 x 3 MatrixData Type: float8Storage: rectangularOrder: Fortran_order

(2)

hull  ConvexHullpoints:hull  mapface  pointsface, hull:

The following example uses polygon data from a section of the built-in world map. This finds all land areas that intersect with the given viewport.

m  DataSets:-Builtin:-WorldMap:

SetViewm, 150, 19, 50, 110:

data  plottools:-getdatad:

polygons  mapx  x3, data:

numelemspolygons;

41

(3)

There are 41 polygons representing various elements of this map. Such polygons will be displayed throughout this example, using the procedure in the Code Edit Region below, along with additional code to help with colors.

 

Remove the polygon representing the background (and the oceans).

polygons  selectp  upperboundp, 1 > 4, polygons:

numelemspolygons;

40

(4)

In this example, every other polygon has more than four vertices, so that is an easy criterion.

colors  randomColorsnumelemspolygons:

This first demonstration uses the ConvexHull command.

ConvexHullpolygons1;

192,147,146,115,112,111,86,85,84,82,74,12,11,268,267,228,217,216,215,195

(5)

It returns the indices of the points occurring in a convex hull. You can easily show these convex hulls as follows:

convexHulls  mapp  pConvexHullp, polygons:

For the rest of this document, you will work with a single polygon. Use the one for which the area of the convex hull is largest:

mainlandCanada  sortpolygons, key = p  ConvexHullp, volume1

mainlandCanada 272 x 2 MatrixData Type: float8Storage: rectangularOrder: Fortran_order

(6)

The DelaunayTriangulation of a set of points subdivides the convex hull of these points into triangles in a way that avoids long and thin triangles as much as possible.

tris  DelaunayTriangulationmainlandCanada:

dt  displayPolygonsmapt  mainlandCanadat, tris, style = polygon: dt;

This overlay shows that some of the triangles fall inside the given polygon, and some fall outside. This is because the input is interpreted as a point cloud, not an ordered polygon.

A VoronoiDiagram is a diagram that shows the dual of a Delaunay triangulation.

The PolygonTriangulation command interprets its argument as a polygon, that is, an ordered sequence of points, in contrast with the other commands mentioned so far, which each interprets its argument as an unordered set of points. It subdivides this polygon into triangles, trying to avoid triangles that are long and narrow.

triangulation  PolygonTriangulationmainlandCanada: