## Friday, January 15, 2016

### Point in convex polygon by coefficients times vertices

Supposing you have n vertices in the plane forming a convex region chosen to be indexed in some order by i, I found that any point inside that convex polygon can be expressed as the sum of coefficients [0..1] multiplying each vertex with coefficients adding to 1...

For example if the vertices were V[0], V[1], V[2], V[3], V[4], a point inside the polygon will be

.2*V[0]+.4*V[1]+.2*V[2]+.1*V[3]+.1*V[4]

Note that the coefficients add to 1 and are between inclusive 0 and 1!

I wrote this program to demonstrate. This is plotting points for any coefficients meeting these two criteria in 20 discrete steps between 0 and 1 inclusive and 5 vertices...

I've made it so c[0] makes a plotted point redder proportional to how large the coefficient is...

Below is with 50 discrete values between 0 and 1 of the variables:

I think it's clear with fine enough steps every part of the pentagon would be plotted, perhaps uniquely...

I'm still working on a proof though... I wrote the program just to see if it obviously wasn't true but it looks like it is...

#### **Source Code requires Python 3 and Pillow for Python**

from PIL import Image

def descend(n, c, i, s, d, plot, coords):
if i < n-1:
m = 1.0
while(m >= -d/2.0):
c[i] = m
if(s+m <=1-d/2.0):
descend(n, c, i+1, s+m, d, plot, coords)
m -= d
else:
c[n-1] = 1.0-s
print(c)
p = [0,0]
for j in range(0, n):
p[0] += c[j]*coords[j][0]
p[1] += c[j]*coords[j][1]
plot.putpixel((int(p[0]), int(p[1])), (255,255-int(c[0]*255),255-int(c[0]*255)))

def main():
coords = [[84,232],[104, 424],[342,508],[528,276],[330,212]]
plot = Image.new("RGB", [800,800])
c = [0,0,0,0,0]
descend(5, c, 0, 0, .05, plot, coords)
plot.save("plot.png")
main()