# Determine point inside/outside enclosed surface
**URL:** https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539
**Category:** Support
**Created:** [October 6, 2022, 7:06pm UTC](https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539 "2022-10-06T19:06:39Z")
**Posts on this page:** 10
**Page:** 1
### Author:  [@drpeterfranz](https://discourse.vtk.org/u/drpeterfranz)
#### Post date: [October 6, 2022, 7:06pm UTC](https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539/1 "2022-10-06T19:06:39Z")
Hi there,
I have a problem here we my application receives a triangulated, closed surface which encloses a volume. The resolution of this surface is high, i.e. there are \> 100,000 triangles in it, and it can be concave. Here’s an example:
I now also have an unstructured grid which contains a similar amount of 3D cells. For each of these cells I would like to know if its centre is located inside or outside of the enclosed volume given by the triangulated surface.
Any ideas on how to do this **really fast**?
---
### Author:  [@mwestphal](https://discourse.vtk.org/u/mwestphal)
#### Post date: [October 7, 2022, 12:48am UTC](https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539/2 "2022-10-07T00:48:49Z")
Hi @drpeterfranz
It may be simpler and faster to use vtkStaticCellLocator on the volume instead of using the surface.
---
### Author:  [@drpeterfranz](https://discourse.vtk.org/u/drpeterfranz)
#### Post date: [October 7, 2022, 12:54am UTC](https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539/3 "2022-10-07T00:54:22Z")
Can you elaborate? Set `vtkStaticCellLocator->SetDataSet()` to the poly data containing the surface encompassing the volume? And then what?
---
### Author:  [@mwestphal](https://discourse.vtk.org/u/mwestphal)
#### Post date: [October 7, 2022, 12:57am UTC](https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539/4 "2022-10-07T00:57:10Z")
Nope, you would need the volume you are refering to in your initial post:
> a triangulated, closed surface which encloses a **volume**.
If you dont have it, then my advice may not be as useful as you would need to reconstruct it, and Delaunay3D do not work with concave surface, so not an option.
---
### Author:  [@drpeterfranz](https://discourse.vtk.org/u/drpeterfranz)
#### Post date: [October 7, 2022, 12:59am UTC](https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539/5 "2022-10-07T00:59:27Z")
Ah, sorry. No, the triangulated surface encloses a real-world volume, i.e. it describes the boundaries of a real world object. What I meant with ‘encloses’ it is that the surface is closed, i.e. it doesn’t have any holes in it. Hope I use the correct language here.
---
### Author:  [@mwestphal](https://discourse.vtk.org/u/mwestphal)
#### Post date: [October 7, 2022, 1:03am UTC](https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539/6 "2022-10-07T01:03:18Z")
Then you can still use a locator with your surface, assuming all your triangle are correctly oriented.
use `vtkStaticCellLocator::IntersectWithLine` and check if the sign of `t` to know if you are inside/outside.
---
### Author:  [@drpeterfranz](https://discourse.vtk.org/u/drpeterfranz)
#### Post date: [October 7, 2022, 1:10am UTC](https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539/7 "2022-10-07T01:10:29Z")
That’s similar to something I have tried before. Will `vtkStaticCellLocator` test every cell for intersection, or will it use its ‘locator’ functionality first to only consider a tiny subset of the cells? Else it would take too long again.
---
### Author:  [@mwestphal](https://discourse.vtk.org/u/mwestphal)
#### Post date: [October 7, 2022, 1:27am UTC](https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539/8 "2022-10-07T01:27:15Z")
The locator internally uses a binary tree so finding the cell is `O(log(n))`.
It is fairly fast and is made for this specific usage.
You can however further optimize if you know that you may hit multiple times the same cells by caching the last N cells or even try to find in the neighbours before using the locator if you know the there is some spatial proximity when you iterate over your volume cell centers.
---
### Author:  [@drpeterfranz](https://discourse.vtk.org/u/drpeterfranz)
#### Post date: [October 7, 2022, 1:39am UTC](https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539/9 "2022-10-07T01:39:17Z")
Perfect, sounds what I have been looking for!
---
### Author:  [@drpeterfranz](https://discourse.vtk.org/u/drpeterfranz)
#### Post date: [October 7, 2022, 2:13am UTC](https://discourse.vtk.org/t/determine-point-inside-outside-enclosed-surface/9539/10 "2022-10-07T02:13:03Z")
Works a treat, razor fast, less than 1 second execution time 😀
Can now use the shapes to assign materials to my model:
