Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


max343

Member Since 04 Nov 2012
Offline Last Active Jun 27 2013 11:14 PM

Posts I've Made

In Topic: Point inside convex polyhedron defined by planes

22 February 2013 - 03:15 PM

I don't have inequalities in my solution. What I suggested disregards direction because it already assumes that the feasible region of the half spaces defines a convex polyhedron. If we'd flip one of the inequalities, the feasible region would be empty.

In Topic: Point inside convex polyhedron defined by planes

22 February 2013 - 01:28 PM

But the simplex algorithm doesn't search through interior points, just through the boundary. Phase I just finds a boundary vertex of the feasible region or returns that the problem is infeasible.
OP wanted something close to the centroid, this is distinctly an interior point.

In Topic: Point inside convex polyhedron defined by planes

22 February 2013 - 03:53 AM

This sounds similar to finding a feasible solution to a linear-programming problem, so I am sure there is literature about it. This seems to be called "Phase I" in the simplex algorithm. I read the description in Wikipedia, but I am not sure I understand it.

I don't think that Simplex algorithm is the best choice here, since it searches for maximum on the boundary, while OP wanted some interior point.

In Topic: Point inside convex polyhedron defined by planes

21 February 2013 - 07:53 PM

BTW, sometimes it makes more sense to find the center of the circumscribed sphere rather than the centroid (which gives bias to clustered vertices). In this case you can do this:
1. Find x0 as I previously described.
2. Solve the weighted minimization problem with the weights: Wi = |Ni*x0-Di|

In Topic: Point inside convex polyhedron defined by planes

21 February 2013 - 06:02 AM

I haven't tested it, but maybe you can do this:

Your plane equations are: Ni*x-Di, with Ni normalized row vectors, Di are scalars, and x is a column vector.
Now minimize the sum of squared distances with respect to x: S=sum[(Ni*x-Di)^2]
Obtain: x=((sum[Ni^T*Ni])^+) * sum[Di*Ni^T]
I'm almost sure that the pseudo-inverse is not required (and you can take the regular inverse), because this reminds me a lot of SVD. However, this is just a hunch.

EDIT: Yup, the matrix should be invertible for any closed polyhedrons. No need for pseudo-inverse.

PARTNERS