analytics

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()



No comments:

Post a Comment