1
$\begingroup$

Is there a general parametrized equation for any Convex Quadrilateral? In other word, I need an equation that all the points that are on the perimeter of the Convex Quadrilateral satisfies it for some set of parameter.

For example the circle has an equation of form:

$$(X-X_0)^2 +(Y-Y_0)^2=R^2$$

In the same way, does the Convex Quadrilateral has an equation of form:

$$F(X,Y,[P_1,P_2,P_3...P_n])=0$$ I do not have an idea about the number of parameters that such equation needs.

$\endgroup$
  • 1
    $\begingroup$ If you have 4 coordinates then you can get four straight lines and any point that satisfy any one of those equation is a point on the quadrilateral. I know this isn't a equation but if you just need to check, this is fine. $\endgroup$ – A---B Jun 4 '16 at 18:51
3
$\begingroup$

All convex polytopes can be defined as the intersection of a set of half-spaces. In 2D, the half-spaces are just lines (splitting the infinite plane in two parts), so this is like starting with a sheet of paper, and using straight cuts only, cutting out the excess outside parts. (I'll limit to 2D from here on end.)

If we define the cutting line so that it first passes through point $\vec{p}_1 = (x_1, y_1)$, then through point $\vec{p}_2 = (x_2, y_2)$, with everything on the left side of the line (viewed from the first point towards the second point) being on the inside, we can use cross product to determine which side point $\vec{p} = (x, y)$ is on:

$$\left( \vec{p} - \vec{p}_1 \right) \times \left( \vec{p}_2 - \vec{p}_1 \right) = \left\lbrace\begin{array}{ll} \lt 0, & \text{inside} \\ = 0, & \text{on the perimeter} \\ \gt 0, & \text{outside}\end{array}\right.$$

If we have a polygon with $n$ points $\vec{p}_i$, $i = 1..n$, and we consider the points cyclically (by copying the first vertex at the end of the list, $\vec{p}_{n+1} = \vec{p}_1$), we need $n$ tests to check whether point $\vec{p}$ is on the perimeter of the polygon: $$d_i = \left(\vec{p} - \vec{p}_i\right)\times\left(\vec{p}_{i+1} - \vec{p}_i\right) \le 0\\ i = 1 .. n, \; \exists i: d_i = 0$$ That is, if all $d_i$ are zero or negative, and at least one of $d_i$ is zero, then point $p$ is on the perimeter of the polygon.

(In numerical computation, where we actually include a nominal thickness, the signed distance from the line is typically used instead: $$d_i = \frac{\left(\vec{p} - \vec{p}_i\right)\times\left(\vec{p}_{i+1} - \vec{p}_i\right)}{\lVert\vec{p}_{i+1} - \vec{p}_i\rVert}$$ with $-t/2 \le d_i \le t/2$ considered on the perimeter, where $t$ is the perimeter thickness, and $d_i \le t/2$ considered inside or on the perimeter.)

Here we get to the main reason why I wrote this answer:

Is it possible to combine all those $n$ inequalities into a single equation?

The answer is yes, but you don't want to, because we have better mathematical tools handling systems of equations -- especially systems of linear equations --, than we have solving complicated single equations.

As an example of how to convert such a system into a single equation, we only need an indicator function $f(x)$: $$f(x) = \left\lbrace\begin{array}{ll} 1, & x \lt 0 \\ 0, & x = 0 \\ n, & x \gt 0\end{array}\right.$$ Then, our system of inequalities testing whether point $\vec{p}$ is on the perimeter of our convex $n$-gon can be written as a single inequality, $$\sum_{i=1}^{n} f(d_i) \le n-1$$

Going back to the original equation for the perimeter of a circle, $$\left(\vec{p} - \vec{c}\right)\cdot\left(\vec{p} - \vec{c}\right) = r^2$$ you could say that circle (and spheres in higher dimensions) happen to be shapes you have very simple indicator functions for.

There are lots of shapes that do have similar "indicator functions", even parametric ones. Metaballs are an interesting example. Or consider, for example, $$\lvert x \rvert + \lvert y \rvert = h$$ which is the perimeter of a square with corners at $(0,h)$, $(h,0)$, $(0,-h)$, and $(-h,0)$ (and area $2h^2$). It's just not axis-aligned.

My point is, these "easy" shapes are the exceptions, but we do have powerful tools for solving the systems of equations (or inequalities) for the general cases, too.

$\endgroup$

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.