1
$\begingroup$

Given a set of 2D points, I am trying to find the smallest convex hull that encloses an arbitrary point (which, in the general case, is not part of the set). By 'smallest convex hull' I am ideally thinking about its area, but I believe using the perimeter might also be good enough for my purposes.

The problem specification is quite simple, but it seems complex to implement such algorithm. I tried to do modify the jarvis march algorithm, but I didn't find a solution so far.

Appreciate any suggestions. Maybe there is a known algorithm for this?

Illustration of the problem (black are the points of the set, red is the target point and also the smallest convex hull

enter image description here

$\endgroup$
4
  • 1
    $\begingroup$ Can you find the 3 nearest neighbors and then try the convex hull of that set? $\endgroup$
    – nicoguaro
    Dec 7, 2021 at 23:42
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Dec 7, 2021 at 23:51
  • 1
    $\begingroup$ Using the three nearest neighbors is no guarantee that you'll find the smallest enclosing set. This is a difficult combinatorial optimization problem. $\endgroup$ Dec 8, 2021 at 5:13
  • 2
    $\begingroup$ Consider 3 nearly colinear points that would form a triangle sliver with a very small area, but nevertheless contain your point. Do you want to include this and other pathological cases? If not you need to add some constraints. Try a Delaunay triangulation and pick the facet containing your point. Maybe that's close enough? $\endgroup$
    – Charlie S
    Dec 8, 2021 at 14:37

2 Answers 2

2
$\begingroup$

It's often best to start with the simplest, easiest-to-implement algorithm you can think of to test that your intuition on a problem is correct and that what you've built will match what you need.

In this case, that's using a O(N³) algorithm to look at all combinations of points and choose the three that form a containing triangle of minimal area.

Doing that on random point sets gives solutions like these:

Smallest containing triangle

Smallest containing triangle

Smallest containing triangle

If this is what you wanted, then you can think about finding a faster solution. If not, you probably need additional constraints. The Delaunay triangulation, for instance, maximizes the minimal angle present in the triangulation. You can find the containing triangle using methods described here.

Implementation

#!/usr/bin/env python3
import matplotlib.pyplot as plt
import numpy as np

def gen_data(N: int) -> np.ndarray:
  return np.random.rand(N,2)

def sign(p1: np.ndarray, p2: np.ndarray, p3: np.ndarray) -> bool:
    return (p1[0] - p3[0]) * (p2[1] - p3[1]) - (p2[0] - p3[0]) * (p1[1] - p3[1])

def point_in_triangle(pt: np.ndarray, tri_pts: np.ndarray) -> bool:
    d1 = sign(pt, tri_pts[0,:], tri_pts[1,:])
    d2 = sign(pt, tri_pts[1,:], tri_pts[2,:])
    d3 = sign(pt, tri_pts[2,:], tri_pts[0,:])

    has_neg = (d1 < 0) or (d2 < 0) or (d3 < 0)
    has_pos = (d1 > 0) or (d2 > 0) or (d3 > 0)

    return not (has_neg and has_pos)

def heron_formula(pts: np.ndarray) -> float:
  a = np.sqrt((pts[0,0]-pts[1,0])**2 + (pts[0,1]-pts[1,1])**2)
  b = np.sqrt((pts[1,0]-pts[2,0])**2 + (pts[1,1]-pts[2,1])**2)
  c = np.sqrt((pts[2,0]-pts[0,0])**2 + (pts[2,1]-pts[0,1])**2)
  s = (a + b + c) / 2
  return np.sqrt(s*(s-a)*(s-b)*(s-c))

def smallest_triangle(pt_to_find: np.ndarray, pts: np.ndarray) -> np.ndarray:
  min_area_tri = np.inf
  tri_pts = None
  for i in range(len(pts)):
    for j in range(i+1,len(pts)):
      for k in range(j+1,len(pts)):
        if point_in_triangle(pt_to_find, pts[(i,j,k),:]):
          area = heron_formula(pts[(i,j,k),:])
          if area < min_area_tri:
            min_area_tri = area
            tri_pts = pts[(i,j,k),:].copy()
  if tri_pts is None:
    raise Exception("No containing triangle found!")
  else:
    return tri_pts

pts = gen_data(100)
pt_to_find = gen_data(1)[0,:]
smallest = smallest_triangle(pt_to_find, pts)
print("Best area", heron_formula(smallest))

# Add first point to the end for drawing purposes
smallest = np.vstack((smallest, smallest[0,:]))

plt.scatter(pts[:,0], pts[:,1])
plt.scatter(pt_to_find[0], pt_to_find[1], c="red", s=20)
plt.plot(smallest[:,0], smallest[:,1], '-')
plt.show()
$\endgroup$
2
$\begingroup$

I don't understand the downvote, the community bot should have been smarter.

Anyway, here is a very quick and dirty method.

  • First of all, a convex hull can be discretized into triangles using its vertices, so what you are looking for is really the minimal triangle.
  • Second, a few sketches led me to believe that the point (from the existing point set) that is closest to your arbitrary point must be a vertex of the minimal triangle, call it P0 and your arbitrary point PA.
  • Third, use the ray P0-PA and its perpendicular at PA to partition your points into three quadrants. P0 is in one quadrant, so you select one point from each of the remaining two quadrants for the other two triangle vertices (according to the closest distance to PA). Note: the term quadrant is not used in a very precise way.

Counter-examples, where the above method fails to be at least a good approximation, are welcome.

illustration updated

$\endgroup$
2
  • $\begingroup$ "point (from the existing point set) that is closest to your arbitrary point must be a vertex of the minimal triangle" <-- This is incorrect. See my answer. $\endgroup$
    – Richard
    Dec 8, 2021 at 17:55
  • 1
    $\begingroup$ @Richard You are right indeed, 2 out of your 3 examples show the closest point does not contribute to the triangle. It also implies that one cannot solve this problem "locally". Points very far from the target point could form the solution. For example, a triangle formed by $(a,0)$ and $(-a, \pm \epsilon/a)$ always contains the origin, and its area can be arbitrarily small. $\endgroup$
    – Taozi
    Dec 8, 2021 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.