Given the coordinates of three points in the plane, what is the
most computationally efficient way of determining whether a given
fourth point is inside the triangle formed by the other three?
If the triangle's vertices are P0, P1, and P2, and the fourth
point is P3, we can place P0 at the origin by subtracting its
coordinates from each of the others. Then compute
a = x1 y2 - x2 y1
b = x1 y3 - x3 y1
c = x2 y3 - x3 y2
The point P3 is inside the triangle T{0,1,2} iff
ab > 0 AND ac < 0 AND a(a-b+c) > 0
Also, one of the points is inside the triangle formed by the other
three iff
abc(a-b+c) < 0
This criterion is related to the note Parabola Through Four Points,
because given any four points P0,P1,P2,P3 on the plane (with P0 at
the origin), those points all lie on a single parabola of the form
y = Gx^2 + Hx if we rotate the xy coordinate axes by an angle theta
that satisfies the equation
A tan(theta)^2 + B tan(theta) + C = 0
where
A = b(y2^2 - y2 y3) - c(y1^2 - y1 y3)
B = b(2 x2 y2 - x2 y3 - y2 x3) - c(2 x1 y1 - x1 y3 - y1 x3)
C = b(x2^2 - x2 x3) - c(x1^2 - x1 x3)
This quadratic has real roots iff B^2 - 4AC is greater than or equal
to zero, and it's clear that a real parabola can pass through four
points iff none of the points lies inside the triangle formed by the
other three. Hence, we know that one of the points IS inside the
triangle formed by the other three if and only if
B^2 - 4AC = 4abc(a-b+c) < 0
The property of no point being inside the polygonal envelope of the
other points in a set is called convexity, so the quantity abc(a-b+c)
is an indicator of the convexity of a given set of four points. It's
also worth noting that the four factors a,b,c,(a-b+c) are really twice
the signed areas of the triangles on the four subsets of 3 points.
Refer to the note Net Area, and Green's Theorem, which includes a
derivation of the fact that the "net area" enclosed by a general
n-sided polygon with vertices x[1],y[1] through x[n],y[n] (in order
around the perimeter) is given by
1 n / \
A = - SUM ( x[i+1] y[i] - x[i] y[i+1] )
2 i=1 \ /
with the understanding that x[n+1] = x[1] and y[n+1] = y[1]. This is
called the "signed area" because the result is positive or negative
depending one whether the path is clockwise or counter-clockwise. So,
twice the signed area enclosed by the path from P1 to P2 to P3 is
A[P1,P2,P3] = (x1 y2 - x2 y1) + (x2 y3 - x3 y2) + (x3 y1 - x1 y3)
Of course, if P0 is located at the xy origin, then twice the signed
areas of the triangles enclosed by the paths P0,P1,P2, and P0,P1,P3,
and P0,P2,P2 are simply
A[P0,P1,P2] = x1 y2 - x2 y1 = a
A[P0,P1,P3] = x1 y3 - x3 y1 = b
A[P0,P2,P3] = x2 y3 - x3 y2 = c
Substituting these into the preceding formula, we see that twice the
fourth triangle's signed area can be expressed as
A[P1,P2,P3] = a - b + c
It's easy to see that four points are convex iff the product of the
signed areas of the triangles on those four points (taken in any
order) is positive, because of the invariance of the product under
index permutations, and by inspection of the two possible topologies.
Hence we arrive at the previous result, that four points (with P0 at
the origin) are convex if and only if abc(a-b+c) is positive.
Dispensing with the requirement for one of the points to be at the
origin, it remains true that the product of the signed areas of the
four triangles on four given points is positive iff those four points
are convex. For convenience, let (ijk) denote twice the signed area
enclosed by the piecewise-linear path from Pi to Pj to Pk to Pi.
Then the four non-colinear points P1,P1,P2,P4 are convex if and
only if
(123)(124)(134)(234) > 0
It's important to note that while this total expression is invariant
under permutations of the indices, it is not invariant under
permutations of the indices in any individual factor. Each factor
has an invariant magitude under permutations, but the sign can be
reversed. Of the six possible permutations of the three indices
in (ijk), three of them are positive three are negative, accordingly
as the permutation is odd or even. Thus the invariance of the sign
of the convexity indicator depends on maintaining a consistent order
of the vertices in all four factors.
Now, let us define the four-index symbol (ijkm) as the product of
the four three-index symbols that can be formed from its indices,
as follows
(ijkm) = (ijk)(ijm)(ikm)(jkm)
This is the convexity indicator for the four points Pi,Pj,Pk,Pm.
Graham Herrick has pointed out that the above can be used to give
an ingenious proof of the fact that any set of FIVE non-colinear
points in the plane must contain at least one subset of four points
that are arranged in a convex pattern. To prove this, he notes
that if five points P1,..,P5 contained no convex subset of four
points, then each of the five subsets consisting of four points
must have a negative convexity indicator. Since the product of
five negative numbers is negative, this implies
(1234)(1235)(1245)(1345)(2345) < 0
However, if we express each of these four-index symbols in terms of
their three-index factors we see that each distinct set of three
indices appears in precisely two factors, so the above quantity
can be expressed as
/ \ 2
( (123)(124)(125)(134)(135)(145)(234)(235)(245)(345) )
\ /
Being a square, this is necessarily positive. Hence, not all five
of the four-point subsets can be non-convex. An odd number of them
must be convex.
Herrick notes that this is a special case of a conjecture of Erdos,
which states that 2^(n-2)+1 non-colinear points in the plane always
contain a convex n-gon. (This is known to be true for n=4 and n=5,
but it remains conjectural for higher n.) For example, with n=4 the
proposition asserts that any 5 non-colinear points in the plane
contain a subset of 4 points arranged in a convex pattern. Likewise,
with n=5 the proposition is that any 9 non-colinear points contains
a subset of 5 points arranged in a convex pattern.
The above proof that every 5-plex contains a convex 4-plex is
interesting for several reasons. Notice that it doesn't rely on
the specific form of the 4-index indicator, but simply on the
fact that it factors symmetrically, such that the product of the
indicators of every 4-plex in a given 5-plex is a square.
We're prefectly entitled to define the 5-index indicator (ijkmn)
as +1 if those 5 points are convex, and -1 if they are not, even
though we may not know how to express it algebraically. It exists
as a well-defined function, simply by virtue of the fact that every
5-plex is definitely either convex or not. Then we can form the
product of all C(9,5)=126 5-index indicators based on 9 arbitrary
(noncolinear) points, and see if this product has a special form
(such as being a square) that we can exploit. Unfortunately, for
all n greater than 4, the value of C(2^(n-2)+1,n) is even, so we
are apparently blocked from applying Herrick's scheme to any more
cases of Erdos' conjecture.
Still, this raises some interesting questions, such as whether
(ijkmn) can be expressed as a product of some function of the four-
index subsets, i.e., whether the indicator (ijkmn) can be expressed
as a symmetrical product of four-index functions
(ijkmn) = F(ijkm) F(ijkn) F(ijmn) F(ikmn) F(jkmn)
We know that F() is NOT the 4-index indicator, because these five
points are convex iff all five of the 4-point indicators are positive,
whereas the above product would give a positive indication iff an
even number of the F() factors are negative. Nevertheless, this
doesn't prove that no function F() exists. It simply means that
F() isn't the 4-point indicator.
Incidentally, notice that if we set F() to the 4-point indicator
the resulting product is not invariant even up to sign, but has 24
distinct value in general (12 up to sign). The group of permutations
S_5 splits into the cyclic and reversal actions. Any rotation of
the indices leaves the product invariant, and reversing the indices
changes the sign. Thus there are 12 independent values.
What interests me most about the above proof is its implications for
information "factoring". We've seen that, given four non-colinear
points on the plane, we could transmit to each of four isolated
people the coordinates of a unique set of three of those four
points, along with a specific ordering of those points (up to
even permutations), and those people could independently compute
the three-point indicator for their respective sets of points
(normalized to +1 or -1), such that the product of all their
numbers indicates whether or not the total set of four points
is convex. This is true in spite of the fact that none of the
four people has enough information to assess the convexity of
the four-point set. Moreover, we can arrange for the returned
values to be either positive or negative (by permuting the order)
with equal frequency on a sequence of trials. In other words,
we're free to reverse the signs of the factors (in unison) without
affecting the overall result.
This is intriguingly similar to situations involving quantum
mechanical phenomena, such as EPR-type experiments, in which the
information available at separate locations is unable to convey
any knowledge of the combined result, and yet the individual
results seem to exhibit, upon combination, some correlative aspects.
In other words, each of two observers may see +1 and -1 (represent-
ing, say, spin UP or spin DOWN) an equal percentage of the time,
apparently randomly distributed, but when they get together and
compare corresponding observations they find correlations, such
that their product is not randomly distributed, and moreover the
factors are correlated in a non-linear way which defies ordinary
causal explanation based on the idea that each indicator has a
definite value prior to observation. In the case of convexity
indicators, this can be attributed to the fact that the three
given points specified to an individual observer can yield +1
or -1, depending on the presumed ordering of those points. This
amount to determining a "basis" for evaluating those points, and
when the observers come together they must reconcile their bases
and establish a consistent ordering, when then ensures that the
product of the indicators (interpreted on this common basis) is
the four-point indicator.
Return to MathPages Main Menu
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4