Need a few pointers

[Things]

Hi guys, I've got a bit of programming to do.

Basically I've got a set of coords for various lines which make up a "polygon", which can be anywhere from 3 to over 12 lines.

I somehow need to check if any of these lines intercept, in code. I can handle the programming aspect of this fine, but I'm unsure as to the maths. Any tips?

[iceisfun]

So your trying to figure out if a point is in a concave polygon or if the polygon has overlapped itself?

[iceisfun]

This is the book I use for a reference when doing any type of intersections

http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323/ref=sr_1_1?ie=UTF8&qid=1395718467&sr=8-1&keywords=collision+detection

[Things]

Basically just checking if any of the lines overlap any other lines, as it effects the area measurement. I don't necessarily need to know where, and what lines cross, basically just if they do.

[T3sl4co1l]

Obligatory joke;
http://xkcd.com/138/


2D?

I did something like that for a sort of graphics engine playaround in Java, lemme see if I can find the relevant bits...

[Linedef] is a class which contains two fields: a pair of Vertex objects, representing the ends of the line.  (It also has some other properties relevant to the engine, but not important here.)

Code: [Select]

public class Linedef {

	/**	Vertices defining the start and end points of the Linedef.	*/
	public Vertex v1, v2;

...

	/**
	 * Calculates the intersection point of the line against an
	 * infinite line, extending from the line segment provided.
	 * @param l line to test against.
	 * @return null if any elements are null, or if the lines are
	 * parallel; else, an Intersection containing two scalars,
	 * representing the percent length along the line (relative to
	 * each line's v1) where the intersection lies, a Vertex
	 * containing the actual coordinates of the intersection,
	 * and a scalar representing the distance from
	 * the line 
	 */
	public Intersection intersection(Linedef l) {
		if (l == null || this.v1 == null || this.v2 == null
				|| l.v1 == null || l.v2 == null)
			return null;
		Vertex d1 = new Vertex(this.v2); d1.subtract(this.v1);
		Vertex d2 = new Vertex(l.v2); d2.subtract(l.v1);
		Vertex d3 = new Vertex(this.v1); d3.subtract(l.v1);
		double det = d1.determinant(d2);
		double c1, c2, side;
		side = d1.determinant(d3);
		if (det == 0)
			//	Lines are parallel, intersection is infinite
			return new Intersection(Double.NaN, Double.NaN, d1, side, this);
		c1 = d2.determinant(d3) / det;
		c2 = side / det;
		side /= d1.norm();
		d1.scalar(c1); d1.add(v1);
		return new Intersection(c1, c2, d1, side, this);
	}
}

[Vertex] is, in effect, an object representing a complex number, or 2x2 matrix (this will become more apparent below).  [Intersection] is merely a container object for returning from the above method.  If you need the lines in 3D -- the chances of random lines in 3D intersecting of course being very small -- these classes can be modified (possibly extended?) to do essentially the same math with an extra dimension (in effect, 3x3 matrices, or quaternions if you like that sort of thing).  You'll want to check if the linear algebra is in fact consistent in that case.

Code: [Select]

public class Vertex {

	public double x, y;

...

	/**
	 * Adds another vector to this one.
	 * @param v vector to add.
	 */
	public void add(Vertex v) {
		if (v == null)
			return;
		x = x + v.x; y = y + v.y;
	}

	public void subtract(Vertex v) {
		if (v == null)
			return;
		x = x - v.x; y = y - v.y;
	}

	/**
	 * Finds the determinant of this vertex against the specified vertex,
	 * i.e. calculates:
	 * det =
	 * | this.x   v.x |
	 * | this.y   v.y |
	 * = this.x * v.y - v.x * this.y
	 * @param v the other vertex composing the determinant. 
	 * @return NaN if v is null, else the determinant.
	 */
	public double determinant(Vertex v) {
		if (v == null)
			return Double.NaN;
		return this.x * v.y - v.x * this.y;
	}

	/**
	 * Finds the norm of this vector.
	 * @return norm (or magnitude or length).
	 */
	public double norm() {
		return Math.hypot(x, y);
	}

	/**
	 * Scalar multiplication of this vector.
	 * @param c scalar to multiply by.
	 */
	public void scalar(double c) {
		x = x * c; y = y * c;
	}
}

In both cases, the constructors are boring (fields from parameters).

After all of this, you get the constants c1 and c2 in the [Intersection] object, which indicate how far along each line segment the intersection occurred.  The lines are actually crossing if 0 <= c1 < 1 and 0 <= c2 < 1.  Beware of null and infinite (parallel, divide by zero) results.

Tim

[IanB]

I was thinking along the lines of what T3sl4co1l proposes. I'm not sure if there is a simpler or more elegant way to approach the problem. Here is an explanation of the mathematics in simple terms:

Suppose you have two line segments in a plane.

Let the first line be between the points (x1, y1) and (x2, y2).

Let the second line be between (x3, y3) and (x4, y4).

Now a variable c1 can be used to represent the distance along the first line, where c1 is between 0 (start of line) and 1 (end of line). Another variable c2 can do the same for the second line.

It follows that the x-coordinate of c1 is given by:

c1x = x1 + c1 * (x2 - x1)

In a similar manner,

c2x = x3 + c2 * (x4 - x3)

c1y = y1 + c1 * (y2 - y1)

c2y = y3 + c2 * (y4 - y3)

At the point where the lines intersect the x- and y-coordinates are equal. So:

c1x = c2x
c1y = c2y

This gives two simultaneous equations:

x1 + c1 * (x2 - x1) = x3 + c2 * (x4 - x3)

y1 + c1 * (y2 - y1) = c2y = y3 + c2 * (y4 - y3)

Solve these equations for c1 and c2 and that will give the point of intersection. If the intersection point lies within both lines, then the lines cross. The intersection point will be within both lines if 0 < c1 < 1 and 0 < c2 < 1.

If c1 or c2 equals 0 or 1 then one of the end points of the lines is intersecting. You will expect this to happen between two lines if they are joined end to end in a polygon.

[Mandelbrot]

I can't help with your problem, but your thread title reminded me of this comic:
http://xkcd.com/138/

edit: Oops, looks like T3sl4co1l beat me to it...

[zapta]

Whatever you do, try to avoid floating point and use integer only.  Floating points are in accurate and difficult to predict in edge cases.

If you need to compute pair wise intersection of a large set of lines this can be expensive. Try to reduce the computation, for example using a a quick comparison x,y's or the signs of dot products (again, with integers only). Typically most pairs of segments in your set will not intersect.

[T3sl4co1l]

Hmm, the numerically unstable part of the calculation lies in division by a difference.

Among real numbers, this is fine unless the line segments are well and truly parallel.  Much the same as saying, two random uncorrelated real numbers will *never* be equal, only greater or lesser than; except in circumstances with an explicit mathematical constraint (which is equivalent to specifying that the numbers are equal).  In analog circuitry, there is no "equator", only the comparator -- greater or lesser than.  (Of course, on the margin near "equal", finite gain and SNR result in a hazy gray area, which could be interpreted as "approximately equal", or as a measure of statistical confidence, "we're not very sure which one is greater".

Floats are a good approximation, and in practice the only exceptions you'll see are contrived cases.  In my program, I do observe an error in one cardinal direction, if the position is advanced only in fixed steps (as soon as you, for example, turn and move in another direction, the bits are all wrong and it won't do it anymore -- unless you perform the exact same movements in reverse, which may not even be possible).  (The underlying cause is not parallelism, but actually being exactly on the line between regions, and technically being on one region while trying to draw something from the other -- which doesn't exist, so it doesn't draw anything on that one point.)

Other than contrived cases (very particular moves, setups, etc.), I have seen one other instance of this sort of error.  I was playing Portal, and trying to move extremely precisely through a portal.  I suspect it crashed when I reached the point exactly in the middle, so it couldn't tell which side I was on (either trying to perform all the tasks -- collision, graphics, physics, etc. -- of both rooms, or neither!) and broke.

So, it's worth noting that, even if you do use floats (which I wouldn't recommend for embedded, but the platform is unspecified), although the chances of equality are small, the case still exists, and sooner or later must be handled.  I imagine many a random game crash has resulted from exactly this fallacy of ignoring the trichotomy of numbers (lesser than, equal to, or greater than).

All this to say; even if you use floats, you have to watch out for it.  You can get away without, but don't whine if you see random, irreproducible errors.  The chances are much, much greater if you use smaller floats (i.e., float instead of double), and greater still under some unlucky combinations of integers (a 32 bit int contains as much information as a 32 bit float, but it depends on how you use it; in fixed point, you must always watch out for the dynamic range (how big the integral part can get / needs to be) and precision detail (how small the fractional steps are; how excess bits of products and quotients are handled).

Going back to division by difference: there are some options.  The determinant of integers will always be an integer.  A singular matrix has a zero determinant, so you can check that as a conditional; a singular matrix also has no inverse.  However, the adjoint of a matrix (I'd have to look up what the definition is for a 2x2) is nearly the inverse (there's also a pseudo-inverse, but I forget what and why), and always exists, even of a singular matrix.  By avoiding total inversion or division, you can potentially do the calculations in a more stable manner, avoiding division until the last possible step.  This also helps retain accuracy and numerical stability, especially when integers or relatively few bits are used.  (Obviously, this also goes for digital (hardware) calculations, but the same lessons apply to analog circuits as well -- not that analog computers are all that popular these days.)

Tim

[zapta]

Among real numbers, this is fine unless the line segments are well and truly parallel.  Much the same as saying, two random uncorrelated real numbers will *never* be equal, only greater or lesser than; except in circumstances with an explicit mathematical constraint (which is equivalent to specifying that the numbers are equal). ...

In computational geometry this is called 'general position'. Very useful when you want to analyze or proove stuff because you don't need to deal with special cases (e.g. three points are collinear).  In reality, when you want to implement an algorithm, this are not as simple and singular cases bite you when your least expect. In addition floating points introduce uncertainty and errors that make things worse. From my experience, forcing all the points to an integer grid and then avoiding floats is your best chance to achieve determinism, reproduce and fix bugs and maintain your sanity. One way as you mention is to defer divisions and reduce the problem to comparison. (equality is also ok when you deal with integers).

My favorite function when I dealt with this stuff was the cross product. Given a segment (a, b) and a point c it tells you if c is on the right, left or collinear with the segment (a, b), all without any  division and with perfect accuracy if a, b, c coordinates are integers.  It can be used creatively and I wouldn't be surprised if it can be used also for this segment intersection problem.  For example

given four integer points representing two segments (a, b), (c, d).  Compute the four dot products below and constrain each result to its sign (+1, 0, -1).

s1 = (a, b) * (a, c)   // on what side of segment (a, b) is point c
s2 = (a, b) * (a, d)   // on what side of segment (a, b) is point d
s3 = (c, d) * (c, a)    // on what side of segment (c, d) is point a
s4 = (c, d) * (c, b)    // on what side of segment (c, d) is point b

Ignoring the colinear cases, I would speculate that the segments intersects if and only if s1 != s2 and s3 != s4.  If one or more of the si are zero, then 3 or 4 of the points are colinear and this requires a little bit more work.

Bottom line, stick with integers if you can ;-)

[Galenbo]

If it's 2D, 2 long lines always intercept (unless parallel). So I would:

Get 2 endpoints and calculate direction coefficient of each short line.

Do the comparison to see witch short lines are parallel
Do the (simple) math to get the list of coordinates where the long lines cross eachother

Filter the list, remove points from the list if they are not on the short line.

I think this must be the easyest/fastest way.

[T3sl4co1l]

My favorite function when I dealt with this stuff was the cross product. Given a segment (a, b) and a point c it tells you if c is on the right, left or collinear with the segment (a, b), all without any  division and with perfect accuracy if a, b, c coordinates are integers.  It can be used creatively and I wouldn't be surprised if it can be used also for this segment intersection problem.

Very likely it's in there somewhere.  My code calculates a lot more than just direction, so it goes through all the motions.  But if you run the algebra for just a few output variables, I bet you'd see something like that.

Tim

[amyk]

There are (somewhat more complex) algorithms that can do this more quickly than the naive methods, if there are many lines to check:
http://www.cs.ucsb.edu/~suri/cs235/Intersection.pdf
http://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf
http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm

(The material there is probably a bit too academic for your tastes... it's difficult reading but you can still mostly figure out what it's trying to say.)