Create convex hull around points

View on GitHub

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.

Image of create convex hull around points

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 a Multipoint object.
  2. Use convexHull(for:) method to create a new Geometry object representing the convex hull of the input points. The returned geometry will either be a Point, Polyline, or Polygon based on the number of input points.

Relevant API

  • Geometry
  • GeometryEngine

Tags

convex hull, geometry, spatial analysis

Sample Code

CreateConvexHullAroundPointsView.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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// Copyright 2023 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
//
//   https://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 ArcGIS
import SwiftUI

struct CreateConvexHullAroundPointsView: View {
    /// The view model for the sample.
    @StateObject private var model = Model()

    /// A Boolean value indicating whether the create button can be pressed.
    @State private var createIsDisabled = true

    /// A Boolean indicate whether the reset button can be pressed.
    @State private var resetIsDisabled = true

    var body: some View {
        // Create a map view to display the map.
        MapView(map: model.map, graphicsOverlays: model.graphicsOverlays)
            .onSingleTapGesture { _, mapPoint in
                model.inputPoints.append(mapPoint)
                model.pointsGraphicsOverlay.addGraphic(Graphic(geometry: mapPoint))
                createIsDisabled = false
                resetIsDisabled = false
            }
            .toolbar {
                ToolbarItemGroup(placement: .bottomBar) {
                    Button("Create") {
                        model.createConvexHull()
                        createIsDisabled = true
                    }
                    .disabled(createIsDisabled)
                    Button("Reset") {
                        model.reset()
                        createIsDisabled = true
                        resetIsDisabled = true
                    }
                    .disabled(resetIsDisabled)
                }
            }
    }
}

private extension CreateConvexHullAroundPointsView {
    /// The view model for this sample.
    private class Model: ObservableObject {
        /// A map with a topographic basemap.
        let map: Map

        /// An array of input points to be used in creating the convexHull.
        var inputPoints: [Point] = []

        /// An array that contains the graphics overlays for the sample.
        var graphicsOverlays: [GraphicsOverlay] {
            return [pointsGraphicsOverlay, convexHullGraphicsOverlay]
        }

        /// The graphics overlay for the input points graphics.
        let pointsGraphicsOverlay: GraphicsOverlay

        /// The graphics overlay for the convex hull graphic.
        private let convexHullGraphicsOverlay: GraphicsOverlay

        /// A red simple marker symbol to display where the user tapped on the map.
        private let markerSymbol: SimpleMarkerSymbol

        /// A blue simple line symbol for the outline of the convex hull graphic.
        private let lineSymbol: SimpleLineSymbol

        /// A hollow polygon simple fill symbol for the convex hull graphic.
        private var fillSymbol: SimpleFillSymbol

        init() {
            map = Map(basemapStyle: .arcGISTopographic)

            markerSymbol = SimpleMarkerSymbol(style: .circle, color: .red, size: 10)
            lineSymbol = SimpleLineSymbol(style: .solid, color: .blue, width: 4)
            fillSymbol = SimpleFillSymbol(style: .noFill, outline: lineSymbol)

            pointsGraphicsOverlay = GraphicsOverlay()
            pointsGraphicsOverlay.renderer = SimpleRenderer(symbol: markerSymbol)
            convexHullGraphicsOverlay = GraphicsOverlay()
        }

        /// Reset the points and graphics.
        func reset() {
            inputPoints.removeAll()
            pointsGraphicsOverlay.removeAllGraphics()
            convexHullGraphicsOverlay.removeAllGraphics()
        }

        /// Create the convex hull graphic using the inputPoints.
        func createConvexHull() {
            // Normalize points and create convex hull geometry.
            if let normalizedPoints = GeometryEngine.normalizeCentralMeridian(of: Multipoint(points: inputPoints)),
               let convexHullGeometry = GeometryEngine.convexHull(for: normalizedPoints) {
                // Set the symbol depending on the geometry type of the convex hull.
                let symbol: Symbol?
                switch convexHullGeometry {
                case is Point:
                    symbol = markerSymbol
                case is Polyline:
                    symbol = lineSymbol
                case is ArcGIS.Polygon:
                    symbol = fillSymbol
                default:
                    symbol = nil
                }

                // Remove the existing graphic for convex hull.
                convexHullGraphicsOverlay.removeAllGraphics()

                // Create the convex hull graphic.
                let convexHullGraphic = Graphic(geometry: convexHullGeometry, symbol: symbol)
                convexHullGraphicsOverlay.addGraphic(convexHullGraphic)
            }
        }
    }
}

#Preview {
    NavigationStack {
        CreateConvexHullAroundPointsView()
    }
}

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