qhull input error: input is less than 3-dimensional since it has the same x coordinate

[KlatbahII]

Hello i've created an issue last summer Using LiDAR Classification of Vegetation instead of NDVI and "Gridded building roof heights" ?.
I managed to run your process with my data and i wanted to implement it on a large area.
The LiDAR i'm using have already a great classification of Vegetation so there is no need to use the gridded points of the CityGML building.

You told me that the workflow is sequential, so i did the following:

• filter my point cloud with vegetation and ground
• Create a canopy height model(CHM)
• Start at the part of the individual tree segmentation

On some area, the process with my data filtered on vegetation works perfectly.

I even manage to create CityGML with your FME script, and display them on a web page

But in another area, i have an error about Convex Hull

This is the line where i get the error

# calculate 3D convex hulls around segmented tree points
# retrieve volume and surface area of the hulls
crown_volumes_df <- compute_crown_volumes(lidar_surface_points, "treeID_temp")

Received error code 1 from qhull. Qhull error:
QH6013 qhull input error: input is less than 3-dimensional since it has the same x coordinate

While executing:  | qhull FA  Qt
Options selected for Qhull 2015.2.r 2016/01/18:
  run-id 2112793898  FArea-total  Qtriangulate  _pre-merge  _zero-centrum
  _max-width 0.25  Error-roundoff 3.1e-09  _one-merge 2.2e-08
  _near-inside 1.1e-07  Visible-distance 6.2e-09  U-coplanar-distance 6.2e-09
  Width-outside 1.2e-08  _wide-facet 3.7e-08

When i have this error, the whole process stops.
I have tried different things without success:

• Use raster crowns_mcws_grid to find area on my point cloud where there are not enough points
• Use vector mcws_segments_poly to get the number of points of my point cloud that are inside each MultiPolygon

At some point, i can see when display the LiDAR and the vector layer mcws_segments_poly that there are only one or a few point inside crowns.

Even after deleting this crowns and points, there is still the same issue

I wanted to know, if you had already met this error and where the problem is coming from.

If needed, i can share with you the code and the data i used

Thanks in advance

[markusmnzngr]

Hi Klatbahll,

Thanks for bringing this to my attention. Indeed, I was able to replicate similar errors. This can occur due to either a due to insufficient points within a tree crown (minimum 4) or, sometimes, even with a sufficient number of points, duplicate points may exist with identical XYZ coordinates.

I've made adjustments to the code and incorporated filters to remove duplicates and consider crown dimensions. Could you please check if your processing works with the updated code?

Besides, your customization of the workflow is reasonable, and the web-based visualization of the 3D tree models looks impressive. It's great to see that.

[KlatbahII]

Thank you very much, i will try the new code this week and i'll let you know what happens.

[KlatbahII]

Hello again,

I managed to test the new code that fix the issues i had.
Like i told you before we are running your code without the parts that uses the building gridded heights. It's because our LiDAR has a good Vegetation Classification.

We have two differents datasets of LiDAR, created by two different companies.
One is working perfectly, and the second one we got some issues.

The issues happend at the same line than before with compute_crown_volumes and it's always related to convexHull.

# calculate 3D convex hulls around segmented tree points
# retrieve volume and surface area of the hulls
crown_volumes_df <- compute_crown_volumes(lidar_surface_points, "treeID_temp")

First issue we encountered is this one :

Error in convhulln(p, "FA") :
Received error code 2 from qhull. Qhull error:
QH6114 qhull precision error: initial simplex is not convex. Distance=0

While executing: | qhull FA Qt
Options selected for Qhull 2015.2.r 2016/01/18:
run-id 1712460830 FArea-total Qtriangulate _pre-merge _zero-centrum
_max-width 0.32 Error-roundoff 3.1e-09 _one-merge 2.2e-08
_near-inside 1.1e-07 Visible-distance 6.2e-09 U-coplanar-distance 6.2e-09
Width-outside 1.2e-08 _wide-facet 3.7e-08

precision problems (corrected unless 'Q0' or an error)
1 flipped facets

The input to qhull appears to be less than 3 dimensional, or a
computation has overflowed.

Qhull could not construct a clearly convex simplex from points:
- p3(v3): 1.6e+06 2.3e+06 1.6
- p2(v2): 1.6e+06 2.3e+06 1.5
- p0(v1): 1.6e+06 2.3e+06 1.8
- p1(v0): 1.6e+06 2.3e+06 1.6

The center point is coplanar with a facet, or a vertex is coplanar
with a neighboring facet. The maximum round off error for
computing distances is 3.1e-09. The cen

What we tried :

Export the layer crowns_mcws_poly and use it to remove crowns that we think are the reasons of the convex hull issues.
Here is the actions we did:

• Remove crowns from the layer crowns_mcws_poly when it contains 4 points or less
• Remove crowns from the layer crowns_mcws_poly when the area is < 0.5m²
• Remove "duplicates" points in lidar_surface_points of 1 centimeter distance

After this, we still got this issue:

Error in convhulln(p, "FA") :
Received error code 2 from qhull. Qhull error:
qhull precision warning:
The initial hull is narrow (cosine of min. angle is 0.9999999999999999).
Is the input lower dimensional (e.g., on a plane in 3-d)? Qhull may
produce a wide facet. Options 'QbB' (scale to unit box) or 'Qbb' (scale
last coordinate) may remove this warning. Use 'Pp' to skip this warning.
See 'Limitations' in qh-impre.htm.
QH6114 qhull precision error: initial simplex is not convex. Distance=-1.2e-10

While executing: | qhull FA Qt
Options selected for Qhull 2015.2.r 2016/01/18:
run-id 443649979 FArea-total Qtriangulate _pre-merge _zero-centrum
_max-width 1.6 Error-roundoff 3.1e-09 _one-merge 2.2e-08
_near-inside 1.1e-07 Visible-distance 6.2e-09 U-coplanar-distance 6.2e-09
Width-outside 1.2e-08 _wide-facet 3.7e-08 _narrow-hull 1.1e-16

precision problems (corrected unless 'Q0' or an error)
1 flipped facets

The input to qhull appears to be less than 3 dimensional, or a
computation

We are not used with the convex hull functions.
Do you have any idea about process or treatment on the lidar to avoid this issues ?

If you need it, i can send you the code and the data i used.

Thanks in advance

[markusmnzngr]

Hey KlatbahII,

the adjustments you tried seem like a good approach. I also implemented similar ones in the last update: # subset crowns with less than 4 points or are not shaped in all 3 dimensions to avoid mistakes in metric calculations and points that don't belong to a tree crown lidar_surface_points <- lidR::filter_poi(lidar_surface_points, !is.na(treeID_temp) & count > 4 & delta_x > 0.1 & delta_y > 0.1 & delta_z > 0.1)

How do you filter duplicate points? Removal of duplicate points with the function from the lidR-package is implemented in the part where urban trees are classified in the point cloud. If you skipped that part because your LiDAR data is already classified, this could be a reason.

# remove duplicate points based on their XYZ-coordinates lidar_surface_points <- lidR::filter_duplicates(lidar_surface_points)

If that doesn't solve the problem, please provide me with your data and code so I can reproduce the error.

[KlatbahII]

Hey, thanks for your answer, Here is the weTransfer link with the code and the data. https://we.tl/t-F64HCAEtXS Here is the content of the README.MD

Hello Markus,

Here is the code and data we used and where we got the error.

• 1576000_2267000_crown_volume.las : The .las that is saved during your process
• 1576000_2267000_crowns_mcws_poly_parameterized.geojson : The variable crowns_mcws_poly, it's the layer from wich we removed entity during our differents tests
• 1576000_2267000_NDVI_50cm.tif : The NDVI of the area, with a resolution of 50cm.
• 1576000_2267000_sol_vegetation.laz : THe input LiDAR filtered on ground and vegetation

The RMarkdown rieux_No_CSV.Rmd is our first attempt that got an error message at the line crown_volumes_df <- compute_crown_volumes(lidar_surface_points, "treeID_temp")

I have created the R file : correction_entites_rieux_TM.R. It was an attempt to edit the layer 1576000_2267000_crowns_mcws_poly_parameterized.geojson in order to remove the crowns that we thought caused the issues. And "start over" the process after theses modifications.

One of the error was this : cosine of min. angle is 0.9999999999999999. I thought it could be that there is points really close from each other. For example i removed points within a distance of 1 centimeter. I dit it with FME. We tried a lot of things(removed polygons of 1576000_2267000_crowns_mcws_poly_parameterized.geojson with an area inferior to 0.5m², filter crowns in the geojson where there is less than 5 points in 1576000_2267000_crown_volume.las). Apply filter to remove entity of the layer 1576000_2267000_crowns_mcws_poly_parameterized.geojson

I hope you'll find the reason, thanks a lot.

[markusmnzngr]

I could reproduce the error and found points causing the problem. It is a "crown" with 5 points, that looks like beeing part of a hedge in front of a building. Problem is that the points are coplanar. That's why no convex hull can be calculated.

I attached the mcws segment and the points. You can download them and remove the points in your workflow like this:

# remove coplanar points - identified "crown"segment
# Import GeoJSON data as an sf object
coplanar_mcws_path  <- here::here("results/parameterized_tree_crowns/coplanar_mcws.geojson")
coplanar_mcws_sf_poly <- sf::st_read(coplanar_mcws_path)
# merge polygon to pointcloud
lidar_surface_points <- lidR::merge_spatial(lidar_surface_points, coplanar_mcws_sf_poly, attribute = "delete")
# filter from point cloud
lidar_surface_points <- lidR::filter_poi(lidar_surface_points, delete==FALSE)

Like you already mentioned, the crowns segmented are slightly variable. So it could be, that a similiar error occurs in another area when segmentation is leading to that specific circumstance. Therefore I recommend testing the lidR::segment_shapes() function to detect coplanar points. It is already implemented in the part of the workflow filtering for roofs as planar shapes. The same logic could apply for hedges.

{r coplanar points classification}
# classify coplanar points as potential roof points
# lidar_surface_points <- lidR::segment_shapes(lidar_surface_points, lidR::shp_plane(th1 = th1_cop, th2 = th2_cop,k = k_cop), "Coplanar")