Stack Overflow
Stack Overflow

Questions tagged [convex]

Anything related to convex geometric shapes. A shape in an Euclidean space is convex if, given two points A and B, every point of the segment AB belongs to the shape, i.e. AB is a subset of the shape.

Anything related to convex geometric shapes.

A shape in an Euclidean space is convex if, given two points A and B, every point of the segment AB belongs to the shape, i.e. AB is a subset of the shape.

See Wikipedia on:

139 questions
23
votes
7 answers

How do I determine if two convex polygons intersect?

Suppose there are a number of convex polygons on a plane, perhaps a map. These polygons can bump up against each other and share an edge, but cannot overlap. To test if two polygons P and Q overlap, first I can test each edge in P to see if it…
Scottie T
  • 11,729
  • 10
  • 45
  • 59
22
votes
3 answers

What's a good convex optimization library?

I am looking for a C++ library, and I am dealing with convex objective and constraint functions.
areslp
  • 383
  • 1
  • 4
  • 17
19
votes
4 answers

Approximation of a solid by a union of spheres

I've got a 3D solid, represented as the union of a set of polyhedral convex hulls. (Or a single convex, if that makes things easier.) I'd like to approximate that solid as the union of a set of spheres, in a way which minimizes both the number of…
Sneftel
  • 40,271
  • 12
  • 71
  • 104
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
11
votes
2 answers

3D collision detection : convex hull vs convex hull , need Position and Normal

I want to know an approximate 3D position and 3D normal of collision site between two 3D convex hulls (A vs B). The CPU in parenthesis shows relative CPU-time needed in my finished program. Part 1: Early-out (CPU 1%) In the first step, I use a…
javaLover
  • 6,347
  • 2
  • 22
  • 67
9
votes
2 answers

Alpha shapes in 3D

Is there an "alpha shape" function in 3 dimensions in python, other than the CGAL python bindings? Alternatively, is there a way to extend the example below into 3D? 2D example: draw a smooth polygon around data points in a scatter plot, in…
skytaker
  • 4,159
  • 1
  • 21
  • 31
8
votes
1 answer

find the maximum convex area

My question is very similar to Plow's Question; but with this difference: How can I find the maximum convex area that can fit inside a non-convex region? For an example, consider this non-convex region: Any ideas or solution would be appreciated,…
Zakhar
  • 313
  • 1
  • 4
  • 12
7
votes
2 answers

Division of a convex hull into two separate parts

I am trying to solve quite a difficult problem for me. I'm not new to programming, but I don't really know how to figure out this problem. It's given a set of points (point []) with Xi and Yi coordinates as an input. The program has to output…
user2943215
6
votes
4 answers

Scipy: Centroid of convex hull

how can I calculate the centroid of a convex hull using python and scipy? All I found are methods for computing Area and Volume. regards,frank.
OD IUM
  • 1,555
  • 2
  • 16
  • 26
6
votes
2 answers

How to find out whether a triangle mesh is concave or not?

Given a three dimensional triangle mesh, how can I find out whether it is convex or concave? Is there an algorithm to check that? If so it would be useful to define a tolerance range to ignore small concavities. Image Source:…
danijar
  • 32,406
  • 45
  • 166
  • 297
6
votes
2 answers

Finding the Oriented Bounding Box of a Convex Hull in XNA Using Rotating Calipers

Perhaps this is more of a math question than a programming question, but I've been trying to implement the rotating calipers algorithm in XNA. I've deduced a convex hull from my point set using a monotone chain as detailed on wikipedia. Now I'm…
MattB
  • 157
  • 1
  • 8
5
votes
4 answers

Find max y coordinate of a convex polygon

I have an array V[1,2,....,n], where each element of the array represents a vertex of a convex polygon in the form of a coordinate pair (x,y). It is given that V[1] is the vertex with the minimum x coordinate and that the vertices V[1,2,....,n] are…
Ank
  • 1,864
  • 4
  • 31
  • 51
5
votes
2 answers

Local and global minima of the cost function in logistic regression

I'm misunderstanding the idea behind the minima in the derivation of the logistic regression formula. The idea is to increase the hypothesis as much as possible (i.e correct prediction probability close to 1 as possible), which in turn requires…
Keir Simmons
  • 1,634
  • 7
  • 21
  • 37
5
votes
2 answers

How do I determine if a polyhedron is convex?

I'm looking for an efficient algorithm that determines if a polyhedron is convex. I started by checking that the Euler characteristic is 2. And I'm also checking that every face is convex. But that still doesn't catch a lot of cases.
Charles Taylor
  • 686
  • 6
  • 23
5
votes
2 answers

Libgdx polygon triangulation

Ok, so I have a polygon (simple but concave) that I'm trying to cut into triangles to make it collide with an other polygon. I knew my polygone was concave, so i decided to use LibGDX EarClippingTriangulator to manage to cut it into triangles. So,…
Sebastien Servouze
  • 720
  • 4
  • 13
1
2 3
…
9 10