How to check if given 3d point is outside convex hull

2
votes

I'm working on a science project. I have a list of xyz-coordinates of voronoi diagram vertices, and a list of points that create my protein's convex-hull (from triangulation). Now some of the vertices lie quite far from the hull and I'd like to filter them out. How can I do it in c++ ? For now it doesn't have to be super optimised, I'm only focused on removing those points.

visualization

I was also thinking to check if a line from voronoi vertex(red crosses) to center of protein(pink sphere) is intersecting with hull face at any point, but I'm not sure how to achive that.

I've read that you can check if a point is inside a polygon by counting the times an infinite line from the point is crossing the hull, but that was for two dimensions. Can similar approach be implemented to suit my needs ?

https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/

1
convex-hull
Wait, do you just have a Voronoi diagram, or a convex hull? And is this really a C++ program, or are you asking for an algorithm? – einpoklum
I have my protein atoms. From those i'm calculating voronoi diagram. I'm also doing quasi triangulation of the protein and I can check which atoms create my hull. I'm making a console application in c++ that will operate on voronoi vertices but I want to reduce their numbers as much as I can before going to next steps. Voronoi vertices that happen to be outside of hull are no use for me. Hope I answered your questions. – WiktorSzy
No, you haven't. But let me rephrase: What is the exact representation of data that you have computed? Describe the data structure you want us to consider. – einpoklum
Objects that store floats (xyz) with coordinates. I want to check if voronoi vertex lies outside of hull (which is also defined as points). Sorry if it's again not what you wanted, I'm still learning new things. – WiktorSzy
So, now I understand which vertices you will want to check, but you still haven't said what data structure is used for the hull. I'm not asking about the structure you use for a point, but for the hull. – einpoklum

1 Answers

0
votes

Let's start with the two-dimensional case. You can find the solution to that on CS.SX:

Determine whether a point lies in a convex hull of points in O(logn)

The idea is that each two consecutive points on the convex hull define a triangular slice of the plane (to some internal point of the hull); you can find the slice in which your point is located, and check whether it's closer to the internal point than the line segment bounding the slide.

For the three-dimensional case, I'm guessing you should be able to do something similar, but the search for the 3 points forming the relevant triangle might be a little tricky. In particular, it would also depend on how the convex hull is represented - as in the 2-d case the convex hull is just a sequence of consecutive points on a cycle.

I know this doesn't quite solve your problem but it's the best I've got given what you've written...