2
$\begingroup$

I have data points (their number between 100 and 1000) in 3D, which possibly come from the area of a triangle with some additional noise (so they would not perfectly be on and inside the triangle but very clearly have a relationship). I would like to quantify how well the points would be fitted by the triangle - ideally a single number similar to how correlation quantifies the relationship between two variables. I don't really need any info of the triangle itself. The pairwise correlations of the variables are not fairly low since the triangle gets projected as another triangle to all three dimensions.
Is there any way to quantify this relationship to distinguish between points that do or do not come from a triangle? By 'form a triangle' I mean that there is a triangle for which 1) the summed squared distance of points from the triangle is minimum and 2) the distance of the edges of the triangle from the points is also minimised. I will have to check over millions of variable triplets, so the simpler the better, though I have access to HPC.

I thought of first quantifying how co-planar the points are, and then applying some additional check-up on the points projected to the identified plane. Or doing a multivariate linear regression with all three variables as targets (in turns) to see how much information I can retain by their combinations. I do not know though what would be the most efficient and bulletproof way to go about it.

The points in the triangle below are here: https://gist.github.com/elakatos/1e7a5a28e8602a53fd7ea5afd4379d9e

Update: the data shown in the figure below was generated by me (with preset relationships to ensure the triangle; but I assume my data would look similar in some cases and I want to identify these cases by some decision making process. Points from a triangle in 3D

$\endgroup$
  • 2
    $\begingroup$ For clarification: Does it suffice to measure whther the points are in a plane or do we need to check the shape too? I mean even if they form e.g. a hexagon they are technically inside a large enough triangle. $\endgroup$ – M. Winter Oct 20 '17 at 11:36
  • $\begingroup$ Yes, whether they form a triangle or not would be quite important. Also, the vertices of the triangle are most probably not amongst the points. $\endgroup$ – Eszter Lakatos Oct 20 '17 at 11:39
  • $\begingroup$ Hm. We probably need more information here. Are the points distributed in some way inside the desired triangle? As I said, any planar cloud of points can be said to be inside a large enough traingle. What does it mean to "form a triangle"? Is the shape of the triangle recognizable from the point cloud? Do you already know the triangle or do you want to find it? So you are looking for the smallest or best fitting triangle to your data? $\endgroup$ – M. Winter Oct 20 '17 at 11:42
  • $\begingroup$ I cannot assume anything regarding the distribution, though I suspect they would be roughly uniform inside the triangle. By form a triangle I mean that there is a triangle for that 1) the summed squared distance of points from the triangle is minimum and 2) the distance of the edges of the triangle from the points is also minimised. I don't know the triangle in general, and I don't necessarily want to find it, just whether there is one. I guess it should be recognisable if plotted in 3D, but I need a less subjective method (also that could be applied to millions of datasets). $\endgroup$ – Eszter Lakatos Oct 20 '17 at 12:19
  • $\begingroup$ Just as an exploratory hint with this particular data with variables $C,D,E$, consider rotating them so you have say $X=\sqrt{\frac12}(C-D)$, $Y=\sqrt{\frac16}(C+D+2E)$ and $Z=\sqrt{\frac13}(C+D-E)$. You will find $Z$ is in the range $[-11.2,11.8]$ while $C,D,E,X,Y$ have much wider ranges. Now plot $Z$ against $X$ to see how little $Z$ varies, and similarly plot $Z$ against $Y$. To see how triangle-like the data is or is not, plot $Y$ against $X$. $\endgroup$ – Henry Oct 20 '17 at 12:24
0
$\begingroup$

I haven't tested any of this but try this:

  • Fit a plane to the points using least squares

  • Project the points onto the coordinate plane corresponding to the smallest coordinate in absolute value in the normalized normal vector to the fitted plane

  • Compute the convex hull of the projected points

The original points fit well into a triangle iff the convex hull has three large sides and the others are small relative to them.

$\endgroup$
  • $\begingroup$ Thanks I was thinking about something along these lines. I'm afraid computational cost might become an issue, but I could break it down to two steps and only proceed with projection/convex hull if a dataset passes some threshold for coplanarity. $\endgroup$ – Eszter Lakatos Oct 20 '17 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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