3
$\begingroup$

Suppose I have a mesh consisting of a set $M$ of conformal elements that fill the region $R=[0,1]\times[0,1]$. Suppose that I also have a 2D shape $S\subset R$ whose boundary $\partial S$ is piecewise linear, but which is not necessarily convex nor necessarily simply connected. Without making any assumptions on the particular shape of the elements in the mesh, how can I efficiently determine the smallest set of elements whose union contains all of the shape $S$?

Though my question is posed in 2D, I'm interested in an approach that would extend to 3D as well.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Can't you, in a first step, find all of the cells that are intersected by the piecewise linear boundary $\partial S$? If your cells are simplices, then this intersection should be relatively straightforward to find by just looping over the line segments that make up $\partial S$. Once you have the cells that are intersected, you will need to find all cells that are either on the inside or outside of a set of connected intersected cells. $\endgroup$ – Wolfgang Bangerth Jan 17 '17 at 1:03
  • $\begingroup$ What makes you think that the smallest set is the best set? $\endgroup$ – Philip Roe Nov 13 '17 at 17:40
  • $\begingroup$ What is the meaning of "conformal elements"? $\endgroup$ – Futurologist Jun 12 '18 at 17:14
1
$\begingroup$

In case you do not want to take a simple convex hull (results in overestimations and not composed only of elements), here is an algorithm for, maybe, solving a specialized version of your problem:

  1. Find all the simply connected components (using e.g. union-find algorithm).
  2. For each component, find the alpha shape.

Naturally extends to 3D. Haven't proved if it's the smallest though.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Let's first also assume you have some way to validate that a point is within the shape $S$. Given you have that implemented, one could use the vertices of some given element to check if it is within the shape $S$.

The next step would be to find an element that does lie within $S$, which could be done by finding an element that contains/shares one of the vertices used to create the piecewise shape $S$. This could be efficiently done using something like a KD Tree, Spatial Hashtable, or similar data structure.

Once you have found a single element that is within the shape $S$, you can then use a Breadth/Depth First Search based on neighboring elements and their vertices to find the elements within $S$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I don't think this will work because the fraction of $S$ that may lie within a cell may be very small and, in particular, not contain any vertex or other special point. I suspect that querying individual points will not work, but that you need to start with queries that test intersection of a cell and $S$. Because the boundary of $S$ is composed of line segments, that should be feasible. $\endgroup$ – Wolfgang Bangerth Jan 17 '17 at 16:36
  • $\begingroup$ @WolfgangBangerth That is certainly an edge case that is feasible. Provided $S$ is sufficiently large, I am sure the above approach could capture majority of the cells, but there could be cells near the boundary of $S$ that fail due to the condition you describe. Perhaps one could use the intersection test you describe for the elements along the boundary of $S$ and then use a Breadth/Depth First traversal for the interior based on an neighboring elements' centroid or vertex? $\endgroup$ – spektr Jan 17 '17 at 20:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.