Double bridges, intersecting lines, hole is being triangulated #175
Description
Using input data for a simplified letter 'P' I see a number of apparent errors in the triangulation which may be causing my box2d implementation to fail.
I've separated earcut from my box2d support code and got this output data:
indices = [1,8,13,9,8,1,1,2,3,3,4,5,6,7,0,0,1,13,9,1,3,6,0,13,10,9,3,5,6,13,11,10,3,5,13,12,11,3,5,5,12,11]```
From this input data:
```const letterP = [
[[40,100], [40,0], [120,0], [150,20], [150,40], [120,60], [80,60], [80,100]],
[[80,15], [120,15], [133,30], [133,35], [118,45], [80,45]]
];
With this code:
flattenedLetter.push(flatten(letterP));
// perform the earcut CDT
earcutIndices.push(earcut(flattenedLetter.vertices, flattenedLetter.holes, flattenedLetter.dimensions));
Looking at the image I see these potential issues:
- there appear to be two bridges from the outer edge to the inner loop
- the hole is triangularised
- triangle lines intersect each other at non-vertex locations
The result when I feed this data into box2d is a letter P with a box on top. The box will vanish if I perturb the coordinate 120,15 in the hole, to 118,15 however the visualisation of the triangles remains very similar (so, maybe it's entirely my box2d and this triangulation is correct?)
In case I've done something daft, here's the python I'm using to plot this data:
import matplotlib.pyplot as plt
import numpy as np
def plot_coordinates(coordinates, indices):
"""
Plot connected points from a flat coordinate list using specified indices.
Args:
coordinates (list): Flat list of coordinates in x,y,x,y... order
indices (list): List of indices where each index i refers to the ith x-coordinate
(with corresponding y-coordinate at position 2i+1)
"""
# Convert the indexed coordinates into x and y lists
x_coords = []
y_coords = []
for idx in indices:
x_coords.append(coordinates[idx * 2])
y_coords.append(coordinates[idx * 2 + 1])
# Create the plot
plt.figure(figsize=(10, 6))
# Plot the points
plt.scatter(x_coords, y_coords, color='blue', s=50)
# Connect the points with lines
plt.plot(x_coords, y_coords, 'b-', linewidth=1)
# Add axes lines at x=0 and y=0
plt.axhline(y=0, color='gray', linestyle='-', linewidth=0.5)
plt.axvline(x=0, color='gray', linestyle='-', linewidth=0.5)
# Add grid
plt.grid(True, linestyle='--', alpha=0.7)
# Equal aspect ratio so circles look circular
plt.axis('equal')
# Add labels
plt.xlabel('X')
plt.ylabel('Y')
plt.title('Connected Coordinates Plot')
# Show the plot
plt.show()
coordinates = [ 40,100, 40,0, 120,0, 150,20, 150,40, 120,60, 80,60, 80,100, 80,15, 120,15, 133,30, 133,35, 118,45, 80,45 ]
indices = [1,8,13,9,8,1,1,2,3,3,4,5,6,7,0,0,1,13,9,1,3,6,0,13,10,9,3,5,6,13,11,10,3,5,13,12,11,3,5,5,12,11]
plot_coordinates(coordinates, indices)