# IsConvex() of "vtkPolyhedron" may give wrong result?

**URL:** <https://discourse.vtk.org/t/isconvex-of-vtkpolyhedron-may-give-wrong-result/13635>\
**Category:** Development\
**Tags:** code\
**Created:** [March 26, 2024, 8:50am UTC](https://discourse.vtk.org/t/isconvex-of-vtkpolyhedron-may-give-wrong-result/13635 "2024-03-26T08:50:17Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![guaguameikong](https://discourse.vtk.org/user_avatar/discourse.vtk.org/guaguameikong/32/8658_2.png) [@guaguameikong](https://discourse.vtk.org/u/guaguameikong)\
**Post date:** [March 26, 2024, 8:50am UTC](https://discourse.vtk.org/t/isconvex-of-vtkpolyhedron-may-give-wrong-result/13635/1 "2024-03-26T08:50:18Z")

</div>

My vtk version is 9.1, C++.  
I use vtkUnstructrudeGrid to store my data, and pick one vtkCell from the ugrid, translate to vtkPolyhedron, check if IsConvex().

put an example below, the right result of IsConvex() is true but I got false:

```auto
# vtk DataFile Version 5.1
vtk output
ASCII
DATASET UNSTRUCTURED_GRID
POINTS 6 float
-41.6027 0 10.2556 -37.5 0 10.6045 -41.8135 0 13.8533 
-41.6027 4 10.2556 -37.5 4 10.6045 -41.8135 4 13.8533 

CELLS 2 24
OFFSETS vtktypeint64
0 24 
CONNECTIVITY vtktypeint64
5 3 0 1 2 4 0 3 4 
1 4 1 4 5 2 4 0 2 
5 3 3 3 5 4 
CELL_TYPES 1
42

```

---

<div class="post-metadata">

**Author:** ![guaguameikong](https://discourse.vtk.org/user_avatar/discourse.vtk.org/guaguameikong/32/8658_2.png) [@guaguameikong](https://discourse.vtk.org/u/guaguameikong)\
**Post date:** [March 26, 2024, 9:23am UTC](https://discourse.vtk.org/t/isconvex-of-vtkpolyhedron-may-give-wrong-result/13635/2 "2024-03-26T09:23:12Z")

</div>

Guess it’s a precision bug

---

<div class="post-metadata">

**Author:** ![guaguameikong](https://discourse.vtk.org/user_avatar/discourse.vtk.org/guaguameikong/32/8658_2.png) [@guaguameikong](https://discourse.vtk.org/u/guaguameikong)\
**Post date:** [March 28, 2024, 9:02am UTC](https://discourse.vtk.org/t/isconvex-of-vtkpolyhedron-may-give-wrong-result/13635/3 "2024-03-28T09:02:26Z")

</div>

**Indeed, it was a bug in the algorithm, and I have fixed it.**  
The IsConvex() function uses the algorithm from Devillers et al. I learned this algorithm from [Determining Convexity of Polyhedra](https://liam.flookes.com/cs/geo/algorithm.html) and tried to fix the bug. When determining “the upper face must not be vertical,” one should not use the face center (based on specific points), but should instead rely on the plane itself. Therefore, I modified the code as follows:

```auto
    // 3. We get the z component of the normal of the highest face
    // If this is null, the face is in the vertical plane
    for (int i=0;i<3;++i){
        c0[i] = c0[i]-c[i];
        c1[i] = c1[i]-c[i];
    }
    tmp0 = c0[2]-dot(c0,n)*n[2] > c1[2]-dot(c1,n)*n[2] ? n0[2] : n1[2];
    if (std::abs(tmp0) < eps)
    {
      continue;
    }

```

---

<div class="post-metadata">

**Author:** ![guaguameikong](https://discourse.vtk.org/user_avatar/discourse.vtk.org/guaguameikong/32/8658_2.png) [@guaguameikong](https://discourse.vtk.org/u/guaguameikong)\
**Post date:** [March 28, 2024, 12:38pm UTC](https://discourse.vtk.org/t/isconvex-of-vtkpolyhedron-may-give-wrong-result/13635/4 "2024-03-28T12:38:48Z")

</div>

The bug can only cause errors **if the polyhedron has a vertical face** , so it has been well hidden so far

---

<div class="post-metadata">

**Author:** ![MicK7](https://discourse.vtk.org/user_avatar/discourse.vtk.org/mick7/32/3362_2.png) [@MicK7](https://discourse.vtk.org/u/MicK7)\
**Post date:** [June 27, 2024, 8:06am UTC](https://discourse.vtk.org/t/isconvex-of-vtkpolyhedron-may-give-wrong-result/13635/5 "2024-06-27T08:06:14Z")

</div>

> [@guaguameikong](#):
>
> ```auto
> // 3. We get the z component of the normal of the highest face
> // If this is null, the face is in the vertical plane
> for (int i=0;i<3;++i){
> c0[i] = c0[i]-c[i];
> c1[i] = c1[i]-c[i];
> }
> tmp0 = c0[2]-dot(c0,n)*n[2] > c1[2]-dot(c1,n)*n[2] ? n0[2] : n1[2];
> if (std::abs(tmp0) < eps)
> {
> continue;
> }
> 
> ```

Can your proposed patch be sum up to :

```auto
tmp0 = c0p[2]- vtkMath::Dot(c0p,n)*n[2] > c1p[2]-vtkMath::Dot(c1p,n)*n[2] ? n0[2] : n1[2];

```

Have you submitted a merge request ?

---

<div class="post-metadata">

**Author:** ![guaguameikong](https://discourse.vtk.org/user_avatar/discourse.vtk.org/guaguameikong/32/8658_2.png) [@guaguameikong](https://discourse.vtk.org/u/guaguameikong)\
**Post date:** [July 19, 2024, 2:00pm UTC](https://discourse.vtk.org/t/isconvex-of-vtkpolyhedron-may-give-wrong-result/13635/6 "2024-07-19T14:00:49Z")

</div>

no