[Home]Trigonometry/Intersection

Robo Home | Trigonometry | Changes | Preferences | AllPages

Showing revision 7
For finding out where (if indeed) a line intersects a given shape Nano made us these functions:
	private static final int TRACE_DEPTH = 16;
	
	public Point2D findIntersection(Line2D line, Shape shape) {
		return findIntersection(line, shape, 0);
	}
	
	private Point2D findIntersection(Line2D line, Shape shape, int depth) {
		Point2D middle = new Point2D.Double((line.getX1() + line.getX2()) / 2, (line.getY1() + line.getY2()) / 2);
		Point2D temp;
		
		if (shape.contains(line.getP1()) == shape.contains(line.getP2()))
			return null;
		
		if (depth >= TRACE_DEPTH)
			return middle;
		
		temp = findIntersection(new Line2D.Double(line.getP1(), middle), shape, depth + 1);
		
		if (temp != null)
			return temp;
		else
			return findIntersection(new Line2D.Double(middle, line.getP2()), shape, depth + 1);
	}
This is completely untested, but at least you will probably be able to fix it where it is broken. It should provide reasonable accuracy, though with a high computational cost, as it is merely a binary search. It should recurse 0 times if the line lies entirely inside or outside the shape, and should recurse between TRACE_DEPTH and 2 * TRACE_DEPTH times otherwise, with an average of 1.5 * TRACE_DEPTH (that is, 3 * TRACE_DEPTH calls to contains()). -- nano
In my computer graphics class, we actually discussed an algorithm like nano's for line clipping. Of course, it can just as easily be done iteratively. -- Kawigi

So true, and the iterative version can use half of the calls to Shape.contains(). It should be quite a bit faster:

	private static final int TRACE_DEPTH = 16;
	
	public Point2D findIntersection(Line2D line, Shape shape) {
		Point2D middle;
		boolean containsFirst;
		
		if ((containsFirst = shape.contains(line.getP1())) == shape.contains(line.getP2()))
			return null;
		
		for (int i = 0; i < TRACE_DEPTH; i++) {
			middle = new Point2D.Double((line.getX1() + line.getX2()) / 2, (line.getY1() + line.getY2()) / 2);

			if (containsFirst != shape.contains(middle))
				line = new Line2D.Double(line.getP1(), middle);
			else
				line = new Line2D.Double(middle, line.getP2());
		}
		
		return new Point2D.Double((line.getX1() + line.getX2()) / 2, (line.getY1() + line.getY2()) / 2);
	}
Again, it's untested. The best I can say is that I read through it quickly after I finished it and it seems to be all there. :) -- nano

I edited it again to change the "else if" into an "else", as the second test was unnecessary. If the whole line intersects the shape, than either one half of it or the other intersects. This again decreases the number of Shape.contains() calls necessary. I also simplified the code by removing a lot of unnecessary boolean saving. -- nano

That looks much nicer. :-) Would it be better of worse to decided when to stop by checking if the guessed intersection and the previously guessed intersection are within a certain distance of eachother? It would stop needless extra iterations, and could still be stopped after TRACE_DEPTH iterations, although it would mean an extra variable, and a call to distance() for each iteration. -- Tango

Yes, I thought of that, but decided it wasn't really worth it. This version has an accuracy that is 1/65536th the length of the line. That's fairly accurate. :) --nano


Robo Home | Trigonometry | Changes | Preferences | AllPages
Edit revision 7 of this page | View other revisions | View current revision
Edited December 24, 2003 19:44 EST by Nano (diff)
Search: