Point Inside Polyhedron

[Nicolas Robert]

Hello ,

I'm looking for an package to find out if my point is inside outside or on my Polyhedron.

There is one such package ?

Thanks

Nicolas

[Rich]

Nicolas Robert <nicolasro...@gmail.com> wrote:
> Hello ,
>
> I'm looking for an package to find out if my point is inside outside or on my Polyhedron.
>
> There is one such package ?

Maybe these commands from TclLib's math::geometry package?:

::math::geometry::pointInsidePolygon P polyline
::math::geometry::pointInsidePolygonAlt P polyline

[Nicolas Robert]

Le samedi 10 mars 2018 16:33:23 UTC+1, Rich a écrit :
> > There is one such package ?
>
> Maybe these commands from TclLib's math::geometry package?:
>
> ::math::geometry::pointInsidePolygon P polyline
> ::math::geometry::pointInsidePolygonAlt P polyline

It works for 2d geometry , I'm looking for the same thing but for 3D geometry
Thanks anyway

[Kevin Kenny]

Do you know if the polytope is convex?
Do you have face orientation a priori?

[Nicolas Robert]

Le lundi 12 mars 2018 19:17:34 UTC+1, Kevin Kenny a écrit :
>
> Do you know if the polytope is convex?

yes the polytope is convex

> Do you have face orientation a priori?

yes , I'm doing the equation of the plane for every faces

[Arjen Markus]

I have no ready solution, but if you do the following, I think you can robustly decide if the point is inside or outside the polyhedron (assumption: the polyhedron is convex and closed, otherwise the concept of inside is a bit tricky):

For each plane holding a face determine if the point in question is on the same side as all the vertices not contained in the current face. If this is the case for all such planes, the point is inside the polyhedron, otherwise it is outside.

You can easily verify this algorithm by taking a box and a point outside the box. That is how I came up with it.

This only works for convex polyhedra.

Regards,

Arjen

[Christian Gollwitzer]

Am 12.03.18 um 21:40 schrieb Nicolas Robert:

I'm sorry that the conversation went off the list, because I replied to
the email inadvertently:

>
> ok , Christian , I understand (I believe...)
> for me there is 4 steps :
>
> for each triangles :
> compute intersection ray with plane
> if intersection
> Check if point intersection is inside triangle
> incr number of intersection
> end
> loop
>
> If number of intersection is odd
> My point is Inside my Polyhedron
>
> Are you agree ?
>

Almost. You need to make sure for each intersection that it is an
intersection of the ray (one side from the starting point) with the
triangle, not the line (two sides). There are two ways:


1) If you have the normal vectors of the faces, and if they are correct:
Multiply (dot-product) the normal vector of the face with the ray unit
vector, only count if it is positive

- or -

2) Multiply the ray unit vector with (s - p), s is the intersection
point, p is the point where you want to know. Only count if positive.

Christian



>
>
>
>
>
> 2018-03-12 22:29 GMT+01:00 Christian Gollwitzer <auri...@gmx.de>:
>
> Am 12.03.18 um 22:22 schrieb nicolas robert:
>
> Thanks Christian,
>
> My faces are triangles , and this why i do plane equation , my plane is defined by three points
> For each triangle
> I do plane equation
> I calculate intersection point
> ...
>
> Sorry , but i don't understand when you say ''count how many times it
> intersects a face''
>
> For an triangle (in my case) There is one intersection or not and not 2 or 3 or ...
>
>
> With any given face, there is one intersection or none (the point is outside the triangle). You intersect a ray from the point with all faces and count how many intersect with the ray. If it is odd, you are inside, if it is even, you are outside. For the ray you can simply take the x-axis starting from your point. Make sure you count only intersections with the ray, not the line. This you see by checking that the intersection point has a larger coordinate in the direction of the ray than the starting point.
>
> Christian
>
>

[EL]

Am 12.03.18 um 21:40 schrieb Nicolas Robert:

If you have a set of hyperplanes that describe your polytope (something
like Ax = b, x >= 0 or Ax <= b, x >= 0; x = (x1, x2, ...)^T), you could
just set your point into the x vector and check whether the inequalities
are correct. If that's the case, the point is inside your polytope,
otherwise it isn't.


--
EL

[Nicolas Robert]

Thank you all for your tips and your answers
I helped this page to find my solution :
http://geomalgorithms.com/a06-_intersect-2.html
and function written in C++

Nicolas