Convex hull

View on GitHubSample viewer app

Create a convex hull for a given set of points. The convex hull is a polygon with shortest perimeter that encloses a set of points. As a visual analogy, consider a set of points as nails in a board. The convex hull of the points would be like a rubber band stretched around the outermost nails.

Create a convex hull

Use case

A convex hull can be useful in collision detection. For example, when charting the position of two yacht fleets (with each vessel represented by a point), if their convex hulls have been precomputed, it is efficient to first check if their convex hulls intersect before computing their proximity point-by-point.

How to use the sample

Tap on the map to add points. Tap the "Create" button to generate the convex hull of those points. Tap the "Reset" button to start over.

How it works

  1. Create an input geometry such as an AGSMultipoint object.
  2. Use class AGSGeometryEngine.convexHull(for:) to create a new AGSGeometry object representing the convex hull of the input points. The returned geometry will either be a AGSPoint, AGSPolyline, or AGSPolygon based on the number of input points.

Relevant API

  • AGSGeometry
  • AGSGeometryEngine

Tags

convex hull, geometry, geometry engine, spatial analysis

Sample Code

ConvexHullViewController.swift
Use dark colors for code blocksCopy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// Copyright 2020 Esri
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

import UIKit
import ArcGIS

class ConvexHullViewController: UIViewController {
    /// The graphics overlay for the convex hull.
    let graphicsOverlay = AGSGraphicsOverlay()

    /// A simple marker symbol to display where the user tapped/clicked on the map.
    let markerSymbol = AGSSimpleMarkerSymbol(style: .circle, color: .red, size: 10)

    /// A simple line symbol for the outline of the convex hull graphic(s).
    let lineSymbol = AGSSimpleLineSymbol(style: .solid, color: .blue, width: 4)

    /// A simple fill symbol for the convex hull graphic(s) - a hollow polygon with a thick red outline.
    lazy var fillSymbol = AGSSimpleFillSymbol(style: .null, color: .red, outline: lineSymbol)

    /// The graphic for the convex hull.
    weak var convexHullGraphic: AGSGraphic?

    /// List of geometry values (MapPoints in this case) that will be used by the AGSGeometryEngine.convexHull operation.
    var inputPoints: [AGSPoint] = []

    /// The bar button item that initiates the create convex hull operation.
    @IBOutlet weak var creatButtonItem: UIBarButtonItem!

    /// The bar button item that removes the convex hull as well as the MapPoints.
    @IBOutlet weak var resetButtonItem: UIBarButtonItem!

    /// The map view managed by the view controller.
    @IBOutlet weak var mapView: AGSMapView! {
        didSet {
            mapView.map = makeMap()
            mapView.graphicsOverlays.add(graphicsOverlay)
            mapView.touchDelegate = self
        }
    }

    /// Creates a map.
    ///
    /// - Returns: A new `AGSMap` object.
    func makeMap() -> AGSMap {
        let map = AGSMap(basemapStyle: .arcGISTopographic)
        return map
    }

    /// Called in response to the Create convex hull button being tapped.
    @IBAction func createConvexHull() {
        if let normalizedPoints = AGSGeometryEngine.normalizeCentralMeridian(of: AGSMultipoint(points: inputPoints)),
            let convexHullGeometry = AGSGeometryEngine.convexHull(for: normalizedPoints) {
            // Change the symbol depending on the returned geometry type of the convex hull.
            let symbol: AGSSymbol
            switch convexHullGeometry.geometryType {
            case .point:
                symbol = markerSymbol
            case .polyline:
                symbol = lineSymbol
            default:
                symbol = fillSymbol
            }
            // Remove the existing graphic for convex hull if there is one.
            if let existingGraphic = convexHullGraphic {
                graphicsOverlay.graphics.remove(existingGraphic)
            }
            let graphic = AGSGraphic(geometry: convexHullGeometry, symbol: symbol)
            convexHullGraphic = graphic
            graphicsOverlay.graphics.add(convexHullGraphic!)
            creatButtonItem.isEnabled = false
        } else {
            // Present an alert if there is a problem with AGSGeometryEngine operations.
            self.presentAlert(title: nil, message: "Geometry Engine Failed!")
        }
    }

    /// Called in response to the Reset button being tapped.
    @IBAction func reset() {
        // Clear the existing points and graphics.
        inputPoints.removeAll()
        graphicsOverlay.graphics.removeAllObjects()
        // Reset button states.
        resetButtonItem.isEnabled = false
        creatButtonItem.isEnabled = false
    }

    // MARK: UIViewController

    override func viewDidLoad() {
        super.viewDidLoad()
        // Add the source code button item to the right of navigation bar.
        (self.navigationItem.rightBarButtonItem as? SourceCodeBarButtonItem)?.filenames = ["ConvexHullViewController"]
    }
}

extension ConvexHullViewController: AGSGeoViewTouchDelegate {
    // MARK: - AGSGeoViewTouchDelegate
    func geoView(_ geoView: AGSGeoView, didTapAtScreenPoint screenPoint: CGPoint, mapPoint: AGSPoint) {
        // Add the map point to the array that will be used by the AGSGeometryEngine.convexHull operation.
        inputPoints.append(mapPoint)
        if !inputPoints.isEmpty {
            resetButtonItem.isEnabled = true
            creatButtonItem.isEnabled = true
        }
        // Create a new graphic for the spot where the user tapped on the map using the simple marker symbol.
        let userTappedGraphic = AGSGraphic(geometry: mapPoint, symbol: markerSymbol)
        graphicsOverlay.graphics.add(userTappedGraphic)
    }
}

Your browser is no longer supported. Please upgrade your browser for the best experience. See our browser deprecation post for more details.