Stack Overflow
Stack Overflow

Questions tagged [convex-hull]

Convex-hull of a set of points X in a Euclidean space is the convex set with smallest area that contains all points of X.

538 questions
177
votes
16 answers

How to tell whether a point is to the right or left side of a line

I have a set of points. I want to separate them into 2 distinct sets. To do this, I choose two points (a and b) and draw an imaginary line between them. Now I want to have all points that are left from this line in one set and those that are right…
Aaginor
  • 4,516
  • 11
  • 51
  • 75
70
votes
12 answers

What's an efficient way to find if a point lies in the convex hull of a point cloud?

I have a point cloud of coordinates in numpy. For a high number of points, I want to find out if the points lie in the convex hull of the point cloud. I tried pyhull but I cant figure out how to check if a point is in the ConvexHull: hull =…
AME
  • 2,499
  • 5
  • 29
  • 45
34
votes
12 answers

Create non-intersecting polygon passing through all given points

Suppose I have an array of points in random order, and I need to find a polygon (by sorting them, such that every adjacent pair represents a side) which passes through all of the points, and its sides are non-intersecting of course. I tried to do it…
max
  • 4,248
  • 2
  • 25
  • 38
27
votes
6 answers

Convex hull of (longitude, latitude)-points on the surface of a sphere

Standard convex hull algorithms will not work with (longitude, latitude)-points, because standard algorithms assume you want the hull of a set of Cartesian points. Latitude-longitude points are not Cartesian, because longitude "wraps around" at the…
Maxy-B
  • 2,772
  • 1
  • 25
  • 33
24
votes
4 answers

How to find convex hull in a 3 dimensional space

Given a set of points S (x, y, z). How to find the convex hull of those points ? I tried understanding the algorithm from here, but could not get much. It says: First project all of the points onto the xy-plane, and find an edge that is definitely…
Ninja420
  • 3,542
  • 3
  • 22
  • 34
19
votes
2 answers

Convex hull area in Python?

I have a set of points A. I get the convex hull CH_A of A. Then, I have extra points, point set B. I add B into A and get a bigger point set. I obtain the convex hull CH_AB of this bigger set containing both A and B. I want to quantify how much I…
Sibbs Gambling
  • 19,274
  • 42
  • 103
  • 174
18
votes
2 answers

In scipy's ConvexHull, what does "area" measure?

The value of the "area" attribute in scipy ConvexHull (see http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html) object does not seem to be (what I understand to be) the area of the convex hull. On the other hand, the…
mjandrews
  • 2,392
  • 4
  • 22
  • 39
18
votes
3 answers

qhull Library - C++ Interface

The qhull library ( qhull.org) has several examples to start in his website, but all the information regarding to the C++ is not very useful to me. I am trying to make a simple convex Hull of 3D points that I read from a file, I can´t use the…
Nuno Pessanha Santos
  • 315
  • 2
  • 10
16
votes
4 answers

The minimum perimeter convex hull of a subset of a point set

Given n points on the plane. No 3 are collinear. Given the number k. Find the subset of k points, such that the convex hull of the k points has minimum perimeter out of any convex hull of a subset of k points. I can think of a naive method runs in…
Chao Xu
  • 2,156
  • 2
  • 22
  • 31
15
votes
2 answers

Intersection of nD line with convex hull in Python

I have created a convex hull using scipy.spatial.ConvexHull. I need to compute the intersection point between the convex hull and a ray, starting at 0 and in the direction of some other defined point. The convex hull is known to contain 0 so the…
user2133814
  • 2,431
  • 1
  • 24
  • 34
15
votes
4 answers

Finding largest subset of points forming a convex polygon

I'm looking for an algorithm for finding largest subset of points (by largest i mean in number) that form a convex polygon from the given set of point. I think this might be solvable using DP but i'm not sure. Is it possible to do this in O(n^3)…
zeulb
  • 637
  • 1
  • 7
  • 23
14
votes
6 answers

Triangulate a set of points with a concave domain

Setup Given some set of nodes within a convex hull, assume the domain contains one or more concave areas: where blue dots are points, and the black line illustrates the domain. Assume the points are held as a 2D array points of length n, where n is…
Daniel R. Livingston
  • 1,227
  • 14
  • 36
13
votes
8 answers

Convex hull of 4 points

I would like an algorithm to calculate the convex hull of 4 2D points. I have looked at the algorithms for the generalized problem, but I wonder if there is a simple solution for 4 points.
Jonathan Udy
  • 133
  • 1
  • 4
12
votes
2 answers

Compute curvature of a bent pipe using image processing (Hough transform parabola detection)

I'm trying to design a way to detect this pipe's curvature. I tried applying hough transform and found detected line but they don't lie along the surface of pipe so smoothing it out to fit a beizer curve is not working .Please suggest some good way…
Nikita Chopra
  • 440
  • 9
  • 22
12
votes
2 answers

Volume of convex hull with QHull from SciPy

I'm trying to get the volume of the convex hull of a set of points using the SciPy wrapper for QHull. According to the documentation of QHull, I should be passing the "FA" option to get the total surface area and volume. Here is what I get.. What…
Diana
  • 1,301
  • 1
  • 9
  • 21
1
2 3
…
35 36