The intersection of 2 lines can be tested with an algorithm like this:

http://www.macs.hw.ac.uk/~

Solved

Posted on 2006-03-29

I have two arrays, storing the x and y values of the polygon.

I want to find out whether the polygon is simple or complex.

The polygon can be concave and is 2d.

Can someone possibly provide suggestions.

Many Thanks.

I want to find out whether the polygon is simple or complex.

The polygon can be concave and is 2d.

Can someone possibly provide suggestions.

Many Thanks.

4 Comments

The intersection of 2 lines can be tested with an algorithm like this:

http://www.macs.hw.ac.uk/~

static double[] polyX = { 1.0, 3.0, 3.0, 1.0 };

static double[] polyY = { 1.0, 1.0, 3.0, 3.0 };

public static boolean checkComplex( final double[] x, final double[] y )

{

int i = 0, j;

for( j = i + 2; j < x.length - 1; j++ )

if( intersect( x, y, i, j ) )

return true;

for( i = 1; i < x.length; i++ )

for( j = i + 2; j < x.length; j++ )

if( intersect( x, y, i, j ) )

return true;

return false;

}

public static boolean intersect( final double[] x, final double[] y, int i1, int i2 )

{

System.out.println( "i: " + i1 + ", j: " + i2 );

int s1 = ( i1 > 0 ) ? i1 -1 : x.length - 1;

int s2 = ( i2 > 0 ) ? i2 -1 : x.length - 1;

return ccw( x[ s1 ], y[ s1 ], x[ i1 ], y[ i1 ], x[ s2 ], y[ s2 ] )

!= ccw( x[ s1 ], y[ s1 ], x[ i1 ], y[ i1 ], x[ i2 ], y[ i2 ] )

&& ccw( x[ s2 ], y[ s2 ], x[ i2 ], y[ i2 ], x[ s1 ], y[ s1 ] )

!= ccw( x[ s2 ], y[ s2 ], x[ i2 ], y[ i2 ], x[ i1 ], y[ i1 ] );

}

public static boolean ccw( double p1x, double p1y, double p2x, double p2y, double p3x, double p3y )

{

double dx1 = p2x - p1x;

double dy1 = p2y - p1y;

double dx2 = p3x - p2x;

double dy2 = p3y - p2y;

return dy1 * dx2 < dy2 * dx1;

}

Title | # Comments | Views | Activity |
---|---|---|---|

Using java code in .Net/c#: namespace issue | 3 | 38 | |

instanceof operator in java | 26 | 57 | |

Eclipse IDE - Cannot copy/paste from console output | 8 | 21 | |

Java Filesystem manipulation of Word Docx file (find replace text) | 3 | 11 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**16** Experts available now in Live!