Triangulation with holes

[novrain99]

Hi,

I am working on a project with character shapes and I need to triangulate some polygons with holes (e.g. the character B). Does your project offer any possibility to solve such a problem?

Cheers,

[GeorgySk]

Hi, @novrain99! Yes, the Polygon class has the triangulate method which performs constrained Delaunay triangulation: https://github.com/lycantropos/gon/blob/master/gon/core/polygon.py#L991

[lycantropos]

Hi @novrain99, as @GeorgySk noted it is possible using Polygon.triangulate method which returns a constrained Delaunay triangulation which considers holes & concavity, to get triangles from triangulation you can simply call Triangulation.triangles method.

[novrain99]

Hi, @lycantropos, @GeorgySk ,

Thanks a lot for your reply and your great work! gon helps me a lot! I just tried to instantiate a Polygon object and the triangulate method. It gives a perfect constrained Delaunay triangulation for the character Y. I just have this question, is there an already existing way to perform the triangulation refinement over the result of the first Delaunay triangles?

I can think of a less immediate way of adding some random extra points inside the polygon of the character, so I wonder if there is already an existing method from gon.

Here is the result I got.

Cheers, @novrain99

[lycantropos]

@novrain99 currently gon doesn't support any triangulation refinement, so if you need one -- you need to investigate and probably implement one

[novrain99]

@lycantropos Hi, thanks for the info! I use the way I mentioned in my last message to generate the triangles. I just have met this problem that, with the same number of extra internal points, the result can be very different. Sometimes it looks perfect and sometimes part of the shape of the character is missing. For example, I tested with the character B which has two holes as a polygon. Here are the results of two tests with 500 internal points: May I ask if you have any insight about this behavior?

Below is how I made the triangulation:

import shapely
import numpy as np 
from gon.base import (EMPTY,
                    Angle, 
                    Contour, 
                    Point, 
                    Polygon,
                    Triangulation
                    )
from ground.base import Context
import matplotlib.pyplot as plt

def generate_random_points(polygon, nb_pts):
    count = 0
    interior = []
    minx, miny, maxx, maxy = polygon.bounds
    while count < nb_pts:
        x = np.random.uniform(minx, maxx)
        y = np.random.uniform(miny, maxy)
        pnt = shapely.Point(x, y)
        if polygon.contains(pnt) and pnt not in interior:
            interior.append([x,y])
            count += 1
    print('Finished.')
    return interior

contour_cap_b = np.load('capital_b.npy')
hole0_b = np.load('hole0.npy')
hole1_b = np.load('hole1.npy')

ext_cap_b = [[p[0], -p[1]] for p in contour_cap_b]
int_cap_b = [[[p[0], -p[1]] for p in hole0_b],
             [[p[0], -p[1]] for p in hole1_b]]

pts_contour_cap_b = [Point(x[0], -x[1]) for x in contour_cap_b]
pts_hole0_b = [Point(x[0], -x[1]) for x in hole0_b]
pts_hole1_b = [Point(x[0], -x[1]) for x in hole1_b]

# build the polygon

polygon_cap_b = Polygon(Contour(pts_contour_cap_b),
                        [Contour(pts_hole0_b),
                         Contour(pts_hole1_b)])
shapely_cap_b = shapely.Polygon(ext_cap_b, 
                                int_cap_b) 

list_nb_pts = [500]

for nb_pts in list_nb_pts:
    int_pts = generate_random_points(shapely_cap_b, nb_pts)
    triangulation = Triangulation.constrained_delaunay(
        polygon=polygon_cap_b,
        extra_constraints=[],
        extra_points=[Point(p[0], p[1]) for p in int_pts],
        context=Context()
    )
    triangles = triangulation.triangles()
    retrieved_points = []
    for triangle in triangles:
        for p in triangle.vertices:
            if p not in retrieved_points: retrieved_points.append(p)
    plt.subplot(1,3,list_nb_pts.index(nb_pts)+1)
    for triangle in triangles:
        plt.plot([p.x for p in triangle.vertices] + [triangle.vertices[0].x], 
                 [p.y for p in triangle.vertices] + [triangle.vertices[0].y])

plt.show()

Cheers,

[lycantropos]

@novrain99 can you please provide a file with a letter polygon? otherwise I'm not able to reproduce this behavior

[novrain99]

@lycantropos Sure! Here are the files I used for the mentioned tests. The contour and two holes for character B.
Archive.zip

[lycantropos]

@novrain99 there are several issues with the script:

1. Using shapely: its Polygon.contains is error-prone and unreliable (as almost all other of shapely routines).
2. Contours in gon should not have its last vertex being equal to the first vertex, because it's redundant, in general before processing we can simply call Polygon.validate or Contour.validate methods and see if they raise any errors (if no errors -- then everything should work just fine).
3. Contours should not have collinear vertices (since it is also redundant and potentially may cause problems along the way), but for our case it's not big of an issue.
4. If we have a lot of queries to a particularPolygon-- then it will be beneficial to Polygon.index it first to improve performance.
5. Using set instead of list can also be an improvement (but I haven't measured it, may not be an issue at all).

So finally we will have something like

import matplotlib.pyplot as plt
import numpy as np
from ground.base import get_context

from gon.base import (Contour,
                      Point,
                      Polygon,
                      Triangulation)

def generate_random_points(polygon: Polygon, nb_pts, context=get_context()):
    interior = []
    bounding_box = context.polygon_box(polygon)
    while len(interior) < nb_pts:
        x = np.random.uniform(bounding_box.min_x, bounding_box.max_x)
        y = np.random.uniform(bounding_box.min_y, bounding_box.max_y)
        pnt = Point(x, y)
        if pnt in polygon and pnt not in interior:
            interior.append(pnt)
    print('Finished.')
    return interior

contour_cap_b = np.load('capital_b.npy')
hole0_b = np.load('hole0.npy',
                  allow_pickle=False)
hole1_b = np.load('hole1.npy',
                  allow_pickle=False)

ext_cap_b = [[p[0], -p[1]] for p in contour_cap_b]
int_cap_b = [[[p[0], -p[1]] for p in hole0_b],
             [[p[0], -p[1]] for p in hole1_b]]

pts_contour_cap_b = [Point(x[0], -x[1]) for x in contour_cap_b[:-1]]
pts_hole0_b = [Point(x[0], -x[1]) for x in hole0_b[:-1]]
pts_hole1_b = [Point(x[0], -x[1]) for x in hole1_b[:-1]]

# build the polygon

polygon_cap_b = Polygon(Contour(pts_contour_cap_b),
                        [Contour(pts_hole0_b),
                         Contour(pts_hole1_b)])
polygon_cap_b.index()

list_nb_pts = [500] * 5

for i, nb_pts in enumerate(list_nb_pts):
    extra_points = generate_random_points(polygon_cap_b, nb_pts)
    with open(f'extra_points_{i}.txt', 'w') as extra_points_file:
        extra_points_file.write(repr(extra_points))
    triangulation = Triangulation.constrained_delaunay(
            polygon=polygon_cap_b,
            extra_constraints=[],
            extra_points=extra_points,
            context=get_context()
    )
    triangles = triangulation.triangles()
    retrieved_points = []
    for triangle in triangles:
        for p in triangle.vertices:
            if p not in retrieved_points:
                retrieved_points.append(p)
    plt.clf()
    for triangle in triangles:
        plt.plot([p.x for p in triangle.vertices] + [triangle.vertices[0].x],
                 [p.y for p in triangle.vertices] + [triangle.vertices[0].y])
    plt.savefig(f'graph_{i}.png')

and the problem with parts of the letter being cut goes away

[lycantropos]

Some of the generated examples please let me know if there are still some issues left

[novrain99]

@lycantropos Wow! A big thanks! I tried to not use shapely and the last identical points just then, it works perfectly! I didn't read very carefully the doc of gon and was not sure if it also had something like Polygon.contains in shapely, so I chose to use that. Now I know it's better to use gon directly. All in all, big thanks!

Cheers,

[novrain99]

I close the issue now.