Create a GeometryBasics convex polygon from an unordered set of points

General Usage
1

I have a set of four 2d points and want to create a quadrilateral. Currently, I manually order the input points to ensure it is convex. Is there a function in GeometryBasiscs that crates a convex polygon from an unordered set of 2d points? If I don’t sort them properly then the lines intersect like an X

2

If you have a set of unordered 2d points, that are vertices of a convex polygon, then you must first reorder them
as follows:

  • calculate the center of mass, c, of the given set of points;
  • calculate the coordinates of vectors \vec{cp}=p-c, where p runs over
    the points, given as a vector of vectors;
  • calculate the angle of each vector \vec{cp}=(x,y) with the positive x-axis, as atan(y, x).
  • sortperm the the computed angles, α, and a get the index vector idx.
  • points[idx] represent the ordered points, and now you can plot the associated polygon with your favorite plotting library.
    I’m using PlotlyJS:
using PlotlyJS, Statistics
function reorderpoints(points)
   x= getindex.( points, 1)
   y= getindex.( points, 2) 
   c = [mean(x), mean(y)]
   v = [p-c for p in points]
   α =[atan(u[2], u[1])  for u in v]
   idx=sortperm(α)
   points[idx]
end 

points= [[-0.35,   1.6],
         [1.0,    0.0],
         [-0.4,   -1.3],
         [-1.5,   -1.2],
         [0.75,   1.5],
         [-1.0,    0.8]]
pts =reorderpoints(points)
push!(pts, pts[1])
fig =Plot(scatter(x=getindex.(pts, 1), 
                  y=getindex.(pts, 2), 
                  fill="toself", 
                  fillcolor="RoyalBlue"),
    Layout(width=400, height=400))

convexpolygon

3 Likes