Convex Hull with Rhino Python

by Tuğrul Yazar | July 28, 2017 01:08

# Drawing the Convex Hull of Given Points
# 28.07.2017 www.designcoding.net - Tugrul Yazar
import rhinoscriptsyntax as rs
points = rs.GetPointCoordinates("Select points")
a = min(points)
start = a
while a:
    o = a
    a = points[0]
    for b in points:
        if (a[0]-o[0])*(b[1]-o[1])-(a[1]-o[1])*(b[0]-o[0]) < 0: a = b
    rs.AddLine(o,a)
    if a == start: break

This was the Design Mathematics[1] exercise today. I found a simple algorithm that creates the desired polyline of the given points. In the first lines, variables are defined. We find the first element of the set we are looking for. The leftmost point in the given point set must be the first element of the convex hull. Next, in the While loop, we start with the first point and iterate through all other points to make the special if check there. While exiting the for loop for each point, we have the resulting point in the desired set. Therefore, we draw a line to represent the hull. At the end of this outer loop, we complete all the points and lines. This algorithm deserves a much better explanation, I know.

According to Wikipedia: “In computational geometry[2], a number of algorithms are known for computing the convex hull for a finite set of points and for other geometric objects. Computing the convex hull means constructing an unambiguous, efficient representation of the required convex shape.”. The one I am using here is not an efficient algorithm since it checks every point in the set over and over again. There are many other algorithms doing the same job. I preferred this one since it is very short. Also, it is good at explaining the students about several programming concepts. For and While loops and if conditionals. I hope I will explain this code in a better context of linear algebra in the future. Nowadays, I am trying to prepare it.

Source URL: https://www.designcoding.net/convex-hull-with-rhino-python/