The Convex Hull Algorithm leads to the smallest convex area (Polygon) that includes all the points in the dataset. In the given table, a list of data points is provided. Extract the points that lie on the vertices of the smallest convex area created by the algorithm described below. The algorithm begins with i=0 and a point p0 known to be on the convex hull, such as the leftmost point. It selects the point pi+1 such that all points are to the right of the line pi pi+1. This point can be found by comparing the polar angles of all points with respect to point pi taken as the center of polar coordinates. Letting i=i+1, and repeating until one reaches ph=p0 again, yields the convex hull in h steps.
📌 Challenge Details and Links
Challenge Number: 80
Challenge Difficulty: ⭐⭐⭐⭐⭐
📥Download Sample File
📥Link to the solutions on LinkedIn
Solving the challenge of Convex Hulls (Gift Wrapping Algorithm)! with Excel
Excel solution 1 for Convex Hulls (Gift Wrapping Algorithm)!, proposed by Bo Rydobon 🇹🇭:
=LET(z,
SORT(
B3:C25,
2
),
s,
SEQUENCE(
ROWS(
z
)
),R,
LAMBDA(r,
a,
LET(b,
TAKE(
a,
-1,
1
),
f,
VSTACK(
FILTER(
s,
ISNA(
XMATCH(
s,
TAKE(
a,
,
1
)
)
)
),
1
),m,
ATAN2(INDEX(
z,
f,
1
)-INDEX(
z,
b,
1
),
INDEX(
z,
f,
2
)-INDEX(
z,
b,
2
)),x,
XLOOKUP(
0,
MOD(
m-TAKE(
a,
-1,
-1
),
2*PI()
),
HSTACK(
f,
m
),
,
1
),
IF(
@x=1,
TAKE(
a,
,
1
),
r(
r,
VSTACK(
a,
x
)
)
))),CHOOSEROWS(
z,
R(
R,
{1,
0}
)
))Excel solution 2 for Convex Hulls (Gift Wrapping Algorithm)!, proposed by Bo Rydobon 🇹🇭:
=LET(z,
SORT(
B3:C25,
{2,
1}
),
s,
SEQUENCE(
ROWS(
z
)
),CHOOSEROWS(z,
TOCOL(SCAN(,
s,
LAMBDA(a,
_,
LET(d,
MOD(ATAN2(TAKE(
z,
,
1
)-INDEX(
z,
a,
1
),
DROP(
z,
,
1
)-INDEX(
z,
a,
2
)),
2*PI())/7,XLOOKUP(
MOD(
a,
1
),
d,
s+d,
,
1
)))),
3)))Excel solution 3 for Convex Hulls (Gift Wrapping Algorithm)!, proposed by محمد حلمي:
=LET(
e,
SORT(
B3:C25,
2
),REDUCE(B2:C2,
SEQUENCE(
10
),
LAMBDA(a,
v,
LET(
u,
TAKE(
a,
-1,
1
),y,
TAKE(
a,
-1,
-1
),j,
FILTER(
e,
ISNA(
XMATCH(
TAKE(
e,
,
1
)&TAKE(
e,
,
-1
),
u&y
)
)
),i,
IFERROR(ATAN2(TAKE(
j,
,
1
)-u,
TAKE(
j,
,
-1
)-y),
""),UNIQUE(
VSTACK(
a, XLOOKUP(
IF(
SUM(
N(
i>=1
)
)>3,
0,
-9
),
i,
j,
,
1
)
)
)))))Excel solution 4 for Convex Hulls (Gift Wrapping Algorithm)!, proposed by Julian Poeltl:
=LET(X,
B3:B25,
Y,
C3:C25,
V,
ROWS(
X
),
I,
SEQUENCE(
V
),
MinY,
MIN(
Y
),
MinYX,
XLOOKUP(
MinY,
Y,
X
),
SPA,
IFERROR(ATAN2(X-MinYX,
Y-MinY),
0),
SP,
SORTBY(
I,
SPA,
-1
),
ItPA,
LAMBDA(A,
LET(XP,
INDEX(
X,
A
),
YP,
INDEX(
Y,
A
),
PA,
IFERROR(ATAN2(X-XP,
Y-YP),
0),
TAKE(
FILTER(
SORTBY(
I,
PA,
-1
),
SORTBY(
I,
PA,
-1
)<>A
),
1
))),
S,
REDUCE(
VSTACK(
XMATCH(
MinYX&MinY,
X&Y
),
TAKE(
SP,
1
)
),
SEQUENCE(
V,
,
0,
0
),
LAMBDA(
A,
B,
VSTACK(
B+ItPA(
TAKE(
A,
1
)
),
A
)
)
),
XM,
XMATCH(
1,
S,
,
-1
),
R,
CHOOSEROWS(
S,
SEQUENCE(
V-XM+1,
,
XM+1
)
),
HSTACK(
INDEX(
X,
R
),
INDEX(
Y,
R
)
))Solving the challenge of Convex Hulls (Gift Wrapping Algorithm)! with Python
Python solution 1 for Convex Hulls (Gift Wrapping Algorithm)!, proposed by Konrad Gryczan, PhD:
import pandas as pd
import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt
path = "CH-80 Convex Hulls.xlsx"
input = pd.read_excel(path, usecols="B:C", nrows=24, skiprows = 1)
test = pd.read_excel(path, usecols="E:F", nrows=5, skiprows = 1)
test.columns = ['X', 'Y']
points = input[['X', 'Y']].values
hull = ConvexHull(points)
# Plotting the convex hull
plt.plot(points[:,0], points[:,1], 'o', label='Points')
for simplex in hull.simplices:
plt.plot(points[simplex, 0], points[simplex, 1], 'k-')
plt.xlabel('X-axis')
plt.ylabel('Y-axis')
plt.title('Convex Hull of DataFrame Points')
plt.legend()
plt.show()
# Validation
vertices = pd.DataFrame(points[hull.vertices], columns=['X', 'Y']).sort_values(by=['X', 'Y']).reset_index(drop=True)
test = test.sort_values(by=['X', 'Y']).reset_index(drop=True)
print(test.equals(vertices)) # TruePython solution 2 for Convex Hulls (Gift Wrapping Algorithm)!, proposed by Alejandro Campos:
df=xl("B3:C25")
points=df.to_numpy()
def gift_wrapping(points):
n = len(points)
hull = []
l = np.argmin(points[:, 0])
p = l
while True:
hull.append(points[p])
q = (p + 1) % n
for i in range(n):
if (orientation(points[p], points[i], points[q]) == 2):
q = i
p = q
if (p == l):
break
return np.array(hull)
def orientation(p, q, r):
val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
if val == 0:
return 0 # colinear
elif val > 0:
return 1 # horario
else:
return 2 # antihorario
hull = gift_wrapping(points)
hullSolving the challenge of Convex Hulls (Gift Wrapping Algorithm)! with R
R solution 1 for Convex Hulls (Gift Wrapping Algorithm)!, proposed by Konrad Gryczan, PhD:
library(tidyverse)
library(readxl)
library(patchwork)
path = "files/CH-80 Convex Hulls.xlsx"
input = read_excel(path, range = "B2:C25")
test = read_excel(path, range = "E2:F7")
hull_indices = chull(input$X, input$Y)
hull_vertices = input[hull_indices,]
hull_vertices = rbind(hull_vertices, hull_vertices[1,])
# validation ----
hull_vertices_val = hull_vertices %>% distinct() %>% arrange(X, Y)
test = test %>% arrange(X, Y)
identical(hull_vertices_val, test)
R solution 2 for Convex Hulls (Gift Wrapping Algorithm)!, proposed by Anil Kumar Goyal:
nformative challenge.
Strategy similar to Konrad Gryczan, PhD but using tidyverse piped synatax
df <- read_excel("OM Challanges/CH-80 Convex Hulls.xlsx", range = "B2:C25")
df %>%
slice(chull(X, Y))