2
$\begingroup$

Given points on a 2D plane, what kind of metrics can be used to define if they closely fit either:

  • triangle
  • square or rectangle
  • circle
  • oval (circular but not oval)

enter image description here

(Image credit: StyleCraze.com "How to Determine the Shape of Your Face".)

Note thanks to John Gowers on Meta for trying to help clarify parts of my old question, which was closed.

$\endgroup$

closed as off-topic by Namaste, Saad, Xander Henderson, JonMark Perry, qwr Jun 12 '18 at 0:45

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Namaste, Saad, Xander Henderson, JonMark Perry, qwr
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Try looking up "shape theory." $\endgroup$ – Alexander Gruber Apr 12 '18 at 3:14
  • $\begingroup$ There is earth mover's distance, which can apply to equal-area shapes and would very roughly capture our intuitive notion of distance between shapes. $\endgroup$ – Solomonoff's Secret Apr 13 '18 at 1:18
  • 1
    $\begingroup$ A standard measure of similarity between shapes is Hausdorff distance. $\endgroup$ – Rahul Apr 13 '18 at 5:46
  • 1
    $\begingroup$ How did my ealier comments /answers disappear from here? $\endgroup$ – Narasimham Apr 13 '18 at 20:26
  • 1
    $\begingroup$ @Narasimham this is not the question that you believe it is. This is the question you have in mind: math.stackexchange.com/questions/2708226/… $\endgroup$ – quid Apr 14 '18 at 14:41
2
+50
$\begingroup$

The four shapes given are all examples of (boundaries of) 2-dimensional convex bodies, so any metric on arbitrary convex bodies will do. Some examples include the following, where $C,D$ are $d$-dimensional convex sets in Euclidean space:

  1. Hausdorff metric: $d(C,D)= \max\left\{\sup\limits_{x \in X}\inf\limits_{y \in Y}~d(x,y),~\sup\limits_{y \in Y}\inf\limits_{x \in X}d(x,y)\right\}$ where $d(x,y)$ is the Euclidean distance function.
  2. Symmetric difference metric: $\Delta_v(C,D)= v (C \cup D) - v (C \cap D)$, where $v$ is Euclidean volume in $\mathbb{E}^d$. See page 1 of this paper and this section of the symmetric difference wiki page.
  3. Symmetric surface area deviation: $\Delta_s(C,D)= s(C \cup D) - s(C \cap D)$, where $s$ is the surface area. See page 1 of this paper.

Note: The symmetric surface area deviation does not satisfy the triangle inequality, so is not technically a metric, but rather a deviation measure.

Note: One can replace the continuous volume in (2) with discrete approximations and still have a metric.

$\endgroup$
  • 1
    $\begingroup$ A related and frequently used notion is the Jaccard distance. This is the symmetric difference metric normalised by the volume of the union. Equivalently, it is 1 minus the volume of the intersection of the two sets divided by the volume of the union. $\endgroup$ – Bence Mélykúti Apr 19 '18 at 12:52
  • $\begingroup$ Can you provide a practical example? :D $\endgroup$ – ina May 1 '18 at 7:50
  • $\begingroup$ Let $S$ be the unit square with vertices $[0,0], [1,0], [0,1], [1,1]$, $T_1$ be the triangle with vertices $[0,0], [1,0], [0,1]$, and $T_2$ be the triangle with vertices $[1,1], [1,0], [0,1]$. Then the area (2-d volume) of the shapes are $A(S)=1, A(T_1)=A(T_2)=1/2$. Then the symmetric difference metric (SDM) between the square and either triangle is $1/2$ since each triangle is completely contained in the square. On the other hand the SDM between the two triangles is $1$ since the union of the two is the square but the intersection is a line segment (and hence has zero area). $\endgroup$ – Aaron Dall May 1 '18 at 8:45
  • $\begingroup$ In the example, the square is closer (in the metric sense) to the the two triangles than the two triangles are to each other. When using the metrics in the answer one typically assumes that the convex bodies all have the same barycenter. Translating the square and two triangles so that they all have the same barycenter gives $\Delta(S, T_1)=\Delta(S, T_2)=1/2$ and $\Delta(T_1, T_2)=1/3$. This shows that after a reasonable normalization (i.e., after translating) the two triangles are closer w.r.t. the metric that either triangle is to the square. $\endgroup$ – Aaron Dall May 1 '18 at 10:07
1
$\begingroup$

All of these shapes can be parameterized by a small set of parameters (assuming that you mean "ellipse" when you say "oval"). For example, a square can be parameterized by a side length and an angle of rotation: 2 parameters. You can create four different optimization algorithms, one for each shape. Each algorithm fits a shape to the set of points. For these algorithms, you will need to choose an optimization metric. An example might be the sum of distances between points and nearest location of shape. The residual (the best value of the optimization metric) will tell you how well each shape fits the set of points. The shape with the lowest metric fits the set of points best.

$\endgroup$

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