convexe polygon around a shape

[jacques_duflos]

Hi all,
I need to get the convex form that strictly contains a text, as shown on the next image.
   
I am writing a script to do so, but maybe it already exists ? has someone heard of such tool for gimp ?

[Ofnuts]

This is called a "convex hull". There are several algorithms for this, just google. A Bezier curve is strictly enclosed in the 4 points that define it, so the thing you search is the convex hull of all the anchors and tangents in the text path (pdb.gimp_vectors_new_from_text_layer(image, layer)).

If you want an example script, my ofn-enclosing-circle does something similar: find the smallest circle that contains all the points of  a path.

[jacques_duflos]

Ok, made it !
I found the convex hull algorithm on github and completed it.
https://gist.github.com/JacquesDuflos/0a...1737e2f24f

Code:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# GIMP plugin to draw convex hulls around shapes
# (c) Jacques Duflos 2023
#
#   History:
#
#   v0.0: 2023-xx-xx: First published version

#   This program is free software; you can redistribute it and/or modify
#   it under the terms of the GNU General Public License as published by
#   the Free Software Foundation; either version 2 of the License, or
#   (at your option) any later version.
#
#   This program is distributed in the hope that it will be useful,
#   but WITHOUT ANY WARRANTY; without even the implied warranty of
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#   GNU General Public License for more details.
#
#   You should have received a copy of the GNU General Public License
#   along with this program; if not, write to the Free Software
#   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

#credit https://gist.github.com/lvngd for the ConvexHull class
import random
import sys, os
from gimpfu import *
import gimpcolor
"""
Computes the Convex Hull with the Graham Scan algorithm
Use:
    h = ConvexHull()
    print(h.hull)
"""

debug = True
def trace(s):
   if debug:
       print "**** "
       print s
       print "**** "
trace("convex_hull test")

class ConvexHull:
    def __init__(self, points):
        if not points:
            self.points = [(random.randint(0,100),random.randint(0,100)) for i in range(50)]
        else:
            self.points = points
        self.hull = self.compute_convex_hull()
   
    def get_cross_product(self,p1, p2, p3):
        return ((p2[0] - p1[0])*(p3[1] - p1[1])) - ((p2[1] - p1[1])*(p3[0] - p1[0]))

    def get_slope(self,p1, p2):
        if p1[0] == p2[0]:
            return float('inf')
        else:
            return 1.0*(p1[1]-p2[1])/(p1[0]-p2[0])

    def compute_convex_hull(self):
        hull = []
        self.points.sort(key=lambda x:[x[0],x[1]])
        start = self.points.pop(0)
        hull.append(start)
        self.points.sort(key=lambda p: (self.get_slope(p,start), -p[1],p[0]))
        for pt in self.points:
            hull.append(pt)
            while len(hull) > 2 and self.get_cross_product(hull[-3],hull[-2],hull[-1]) < 0:
                hull.pop(-2)
        return hull
        
        
def PointsFromVectors(vectors):
    num_strokes, ids = pdb.gimp_vectors_get_strokes(vectors)
    listOfPoints = []
    for stroke_id in ids:
        type_, num_points, controlpoints, closed = pdb.gimp_vectors_stroke_get_points(vectors, stroke_id)
        listOfPoints += controlpoints
    trace(listOfPoints)
    return listOfPoints

def ConvexHullVectors(image,vectors=None):
    if vectors == None : vectors = pdb.gimp_image_get_active_vectors(image)
    # get the list of every points of the vectors's stroke
    listOfPoints = PointsFromVectors(vectors)
    # organize the list to be compatible with the class
    listOfPointsTupple=[]
    while len(listOfPoints)>1:
        listOfPointsTupple.append((listOfPoints.pop(0),listOfPoints.pop(0)))
    trace ("list")
    trace (listOfPointsTupple)
    listOfPointsTupple = list(dict.fromkeys(listOfPointsTupple))
    # todo : delet at once the duplicated consecutive points (when tengents are superposed with the point)
        
    trace("list sans doublons")
    trace(listOfPointsTupple)
    
    h = ConvexHull(listOfPointsTupple)
    trace ("convex hull")
    trace (h.hull)
    hull=h.hull
    #triple each element to get a list with tengants
    hull = [[i,i,i] for i in hull]
    trace(hull)
    hull = [item for sublist in hull for item in sublist]
    trace(hull)
    #flatten the hull to be easyer tu use with gimp
    hullFlattened = [item for sublist in hull for item in sublist]
    trace ("flattened")
    trace (hullFlattened)
    #create the new vector
    hullVectors = pdb.gimp_vectors_new(image, "convex hull")
    stroke_id = pdb.gimp_vectors_stroke_new_from_points(hullVectors, VECTORS_STROKE_TYPE_BEZIER , len(hullFlattened), hullFlattened, True)
    pdb.gimp_image_insert_vectors(image, hullVectors, None, 0)
    trace ("fini")
    return hullVectors

def ConvexHullText(image,layer):
    vectorsText = pdb.gimp_vectors_new_from_text_layer(image, layer)
    ConvexHullVectors(image,vectorsText)
    
    
### Registrations
whoiam='\n'+os.path.abspath(sys.argv[0])

register(
   'convex-hull',
   'creer un convex hull autour d un texte %s' % whoiam,
   'creer un convex hull autour d un texte',
   'Jacques Duflos','Jacques Duflos','2023',
   'creer un convex hull autour d un texte...',
   '*',
   [
       (PF_IMAGE,  'image',            'Image', None),
       (PF_DRAWABLE,  'drawable',            'Drawable', None)
   ],
   [],
   ConvexHullText,
   menu='<Image>/Layer'
)

main()

[Ofnuts]

Code:

listOfPointsTupple=[]
   while len(listOfPoints)>1:
       listOfPointsTupple.append((listOfPoints.pop(0),listOfPoints.pop(0)))

Much more pythonic (and likeky faster):

Code:

listOfPointsTupple=zip((listOfPoints[0::2],listOfPoints[1::2])

[jacques_duflos]

thanks for the advice. Lists with python are a nightmare for me.

another surely optimisable part of my script is when I triple the elements of the convex hull to the points and their two tangents. And then I flatten the list with a line of code I copied without understanding it from this page. Is there a more pythonic way of doing so ?

Code:

    hull = [[i,i,i] for i in hull]
   hull = [item for sublist in hull for item in sublist]

Another curiosity in my script is the line I delete doubles. I use the line found in this page, but is it not over-engineer to use dictionaries for such a common task ?

Code:

    listOfPointsTupple = list(dict.fromkeys(listOfPointsTupple))

[Ofnuts]

(05-16-2023, 05:38 PM)jacques_duflos Wrote: thanks for the advice. Lists with python are a nightmare for me.

Lists are one of the very cool features of Python, so better get acquainted with them.

(05-16-2023, 05:38 PM)jacques_duflos Wrote: another surely optimisable part of my script is when I triple the elements of the convex hull to the points and their two tangents. And then I flatten the list with a line of code I copied without understanding it from this page. Is there a more pythonic way of doing so ?

Code:

    hull = [[i,i,i] for i in hull]
   hull = [item for sublist in hull for item in sublist]

Yes, you can actually do it in one shot:

Code:

tripledHull=[p for p in hull for _ in range(3)]

And if your ps are really points (coordinate pairs) you can even get the completely flattened list of coordinates in one shot:

Code:

➤> hull=[(1.,2.),(3.,4.),(5.,6.)]
➤> pathCoords=[c for p in hull for _ in range(3) for c in p ]
➤> pathCoords
[1.0, 2.0, 1.0, 2.0, 1.0, 2.0, 3.0, 4.0, 3.0, 4.0, 3.0, 4.0, 5.0, 6.0, 5.0, 6.0, 5.0, 6.0]

The "comprehension" is really just a loop written backwards. You can see it like this:

Code:

pathcoords=[]
for p in hull:         # we iterate the points[/font]
    for _ in range(3): # doing the same thing three times[/font]
        for c in p:     # iterate the coordinates in the point[/font]
            pathCoords.append(c)

(05-16-2023, 05:38 PM)jacques_duflos Wrote: Another curiosity in my script is the line I delete doubles. I use the line found in this page, but is it not over-engineer to use dictionaries for such a common task ?

Code:

    listOfPointsTupple = list(dict.fromkeys(listOfPointsTupple))

A slightly simpler way would be to go through a set: uniques=list(set(duplicates)). However, the set has no order, so nothing says you will be getting the points in hull order, which is important of you are making a path from it. On the other hand dictionary keys will always be listed in the order in which they have been added (so they are technically an "ordered set"). The core of python is built on very efficient hash maps and dictionaries and sets, being implemented with such maps, are very efficient. So, in the general case, using that technique has some merit. The case where ou could do better is when duplicates are guaranteed to be consecutive, in which case you could avoid adding them to the list is they are equate to targetList[-1].

Edit: Major snag: dicts are ordered since Python 3.6. Since you are in Python 2.7, you have to explicitly use an OrderedDict:

Code:

➤> from collections import OrderedDict
➤> uniques=list(OrderedDict.fromkeys(duplicates))