Create convex hull around points

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.

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. Click the "Create Convex Hull" button to generate the convex hull of those points. Click the "Reset" button to start over.

How it works

  1. Create an input geometry such as a Multipoint object.
  2. Use GeometryEngine.convexHull(inputGeometry)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

MainActivity.kt
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
/*
 * 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
 *
 *    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.
 *
 */

package com.esri.arcgismaps.sample.createconvexhullaroundpoints

import android.os.Bundle
import android.util.Log
import androidx.appcompat.app.AppCompatActivity
import androidx.databinding.DataBindingUtil
import androidx.lifecycle.lifecycleScope
import com.arcgismaps.ApiKey
import com.arcgismaps.ArcGISEnvironment
import com.arcgismaps.Color
import com.arcgismaps.geometry.Geometry
import com.arcgismaps.geometry.GeometryEngine
import com.arcgismaps.geometry.Point
import com.arcgismaps.geometry.Multipoint
import com.arcgismaps.geometry.Polyline
import com.arcgismaps.geometry.Polygon
import com.arcgismaps.mapping.ArcGISMap
import com.arcgismaps.mapping.BasemapStyle
import com.arcgismaps.mapping.Viewpoint
import com.arcgismaps.mapping.symbology.SimpleLineSymbol
import com.arcgismaps.mapping.symbology.SimpleLineSymbolStyle
import com.arcgismaps.mapping.symbology.SimpleMarkerSymbol
import com.arcgismaps.mapping.symbology.SimpleMarkerSymbolStyle
import com.arcgismaps.mapping.symbology.SimpleFillSymbol
import com.arcgismaps.mapping.symbology.SimpleFillSymbolStyle
import com.arcgismaps.mapping.view.Graphic
import com.arcgismaps.mapping.view.GraphicsOverlay
import com.esri.arcgismaps.sample.createconvexhullaroundpoints.databinding.ActivityMainBinding
import com.google.android.material.snackbar.Snackbar
import kotlinx.coroutines.launch

class MainActivity : AppCompatActivity() {

    // set up data binding for the activity
    private val activityMainBinding: ActivityMainBinding by lazy {
        DataBindingUtil.setContentView(this, R.layout.activity_main)
    }

    // setup binding for the MapView
    private val mapView by lazy {
        activityMainBinding.mapView
    }

    // action button that creates the canvas hull
    private val createButton by lazy {
        activityMainBinding.createButton
    }

    // action button to reset the map
    private val resetButton by lazy {
        activityMainBinding.resetButton
    }

    // a red marker symbol for points
    private val pointSymbol = SimpleMarkerSymbol(SimpleMarkerSymbolStyle.Circle, Color.red, 10f)

    // a blue line symbol
    private val lineSymbol = SimpleLineSymbol(SimpleLineSymbolStyle.Solid, Color.blue, 3f)

    // a fill symbol with an empty fill for polygons
    private val fillSymbol = SimpleFillSymbol(SimpleFillSymbolStyle.Null, Color.red, lineSymbol)

    // set up the point graphic with point symbol
    private val pointGraphic = Graphic(symbol = pointSymbol)

    // init the convex hull graphic
    private val convexHullGraphic = Graphic()

    // create a graphics overlay to draw all graphics
    private val graphicsOverlay = GraphicsOverlay()

    // list to store the selected map points
    private val inputPoints = mutableListOf<Point>()

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)

        // authentication with an API key or named user is
        // required to access basemaps and other location services
        ArcGISEnvironment.apiKey = ApiKey.create(BuildConfig.API_KEY)
        lifecycle.addObserver(mapView)

        // add point and convex hull graphics to the graphics overlay
        graphicsOverlay.graphics.addAll(listOf(pointGraphic, convexHullGraphic))

        // create and add a map with topographic basemap style
        val map = ArcGISMap(BasemapStyle.ArcGISTopographic).apply {
            // set a default initial point and scale
            initialViewpoint = Viewpoint(Point(34.77, -10.24), 20e7)
        }

        // configure map view assignments
        mapView.apply {
            this.map = map
            // add the graphics overlay to the mapview
            graphicsOverlays.add(graphicsOverlay)
        }

        lifecycleScope.launch {
            // if the map load fails show the error and return
            map.load().onFailure {
                return@launch showError("Error loading map")
            }
            // capture and collect when the user taps on the screen
            mapView.onSingleTapConfirmed.collect { event ->
                event.mapPoint?.let { point ->
                    addMapPoint(point)
                }
            }
        }

        // add a click listener to create a convex hull
        createButton.setOnClickListener {
            // check if the pointGraphic's geometry is not null
            pointGraphic.geometry?.let { geometry ->
                createConvexHull(geometry)
            }
        }

        // add a click listener to reset the map
        resetButton.setOnClickListener {
            resetMap()
        }
    }

    /**
     * Adds the [point] to the map drawn as a Multipoint geometry
     */
    private fun addMapPoint(point: Point) {
        // add the new point to the points list
        inputPoints.add(point)
        // recreate the graphics geometry representing the input points
        pointGraphic.geometry = Multipoint(inputPoints)
        // enable all the action buttons, since we have at least one point drawn
        createButton.isEnabled = true
        resetButton.isEnabled = true
    }

    /**
     * Creates and draws a convex hull graphic on the map using [pointGeometry] points
     */
    private fun createConvexHull(pointGeometry: Geometry) {
        // normalize the geometry for panning beyond the meridian
        // and proceed if the resulting geometry is not null
        val normalizedPointGeometry = GeometryEngine.normalizeCentralMeridian(pointGeometry)
            ?: return showError("Error normalizing point geometry")

        // create a convex hull from the points and proceed if it's not null
        val convexHullGeometry = GeometryEngine.convexHullOrNull(normalizedPointGeometry)

        // the convex hull's geometry may be a point or polyline if the number of
        // points is less than 3, set its symbol accordingly
        convexHullGraphic.symbol = when (convexHullGeometry) {
            is Point -> {
                // set symbol to use the pointSymbol
                pointSymbol
            }
            is Polyline -> {
                // set symbol to use the lineSymbol
                lineSymbol
            }
            is Polygon -> {
                // set symbol to use the fillSymbol
                fillSymbol
            }
            else -> {
                showError("Unknown geometry for convex hull")
                null
            }
        }
        // update the convex hull graphics geometry
        convexHullGraphic.geometry = convexHullGeometry
        // disable the create button until new input points are created
        createButton.isEnabled = false
    }


    /**
     * Resets the map by clearing any drawn points, graphics and disables all buttons
     */
    private fun resetMap() {
        // remove all the selected points
        inputPoints.clear()
        // remove the geometry for the point graphic and convex hull graphics
        pointGraphic.geometry = null
        convexHullGraphic.geometry = null
        // disable the buttons
        resetButton.isEnabled = false
        createButton.isEnabled = false
    }

    private fun showError(message: String) {
        Log.e(localClassName, message)
        Snackbar.make(mapView, message, Snackbar.LENGTH_SHORT).show()
    }
}

/**
 * Simple extension property that represents a blue color
 */
private val Color.Companion.blue
    get() = fromRgba(0, 0, 255)

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