How to determine whether a 3d point lies within a set of 3d points (a modeled room)

Hello, I have a set of coordinates that describe a room. I want to calculate volume of that room using Monte Carlo method. How can I determine whether a random point is within the room or not?

I was thinking about creating a line from the middle of the room to the point and checking if the line intersects any of the walls. However, with Monte Carlo method I am not sure if this method is not too computationally complex. Maybe there is a better and a quicker method than that. Could you please suggest me any build in functions that could be applied to my problem?

Thank you very much.

Answer 1

[Abolfazl Chaman Motlagh]

there is one easy way i can think, but that's not maybe very easy to write.

you can devide the the while interior of set into some convex subsets. for example in your attached image there are 3 obvious convex subset (main hall , extra space in front face, and extra space in back face). the convex linear subset of euclidean spaces can easily interpreted in ineqality of form:

(the propertiy you mentioned that every interior point is convex combination of 2 point in walls are true because of this. in general you can represent every interior points in convex combination of just nodes in corners.)

Hence the condition you can check for evey points is :

all(A*x<=c)

this code check if all conditions of A*x<=c are satisfied. this is the mathematical meaning of interior.

now A and c are coefficients which can be found for every surface by it's equation.

the equation of i-th surface is like :

and for every surface you should check if <= is inside or >= . in the >= case multiply the inequality by (-1) and make it <=.

the reason i said maybe it's not easy to write is beacause you should drive A and C by yourself for every problem. (or maybe that's another problem to automate this procedure too)

i think this should do the task.

[Abolfazl Chaman Motlagh]

there is easy way to find equation of plane by three points. in every convex subset put another vertex of that segment (which is not on that certatin surface ) in the equation you just found and check the sign of A*x-C . this should automate the algorithm for finding A and C.