Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

EarCut is failing in some cases #30

Open
gkjohnson opened this issue Sep 27, 2023 · 4 comments
Open

EarCut is failing in some cases #30

gkjohnson opened this issue Sep 27, 2023 · 4 comments
Milestone

Comments

@gkjohnson
Copy link
Owner

Is this because there are crossing edges in a single loop?

image
@gkjohnson gkjohnson added this to the v0.0.2 milestone Sep 27, 2023
@gkjohnson
Copy link
Owner Author

Seems likely to be due to edge crossings:

https://jsfiddle.net/4mfn09up/5/

image

@gkjohnson
Copy link
Owner Author

gkjohnson commented Sep 27, 2023

Though on failing cases for the rover model there are no crossings listed.

Edit: Though there could still be crossings between paths

Edit2: Nope still no crossings

Count Code for All Loops
export function countCrossings( loops ) {

	const l0 = new Line3();
	const l1 = new Line3();
	let tot = 0;

	for ( let k = 0, kl = loops.length; k < kl; k ++ ) {

		const points0 = loops[ k ];
		for ( let i = 0, l = points0.length; i < l; i ++ ) {

			const i1 = ( i + 1 ) % l;
			l0.start.copy( points0[ i ] );
			l0.end.copy( points0[ i1 ] );

			l0.start.z = 0;
			l0.end.z = 0;

			for ( let k2 = k; k2 < kl; k2 ++ ) {

				const points1 = loops[ k2 ];
				for ( let j = 0, jl = points1.length; j < jl; j ++ ) {

					if ( k === k2 && j < i ) {

						continue;

					}

					const j1 = ( j + 1 ) % jl;
					l1.start.copy( points1[ j ] );
					l1.end.copy( points1[ j1 ] );

					l1.start.z = 0;
					l1.end.z = 0;

					if (
						l1.start.equals( l0.start ) ||
						l1.end.equals( l0.end ) ||
						l1.start.equals( l0.end ) ||
						l1.end.equals( l0.start )
					) {

						continue;

					}

					if ( lineCrossesLine( l0, l1 ) ) {

						tot ++;

					}

				}

			}

		}

	}

	return tot;

}
Crossing Count Code
function countCrossings( points ) {

	const l0 = new Line3();
	const l1 = new Line3();
	let tot = 0;

	for ( let i = 0, l = points.length; i < l; i ++ ) {

		const i1 = ( i + 1 ) % l;
		l0.start.copy( points[ i ] );
		l0.end.copy( points[ i1 ] );

		l0.start.z = 0;
		l0.end.z = 0;

		for ( let j = i + 2; j < l; j ++ ) {

			const j1 = ( j + 1 ) % l;
			l1.start.copy( points[ j ] );
			l1.end.copy( points[ j1 ] );

			l1.start.z = 0;
			l1.end.z = 0;

			if (
				l1.start.equals( l0.start ) ||
				l1.end.equals( l0.end ) ||
				l1.start.equals( l0.end ) ||
				l1.end.equals( l0.start )

			) {

				continue;

			}

			if ( lineCrossesLine( l0, l1 ) ) {

				tot ++;

			}

		}

	}

	return tot;

}

@gkjohnson
Copy link
Owner Author

mapbox/earcut#163

@gkjohnson
Copy link
Owner Author

gkjohnson commented Sep 28, 2023

It looks like having points that are in the same spot - either within the same loop or between holes - can cause issues. Would be best to figure out how to remove those cases.

Maybe inflation will help?

@gkjohnson gkjohnson modified the milestones: v0.0.2, v0.0.3 Sep 30, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant