title: Constructing convex hull object with known triangular faces
body: <p>TLDR: I need to construct a python object for fast interior point testing, similar to a SciPy <code>ConvexHull</code> or <code>DelaunayTriangulation</code>. The catch is that I know ahead of time the order in which the triangulation of the points <em>must</em> be constructed: (6 points, 8 triangular faces, with a specific ordering of each face). In effect, I already know what the convex hull should be, but I need it in a form that I can use with existing (and optimised!) libraries (eg Scipy spatial). How can I do this?</p>
  
  <p><strong>Context:</strong> 
  I need to construct a triangular prism (imagine a Toblerone bar - 2 end faces, 6 side faces, all triangular) in order to do some interior point testing. As I will have many such prisms lying adjacent to each other (adjacent on their side faces, imagine many Toblerone bars stood on their ends and next to each other), I need to be careful to ensure that no region in space is contained by two adjacent prisms. The cross section of the prism will not generally be uniform, hence the possibility of overlap between adjacent prisms, as illustrated by this diagram of the approximately planar face between two adjacent prisms:</p>
  
  <pre><code> ____
  |\  /|
  | \/ |
  | /\ | 
  |/__\|
  </code></pre>
  
  <p>Note the two different diagonals constructed along the face - this is the problem. One prism may split the face into two triangles using the \ diagonal, and the neighbouring prism may instead use the /. In order to ensure no overlap between adjacent prisms, I need to explicitly control the order in which the triangles are formed so that they always use the same diagonal. This I can do: for each prism that I need to construct, I know ahead of time in what order the triangular faces should be constructed. Here's an illustration of two adjacent prisms, with the correct shared diagonal between them: <a href="https://i.stack.imgur.com/fikaS.png" rel="nofollow noreferrer">neighbouring prisms, shared diagonal</a></p>
  
  <p>My issue is with performing fast interior point testing with these prisms. Previously, I was using the approach linked in this <a href="https://stackoverflow.com/questions/16750618/whats-an-efficient-way-to-find-if-a-point-lies-in-the-convex-hull-of-a-point-cl/16898636#16898636">answer</a>: <code>Delaunay(prism_points).find_simplex(test_points) &gt;= 0</code>. It's quick because it is using highly optimised library code, but I have no control over the construction of the triangulation, so there could be overlap. </p>
  
  <p>If I construct the hulls as explicit <code>np.array</code> objects (vertices, faces) then I can use my own code to do the tests (there are numerous possible approaches, I'm projecting rays and testing for intersection with each triangular face). The problem is that this is around ~100x slower than the <code>find_simplex()</code> approach mentioned earlier. Whilst I'm sure I could get the code a bit quicker, it is worth pointing out this code is already fairly optimised from another use case with Cython - I am not sure if I can find all the extra speed I need here. As for the inevitable "do you really need the speed question", please take my word for it. This is turning a 5 minute job into many hours. </p>
  
  <p>What I need is to construct an object I can use with external optimised libraries, whilst retaining control of the triangular faces. Adding extra Cython to my code is of course an option, but which such highly optimised code already out there, using that would be vastly preferable. </p>
  
  <p>Thanks to anyone that can help. </p>