The centroid of all the points is C

The centroid of all the points except point A is C(A)

V is the normalized vector from A to C

V2 is the normalized vector C to C(A)

Point A is colored red if:

VxV2 < 0

And blue if:

VxV2 > 0

where x is the cross product, V(x)*V2(y)-V2(x)*V(y)

What you end up with is a division of the points into a red group and a blue group such that the line dividing the two groups through the centroid crosses the line between the centroid of the red group and the centroid of the blue group through the centroid of all the points (not necessarily perpendicularly)

In the above the blue dot's center is to the left of the line going through it...

**Python Source Code**

from PIL import Image, ImageDraw

import random

def distance(a, b):

return ((a[0]-b[0])**2.0 + (a[1]+b[1])**2.0)**.5

def main():

points = []

plot = Image.new("RGB", (800,800))

plotdraw = ImageDraw.Draw(plot)

centroid = [0,0]

numpoints = 20

for i in range(0, numpoints):

x = random.randint(100,700)

y = random.randint(100,700)

centroid[0] += x

centroid[1] += y

points.append((x,y))

centroid[0] = centroid[0] / numpoints

centroid[1] = centroid[1] / numpoints

x = centroid[0]

y = centroid[1]

plotdraw.ellipse([(x-10,y-10), (x+10, y+10)], (255,255,255))

centerred = [0,0]

nred = 0

centerblue = [0,0]

nblue = 0

for i in range(0, numpoints):

x = points[i][0]

y = points[i][1]

cv = ((centroid[0]-x)/distance(centroid, (x,y)), (centroid[1]-y)/distance(centroid, (x,y)))

c2x = (centroid[0]*numpoints - x)/(numpoints-1)-cv[0]

c2y = (centroid[1]*numpoints - y)/(numpoints-1)-cv[1]

c2 = [c2x, c2y]

c2[0] /= distance(c2, cv)

c2[1] /= distance(c2, cv)

d = cv[0]*c2[1]-cv[1]*c2[0]

if d < 0:

centerred[0]+=x

centerred[1]+=y

nred +=1

plotdraw.ellipse([(x-10,y-10), (x+10, y+10)], (255,0,0))

elif d > 0:

centerblue[0]+=x

centerblue[1]+=y

nblue +=1

plotdraw.ellipse([(x-10,y-10), (x+10, y+10)], (0,0,255))

else:

plotdraw.ellipse([(x-10,y-10), (x+10, y+10)], (0,255,0))

centerred[0]/=nred

centerred[1]/=nred

centerblue[0]/=nblue

centerblue[1]/=nblue

plotdraw.ellipse([(centerred[0]-10,centerred[1]-10), (centerred[0]+10, centerred[1]+10)], (255,255,255))

plotdraw.ellipse([(centerblue[0]-10,centerblue[1]-10), (centerblue[0]+10, centerblue[1]+10)], (255,255,255))

plot.save("plot.png")

main()

## No comments:

## Post a Comment