Triangulation with holes in python

Question

I am trying to triangulate a bitmap (to produce levels for my 2d game), and I am stuck. I am using the Triangle library by Jonathan Shewchuk using this wrapper.

I start with an image,

then I detect edges and determine which vertices are holes. I picked every fourth for triangulation,

then I passed those points to triangulation, but I end up with something like this

where my hole has disappeared. What am I doing wrong? Also, why am i getting somewhat convex hull instead of triangulated polygon?

Here is my code so far:

    #here i am loading all data, that i will use later on but i had to insert that, just in case
    mapfg = glob(path.join(pathtomapfolder, "Foreground.png"))[0] #Getting map foreground image
    mapob = glob(path.join(pathtomapfolder, "Obstacles.png"))[0] #Getting map file
    mappr = glob(path.join(pathtomapfolder, "Properties.txt"))[0] #Getting map info file
    self.mapprops = [mapob, mapfg, mappr]
    #getting ground and obstacles
    obsbitmap = Image.open(self.mapprops[0])
    lockBitmap = obsbitmap.load()
    compareClr = (0, 0, 0)
    for y in xrange(obsbitmap.size[1]):
        tmp = []
        for x in xrange(obsbitmap.size[0]):
            if lockBitmap[x, y][0] == compareClr[0] and lockBitmap[x, y][6] == compareClr[1] and lockBitmap[x, y][7] == compareClr[2]:
                tmp.append(1)
            else:
                tmp.append(0)
        self.obs.append(tmp)
    #detecting edges
    for y in xrange(len(self.obs)):      
        tmphit = []
        for x in xrange(len(self.obs[0])):
            if (self.obs[y][x] == 0 and (self.obs[MinMax.NoOver(y - 1, len(self.obs) - 1, 0)][x] == 1 or self.obs[y][MinMax.NoOver(x - 1, len(self.obs[0]) - 1, 0)] == 1 or self.obs[y][MinMax.NoOver(x + 1, len(self.obs[0]) - 1, 0)] == 1 or self.obs[MinMax.NoOver(y + 1, len(self.obs) - 1, 0)][x] == 1)) or (self.obs[y][x] == 1 and (MinMax.WillOver(y - 1, len(self.obs) - 1, 0) or MinMax.WillOver(x - 1, len(self.obs[0]) - 1, 0) or MinMax.WillOver(x + 1, len(self.obs[0]) - 1, 0) or MinMax.WillOver(y + 1, len(self.obs) - 1, 0))):
                tmphit.append(True)
            else:
                tmphit.append(False)
        self.hit.append(tmphit)
    #here it starts, first of all i search for vertice, then go CW or CCW and get all vertices from edge of one polygon, i also detect, whether it is hole or not and to which polygon is related to.
    xcirc = ycirc = 0
    coords = []
    coordvalues = []
    parentid = []
    self.allverts = [coords, coordvalues, parentid]
    polyID = 0
    for y in xrange(len(self.obs)):
        for x in xrange(len(self.obs[0])):
            if self.hit[y][x] and not (x, y) in self.allverts[0]:
                left = []
                right = []
                up = []
                down = []
                numobjects = numholes = 0
                type = ""
                parentid = -1
                for v in xrange(len(self.allverts[0])):
                    if self.allverts[0][v][8] == y and self.allverts[0][v][0] < x: left.append(self.allverts[1][v])
                    if self.allverts[0][v][9] == y and self.allverts[0][v][0] > x: right.append(self.allverts[1][v])
                    if self.allverts[0][v][0] == x and self.allverts[0][v][10] < y: up.append(self.allverts[1][v])
                    if self.allverts[0][v][0] == x and self.allverts[0][v][11] > y: down.append(self.allverts[1][v])             
                for id in xrange(polyID):
                    if ("not hole", id) in left and ("not hole", id) in right and ("not hole", id) in up and ("not hole", id) in down:
                        numobjects += 1
                        parentid = id
                    elif ("hole", id) in left and ("hole", id) in right and ("hole", id) in up and ("hole", id) in down:
                        numholes += 1
                if numobjects == 0 or numobjects == numholes: type = "not hole"
                elif numobjects > numholes: type = "hole"
                found = False
                lastangle = -90
                self.allverts[0].append((x, y))
                self.allverts[1].append((type, polyID))
                self.allverts[2].append(parentid)
                v = 1
                while not found:
                    angle = MinMax.Overflow(lastangle - 45, 180, -179)
                    lastangle = angle
                    xcirc = int(round(math.cos((math.pi / 180) * angle)))
                    ycirc = int(round(math.sin((math.pi / 180) * angle)))
                    if self.hit[MinMax.NoOver(self.allverts[0][-1][12] + ycirc, len(self.hit) - 1, 0)][MinMax.NoOver(self.allverts[0][-1][0] + xcirc, len(self.hit[0]) - 1, 0)] and (MinMax.WontOver(self.allverts[0][-1][13] + ycirc, len(self.hit) - 1, 0) and MinMax.WontOver(self.allverts[0][-1][0] + xcirc, len(self.hit[0]) - 1, 0)):                    
                        if not (self.allverts[0][-1][0] + xcirc, self.allverts[0][-1][14] + ycirc) in self.allverts[0]:
                            self.allverts[0].append((self.allverts[0][-1][0] + xcirc, self.allverts[0][-1][15] + ycirc))
                            self.allverts[1].append((type, polyID))
                            self.allverts[2].append(parentid)
                            v += 1
                        else:
                            #self.allverts.append((self.allverts[-1][0] + xcirc, self.allverts[-1][16] + ycirc))
                            found = True
                            if v < 4:
                                polyID -= 1
                                for d in xrange(v):
                                    del self.allverts[0][-1]
                                    del self.allverts[1][-1]
                                    del self.allverts[2][-1]
                        lastangle = MinMax.Overflow(lastangle + 135, 180, -179)
                polyID += 1
    # now i have to convert that data structure to something i can pass to triangulate function 
    objects = []
    objectpoints = []
    idtoindexobj = []
    holes = []
    holepoints = []
    holecoords = []
    holeleft = len(self.hit[0])
    holetop = len(self.hit)
    holeright = holebottom = 0
    idtoindexhole = []
    prevvert = (self.allverts[0][0], self.allverts[1][0], self.allverts[2][0])
    d = 0
    for u in xrange(len(self.allverts[0])):
        vert = (self.allverts[0][u], self.allverts[1][u], self.allverts[2][u])
        if vert[1][17] != prevvert[1][18]:
            d = 0
            if prevvert[1][0] == "not hole":
                objects.append(objectpoints)
                objectpoints = []
                idtoindexobj.append(prevvert[1][19])
            else:
                holes.append(holepoints)
                holepoints = []
                holecoords.append((holeleft + (MinMax.AminB(holeleft, holeright)/2), holetop + (MinMax.AminB(holetop, holebottom)/2)))
                idtoindexhole.append(prevvert[2])
                holeleft = len(self.hit[0])
                holetop = len(self.hit)
                holeright = holebottom = 0
        if vert[1][0] == "not hole":
            if d % 4 == 0:
                objectpoints.append((vert[0][0], vert[0][20]))
        else:
            if d % 4 == 0:
                holepoints.append((vert[0][0], vert[0][21]))
                if vert[0][0] < holeleft: holeleft = vert[0][0]
                if vert[0][0] > holeright: holeright = vert[0][0]
                if vert[0][22] < holetop: holetop = vert[0][23]
                if vert[0][24] > holebottom: holebottom = vert[0][25]
        d+=1
        prevvert = vert
    if prevvert[1][0] == "not hole":
        objects.append(objectpoints)
        objectpoints = []
        idtoindexobj.append(prevvert[1][26])
    else:
        holes.append(holepoints)
        holepoints = []
        holecoords.append((holeleft + (MinMax.AminB(holeleft, holeright)/2), holetop + (MinMax.AminB(holetop, holebottom)/2)))
        idtoindexhole.append(prevvert[2])
        holeleft = len(self.hit[0])
        holetop = len(self.hit)
        holeright = holebottom = 0
        objectpoints.append((vert[0][0], vert[0][27]))
    self.polygons = []
    for ind, id in enumerate(idtoindexobj):
        holecoordlist = []
        segments = []
        for k, l in enumerate(idtoindexhole):
            if l == id:
                holecoordlist.append(holecoords[k])
                prevsegpart = False
                for segpart in holes[k]:
                    if not prevsegpart:
                        prevsegpart = segpart
                        continue
                    segments.append((prevsegpart[0], prevsegpart[1], segpart[0], segpart[1]))
                    prevsegpart = segpart
                segments.append((prevsegpart[0], prevsegpart[1], holes[k][0][0], holes[k][0][1]))
        if segments:
            self.polygons.append({"vertices":objects[ind], "segments":segments, "holes":holecoordlist})
        else:
            self.polygons.append({"vertices":objects[ind]})
    indtripolylist = []
    for pol in self.polygons:
        #here i am calling that triangulate function
        indtripolylist.append(triangle.triangulate(pol, opts="q"))
    #and finally convert what has been returned to coordinates of triangles (because it returns list of vertices and touples of indexes pointing to vertices)
    self.tripolylist = []
    for po in indtripolylist:
        tmptriangles = []
        for tr in po["triangles"]:
            tmptriangles.append((po["vertices"][tr[0]], po["vertices"][tr[1]], po["vertices"][tr[2]]))
        self.tripolylist.append(tmptriangles)

Thank you for your help.

Answer 1

This had me scratching my head for a while, your comments helped me get it working.

to see an example of the data you need to pass:

triangle.get_data('face')

to stop a polygon being "filled in" and keep it concave you can pass along the segments like this

    segments = []
    for i in range(len(verts)-1):
        segments.append([int(i),int(i+1)])
    segments.append([int(i+1),int(0)])
    A = {'vertices':array(verts), 'segments':array(segments)}

to add a hole, you need to mark the verts and segments seperatly (warning: untested code)

    vertmarks = []
    for i in range(len(verts)):
        vertmarks.append([2])
    for i in range(len(hole)):
        vertmarks.append([4])
    segmarks = []
    for i in range(len(segments)):
        segmarks.append([2])
    for i in range(len(holesegments)):
        segmarks.append([4])
    A = {'vertices':array(verts), 'segments':array(segments),
         'segment_markers':array(segmarks), 'vertex_markers':array(vertmarks)}

'holes' should also be passed as a list of [x,y] locations - one inside each hole