Editing revision 7 of Trigonometry/Intersection

Robo Home | Changes | Preferences | AllPages

Editing old revision 7. Saving this page will replace the latest revision with this text.

For finding out where (if indeed) a line intersects a given shape [[Nano]] made us these functions:
<pre>
	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);
	}
</pre>
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:
<pre>
	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);
	}
</pre>
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]]

Summary:
Consciousness check: 11 - 3 =
This change is a minor edit. Send email notification that Trigonometry/Intersection has been changed.
(Visit Preferences to set your user name.)

View other revisions
Robo Home | Trigonometry | Changes | Preferences | AllPages