I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Ray Casting

08.08.2012
| 4376 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Ray Casting Algorithm

A ray casting algorithm checks if a point is inside or outside a polygon.  It's called Ray Casting because the typical solution for such a problem is to to create a horizontal ray starting at the given point and checking if it intersects the side of the polygon. Check out the Wikipedia page for more details. 

Catch up on all our previous puzzlers here

Comments

Vijay Nathani replied on Fri, 2012/08/10 - 3:37am

The Groovy solution


@groovy.transform.Immutable class Point { double x, y; }
@groovy.transform.Immutable class LineSegment { 
	Point p1,p2; 
	def isHorizontal() { Math.abs(p1.y - p2.y) < 0.0001 }
	def isVertical() { Math.abs(p1.x - p2.x) < 0.0001 }
	def slopeM() { (p2.y - p1.y) / (p2.x - p1.x) }
	def interceptC() { p1.y - slopeM() * p1.x }
	def withinBounds(p) { (p1.x..p2.x).containsWithinBounds(p.x) && (p1.y..p2.y).containsWithinBounds(p.y) }
}
boolean isRayIntersecting(Point startOfRay, LineSegment ls) {
	if (ls.isHorizontal()) return false
	def intersectionX = ls.isVertical()?ls.p1.x:((startOfRay.y - ls.interceptC()) / ls.slopeM())
	intersectionX >= startOfRay.x && ls.withinBounds(new Point(intersectionX, startOfRay.y))
}
boolean isPointInside(point, polygonEndpoints) {
	((1..polygonEndpoints.size()).count { isRayIntersecting(point, new LineSegment(polygonEndpoints[it-1], polygonEndpoints[it % polygonEndpoints.size()])) }) % 2 
}
def endPointsOfPolygon = [ new Point(1,1), new Point(5,1), new Point(3,7) ]
println isPointInside(new Point(2,3), endPointsOfPolygon)  //prints true
println isPointInside(new Point(0,0), endPointsOfPolygon)  //prints false

Gervais Blaise replied on Fri, 2012/08/10 - 2:05am

Vijay Nathani replied on Fri, 2012/08/10 - 3:41am in response to: Gervais Blaise

java.awt.Polygon accepts only integers as endpoints of polygon. It is meant for a polygon drawn on the screen.

In  graph theory, the co-ordinates are float or double. So the existing Polygon.contains function may not be usable.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.