UV shotgun

import bpy
from mathutils import geometry as gm
import math
import random
import time

#from os.path import dirname
#module_dir = "\\".join(dirname(__file__).split("\\")[:-1])

#import sys
#if not module_dir in sys.path:
#    sys.path.insert(0, module_dir)

rnd = random.random

class Island():
    def __init__(self, polys, obj):
        self.obj = obj
        self.polys = polys
        self.verts = []
        self.uv_layer = obj.data.uv_layers.active
        self.vertcount = 0

        # verts matching poly indices
        for f in self.polys:
            lidcs = obj.data.polygons[f].loop_indices
            self.verts.append([[*self.uv_layer.data[l].uv] for l in lidcs])
            self.vertcount += len(lidcs)
        self._bb_calc()

    def _bb_calc(self):
        self.minx, self.miny, self.maxx, self.maxy = (100.0,100.0, -100.0,-100.0)
        self.avg_x, self.avg_y = 0.0, 0.0
        for a in self.verts:
            for t in a:
                if t[0] > self.maxx: self.maxx = t[0]
                if t[0] < self.minx: self.minx = t[0]
                if t[1] > self.maxy: self.maxy = t[1]
                if t[1] < self.miny: self.miny = t[1]

                self.avg_x += t[0]
                self.avg_y += t[1]

        self.avg_x //= self.vertcount
        self.avg_y //= self.vertcount

        self.bb_x = self.maxx - self.minx
        self.bb_y = self.maxy - self.miny

        self.bb_size = round(self.bb_x * self.bb_y, 4)

        # uv edges
        self.lines = []
        for f in range(len(self.verts)):
            for j in range(len(self.verts[f])):
                self.lines.append((
                    tuple(self.verts[f][j]),
                    tuple(self.verts[f][(j+1)%len(self.verts[f])])))

        # sort uv edges by x location from 0->
        #self.lines = [(i[0],i[1]) if i[0][0]<i[1][0] else (i[1],i[0]) for i in self.lines]
        #self.lines.sort(key=lambda x: x[0][0])

    def check_collision(self, other):
        # check bounding boxes
        if self.minx > other.maxx or self.miny > other.maxy or self.maxx < other.minx or self.maxy < other.miny:
            return False

        # check for point inside polygon collision, random
        a = self.verts[random.randint(0, len(self.verts)-1)]
        for t in a:
            for f in other.verts: # faces
                if len(f) == 4:
                    if gm.intersect_point_quad_2d(t, f[0], f[1], f[2], f[3]):
                        return True
                elif len(f) == 3:
                    if gm.intersect_point_tri_2d(t, f[0], f[1], f[2]):
                        return True

        # check for line collisions
        for l in self.lines:
            for ol in other.lines:
                if gm.intersect_line_line_2d(l[0], l[1], ol[0], ol[1]):
                    return True

        return False

    def _updateloc(self, x, y):
        self.maxx += x
        self.minx += x
        self.maxy += y
        self.miny += y
        self.lines = [((a[0]+x,a[1]+y), (b[0]+x,b[1]+y)) for (a,b) in self.lines]

    def rotate90(self):
        for i in range(len(self.verts)):
            for j in range(len(self.verts[i])):
                x = self.verts[i][j][0]
                y = self.verts[i][j][1]
                self.verts[i][j][0] = self.avg_y - y
                self.verts[i][j][1] = x - self.avg_x
        self._bb_calc()

    def flipx(self):
        for i in range(len(self.verts)):
            for j in range(len(self.verts[i])):
                x = self.verts[i][j][0]
                self.verts[i][j][0] = self.avg_x - x
        self._bb_calc()

    def move(self, x, y):
        for i in range(len(self.verts)):
            for j in range(len(self.verts[i])):
                self.verts[i][j][0] += x
                self.verts[i][j][1] += y
        self._updateloc(x, y)

    def set_location(self, x, y):
        dispx = x - self.minx
        dispy = y - self.miny
        for i in range(len(self.verts)):
            for j in range(len(self.verts[i])):
                self.verts[i][j][0] += dispx
                self.verts[i][j][1] += dispy
        self._updateloc(dispx, dispy)

    def write(self):
        for fi, f in enumerate(self.polys):
            for i, loop_idx in enumerate(self.obj.data.polygons[f].loop_indices):
                self.obj.data.uv_layers.active.data[loop_idx].uv = \
                    self.verts[fi][i]

    def __repr__(self):
        return "verts: " + repr(self.verts) + "  polys: " + repr(self.polys)


def approximate_islands(ob, uv_layer):
    islands = []

    # merge polygons sharing uvs
    for poly in ob.data.polygons:
        #poly_info = list(zip([i for i in poly.loop_indices], [i for i in poly.vertices]))
        poly_info = [i for i in poly.loop_indices]
        uvs = set((round(uv_layer[i].uv[0], 4), round(uv_layer[i].uv[1], 4)) for i in poly_info)
        notfound = True
        for i,island in enumerate(islands):
            if island & uvs != set():
                islands[i] = islands[i].union(uvs)
                notfound = False
                break
        if notfound:
            islands.append(uvs)

    # merge sets sharing uvs
    for isleidx in range(len(islands)):
        el = islands[isleidx]
        notfound = True
        for i, isle in enumerate(islands):
            if i == isleidx:
                continue
            if el & isle != set():
                islands[i] = islands[i].union(el)
                islands[isleidx] = set()
                notfound = False
                break

    # remove empty sets
    islands = [i for i in islands if i != set()]
    return islands

bpy.ops.object.mode_set(mode='OBJECT')
ob = bpy.context.object
uv_layer = ob.data.uv_layers.active.data

# get islands and their verts
islands = approximate_islands(ob, uv_layer)
print(len(islands))

# connect polys to island data
islefaces = [set()] * len(islands)
for poly in ob.data.polygons:
    uvs = set((round(uv_layer[i].uv[0], 4), round(uv_layer[i].uv[1], 4)) for i in poly.loop_indices)
    for i, isle in enumerate(islands):
        if uvs & isle != set():
            islefaces[i] = islefaces[i].union(set([poly.index]))

isles = []
for i in range(len(islands)):
    isles.append(Island(islefaces[i], ob))

isles.sort(key=lambda x: 1-x.bb_size)
print(isles[0].bb_size)

#for i in isles:
#    i.move(-1.0, 0.0)

#isles[0].move(-isles[0].minx, -isles[0].miny)

# start monte carlo iteration
iters = 2000
iter_div = float(iters)/1.5
start_time = time.time()
total_checks = 0

for p in range(len(isles)):
    icnt = 0
    pcnt = 0
    # find a free location
    for i in range(iters):
        i_div = float(i)/iter_div
        #isles[p].set_location(rnd()*(1.0-isles[p].bb_x)*float(i)/iter_div, rnd()*(1.0-isles[p].bb_y)*float(i)/iter_div)
        if rnd() > 0.75:
            isles[p].rotate90()

        if rnd() > 0.75:
            isles[p].flipx()

        if rnd() > 0.5: # x or y axis
            isles[p].set_location(rnd()*i_div, 1.0*i_div)
        else:
            isles[p].set_location(1.0*i_div, rnd()*i_div)

        somecollision = False
        for tf in range(0,p):
            icnt += 1
            if isles[p].check_collision(isles[tf]):
                somecollision = True

        pcnt += 1
        if not somecollision:
            break
    # zigzag with y and x axis towards origin until collision

    print(repr(p)+"/"+repr(len(isles))+" i:"+repr(icnt)+" p:"+repr(pcnt))
    total_checks += icnt

end_time = time.time()
tot_time = end_time - start_time
print(repr(total_checks) + " total collision checks in " + repr(round(tot_time,2))+" seconds. (" + repr(round(float(total_checks)/tot_time, 2)) + " checks per second)")

# write data out
for i in isles:
    i.write()