In this beautiful illustration I made with my vast graphical skills, there are 4 regions (rightly labeled) and a line that passes through 3 of them (regions 2-4).
What is the best way to check which regions the line pass through. Do I have to manually loop through the 4 regions to see if the line lies in its boundaries? Can I take the starting and end point of the line to see which regions it lies in? Is there example code? I’m a bit too tired to think logically.
Hello!
You can check out my topic: http://www.java-gaming.org/index.php/topic,24587.0.html
where pseudocode was given, and apply it to the lines ends. However, that doesn’t tell if it passes through any other regions.
I need to know all regions a line lies on, and it can be on infinitely many regions.
I am not sure if that is it or not
But I do know that a seperating axis theorem check of “Line vs AABB” will work if you just compare the line to a group of AABBs (Axis Aligned Bounded Boxes) as each region.
I can write a small little code for it come Monday thatll do exactly this. About to head out of town for weekend right now though.
edit:
Although I think their code might be in C# or C++ I Am sure you can hack it together to work in Java.
http://www.gamedev.net/topic/338987-aabb---line-segment-intersection-test/
Ahh well, I ended up doing it by myself (namrog I would still appreciate if you write your code so I can compare speeds).
Heres the code:
private static final void getRegionsOfLine(int x0, int y0, int x1, int y1, int regionXSize, int regionYSize) {
boolean steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);
if (steep) {
int tmp = x0;
x0 = y0;
y0 = tmp;
tmp = x1;
x1 = y1;
y1 = tmp;
}
if (x0 > x1) {
int tmp = x0;
x0 = x1;
x1 = tmp;
tmp = y0;
y0 = y1;
y1 = tmp;
}
int deltax = x1 - x0;
int deltay = Math.abs(y1 - y0);
int error = deltax / 2;
int ystep = -1;
int y = y0;
if (y0 < y1)
ystep = 1;
for (int x = x0; x <= x1; x++) {
int absX;
int absY;
if (steep) {
absX = y;
absY = x;
} else {
absX = x;
absY = y;
}
int regX = absX / regionXSize;
int regY = absY / regionYSize;
if (absX < 0)
regX--;
if (absY < 0)
regY--;
// Region is: (regX, regY)
int dX;
int dY;
if (steep) {
dX = regionYSize - (absY - (regionYSize * regY));
dY = absX - (regionXSize * regX);
} else {
dX = regionXSize - (absX - (regionXSize * regX));
dY = absY - (regionYSize * regY);
}
int ceil = x + dX;
for (; x < ceil; x++) {
error -= deltay;
if (error < 0) {
y += ystep;
error += deltax;
dY += ystep;
if (dY == -1 || dY == (steep ? regionXSize : regionYSize))
break;
}
}
}
}
EDIT: bug fixes
Are there any faster solutions?
Ill write something up this week sometime.
I officially just got kicked out of gf’s place and I can’t move into my new apartment for a few more days so I am officially the homeless bum on JGO right now 
:-\ Tough luck, man…
Aww sorry to hear that :’(
I want to share some words of wisdom, I recently picked up:
‘Experience is what you get when you did not get what you wanted’ -namrog84
Goodluck! :emo: and enjoy your hotel!
if you want, you can seek closure in the JGO vault.
haha thanks everyone. Great advice Riven 
sorry for hijacking the line logic thread counterp.
p.s. I slept in my car last night Yay for work computer!
counterp, I didn’t write these but compare speeds of these 2 methods. 1 is from the internals of the java’s rect2d
Line2D.Double line = new Line2D.Double(20,40,600,400); I chose this at random number
//should use a custom linetype to reduce casting for int
int rX=20; //how many X rect
int rY=20; //how many Y rect
int spacing=25; //you can separate this into xSpace and ySpace for non squares
public void render(Graphics g) {
g.drawLine((int)line.x1, (int)line.y1, (int)line.x2, (int)line.y2);
for(int i=0;i<rX;i++){
for(int j=0;j<rY;j++){
//if(SegmentIntersectRectangle(i*spacing,j*spacing,i*spacing+spacing,j*spacing+spacing,line.x1,line.y1,line.x2,line.y2)){
//other test to compare
if(intersectsLine(line.x1, line.y1, line.x2, line.y2,i*spacing, j*spacing, spacing, spacing)){
g.setColor(Color.red); //hit!
}else{
g.setColor(Color.white); //miss!
}
g.drawRect(i*spacing, j*spacing, spacing, spacing);
}
}
}
//could throw a few of the rectX/Y and sizes into constants of some kind to help improve efficiency a little of having to not redo multiplication.
first test
private static final int OUT_LEFT = 1;
private static final int OUT_TOP = 2;
private static final int OUT_RIGHT = 4;
private static final int OUT_BOTTOM = 8;
private static int outcode(double pX, double pY, double rectX, double rectY, double rectWidth, double rectHeight) {
int out = 0;
if (rectWidth <= 0) {
out |= OUT_LEFT | OUT_RIGHT;
} else if (pX < rectX) {
out |= OUT_LEFT;
} else if (pX > rectX + rectWidth) {
out |= OUT_RIGHT;
}
if (rectHeight <= 0) {
out |= OUT_TOP | OUT_BOTTOM;
} else if (pY < rectY) {
out |= OUT_TOP;
} else if (pY > rectY + rectHeight) {
out |= OUT_BOTTOM;
}
return out;
}
public static boolean intersectsLine(double lineX1, double lineY1, double lineX2, double lineY2, double rectX, double rectY, double rectWidth, double rectHeight) {
int out1, out2;
if ((out2 = outcode(lineX2, lineY2, rectX, rectY, rectWidth, rectHeight)) == 0) {
return true;
}
while ((out1 = outcode(lineX1, lineY1, rectX, rectY, rectWidth, rectHeight)) != 0) {
if ((out1 & out2) != 0) {
return false;
}
if ((out1 & (OUT_LEFT | OUT_RIGHT)) != 0) {
double x = rectX;
if ((out1 & OUT_RIGHT) != 0) {
x += rectWidth;
}
lineY1 = lineY1 + (x - lineX1) * (lineY2 - lineY1) / (lineX2 - lineX1);
lineX1 = x;
} else {
double y = rectY;
if ((out1 & OUT_BOTTOM) != 0) {
y += rectHeight;
}
lineX1 = lineX1 + (y - lineY1) * (lineX2 - lineX1) / (lineY2 - lineY1);
lineY1 = y;
}
}
return true;
}
2nd test
boolean SegmentIntersectRectangle(double a_rectangleMinX,
double a_rectangleMinY, double a_rectangleMaxX,
double a_rectangleMaxY, double a_p1x, double a_p1y, double a_p2x,
double a_p2y) {
// Find min and max X for the segment
double minX = a_p1x;
double maxX = a_p2x;
if (a_p1x > a_p2x) {
minX = a_p2x;
maxX = a_p1x;
}
// Find the intersection of the segment's and rectangle's x-projections
if (maxX > a_rectangleMaxX) {
maxX = a_rectangleMaxX;
}
if (minX < a_rectangleMinX) {
minX = a_rectangleMinX;
}
if (minX > maxX) // If their projections do not intersect return false
{
return false;
}
// Find corresponding min and max Y for min and max X we found before
double minY = a_p1y;
double maxY = a_p2y;
double dx = a_p2x - a_p1x;
if (Math.abs(dx) > 0.0000001) {
double a = (a_p2y - a_p1y) / dx;
double b = a_p1y - a * a_p1x;
minY = a * minX + b;
maxY = a * maxX + b;
}
if (minY > maxY) {
double tmp = maxY;
maxY = minY;
minY = tmp;
}
// Find the intersection of the segment's and rectangle's y-projections
if (maxY > a_rectangleMaxY) {
maxY = a_rectangleMaxY;
}
if (minY < a_rectangleMinY) {
minY = a_rectangleMinY;
}
if (minY > maxY) // If Y-projections do not intersect return false
{
return false;
}
return true;
}
edit:
I still can see a custom solution in my head that I feel like is way quicker and like 5 lines tops. Itd use
double m=(line.y1-line.y2)/(line.x1-line.x2);
double b = m*line.x1-line.y1;
then a return function with 4 or 8 &&|| sets of ?<x<?
I also could imagine another one, that doesn’t need to blunt force your way through ALL the rectangles(as clearly some have 0 chance of ever being in it, but by using the slope calculation, directly hit numbers in simple boolean grid[][]; So you wouldnt need a nested for loop(this should be the fastest) for detection? but a direct grid[pointY/rectHeight] = HIT;
Ahh well, I don’t think bruteforcing will work well, I tested yours and it’s rather slow with small lines and large lines alike.
this will explode if x1==x2
it’s on the tip of my mind (lol) but I KNOW that some important optimizations can be done to mine to avoid the second loop.
I suppose you’d need a special case for vertical/horizontal lines
easiest way would probably just nudge the line slightly non vertical anytime it equals vertical.
otherwise special case code 
I assume your regions are laid out in a regular grid, so you can calculate the start and end cell like:
int col0 = (int) ((float)x0/regionWidth);
int row0 = (int) ((float)y0/regionHeigth);
int col1 = (int) ((float)x1/regionWidth);
int row1 = (int) ((float)y1/regionHeigth);
line equation is
y=m*x+b
=>
x=(y-b)/m
with x0/y0, x1/y1 you can solve this to
m=(y0-y1)/(x0-x1)
b=y0-m*x0
now everything you have to do is to sample from col0/row0 to col1/row1 with regionWidth or regionHeight stepping (depending on |m|<>1)
int col0 = (int) ((float)x0/regionWidth);
int row0 = (int) ((float)y0/regionHeigth);
int col1 = (int) ((float)x1/regionWidth);
int row1 = (int) ((float)y1/regionHeigth);
float m=(float)(y0-y1)/(x0-x1)
float b=y0-m*x0
// a "steep" line
if(Math.abs(m)>1)
{
// does it go up or down?
int dir=(y0<y1)1:-1;
for(int row=row0; row!=row1; row+=dir)
{
float y= row*regionHeight;
float x= (y-b)/m;
int col = (int) (x/regionWidth);
// TODO store row and col somewhere
}
}
// a "flat" line
else
{
// does it go right or left?
int dir=(x0<x1)1:-1;
for(int col=col0; col!=col1; col+=dir)
{
float x= col*regionWidth;
float y=m*x+b;
int row = (int) (y/regionHeight);
// TODO store row and col somewhere
}
}
Haven’t tested it, but should work
perrrrrrrfect-o
although it’s a shame that you aren’t as gifted in italian cuisine as I am
EDIT: ahh well yours doesn’t fill all the required squares
You can visualize it with this (contains both of our methods side by side, mine seems to be a bit inaccurate :\ )
import java.awt.Canvas;
import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
import javax.swing.JFrame;
import javax.swing.WindowConstants;
public class Main {
private static final int REGION_X = 25;
private static final int REGION_Y = 25;
private static int alternate = 0;
public static void main(String[] args) {
JFrame frame = new JFrame("Line Test");
frame.setVisible(true);
final int w = 1000;
final int h = 500;
frame.setSize(w, h);
frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
Canvas canvas = new Canvas() {
@Override
public void paint(Graphics g) {
g.setFont(new Font("Times New Roman", Font.PLAIN, 9));
int fH = g.getFontMetrics().getHeight();
for (int x = 0; x < w / REGION_X / 2; x++) {
for (int y = 0; y < h / REGION_Y; y++) {
if (x % 2 == 0)
if (y % 2 == 1)
g.setColor(Color.red);
else
g.setColor(Color.black);
else
if (y % 2 == 0)
g.setColor(Color.red);
else
g.setColor(Color.black);
g.fillRect(x * REGION_X, y * REGION_Y, REGION_X, REGION_Y);
g.setColor(g.getColor() == Color.black ? Color.red : Color.black);
g.drawString(x + ", " + y, x * REGION_X + 2, y * REGION_Y + fH);
}
}
line(50, 50, 400, 300, REGION_X, REGION_Y, g);
g.setColor(Color.white);
g.fillRect(w / 2 - 1, 0, 2, h);
for (int x = w / REGION_X / 2; x < w / REGION_X; x++) {
for (int y = 0; y < h / REGION_Y; y++) {
if (x % 2 == 0)
if (y % 2 == 1)
g.setColor(Color.red);
else
g.setColor(Color.black);
else
if (y % 2 == 0)
g.setColor(Color.red);
else
g.setColor(Color.black);
g.fillRect(x * REGION_X, y * REGION_Y, REGION_X, REGION_Y);
g.setColor(g.getColor() == Color.black ? Color.red : Color.black);
g.drawString(x + ", " + y, x * REGION_X + 2, y * REGION_Y + fH);
}
}
line2(50 + w / 2, 50, 400 + w / 2, 300, REGION_X, REGION_Y, g);
}
};
canvas.setSize(frame.getSize());
frame.add(canvas);
}
private static final void line(int x0, int y0, int x1, int y1, int regionWidth, int regionHeight, Graphics g) {
int col0 = (int) ((float)x0/regionWidth);
int row0 = (int) ((float)y0/regionHeight);
int col1 = (int) ((float)x1/regionWidth);
int row1 = (int) ((float)y1/regionHeight);
float m=(float)(y0-y1)/(x0-x1);
float b=y0-m*x0;
// a "steep" line
if(Math.abs(m)>1)
{
// does it go up or down?
int dir=(y0<y1)?1:-1;
for(int row=row0; row!=row1; row+=dir)
{
float y= row*regionHeight;
float x= (y-b)/m;
int col = (int) (x/regionWidth);
g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
g.fillRect(col * REGION_X, row * REGION_Y, REGION_X, REGION_Y);
}
}
// a "flat" line
else
{
// does it go right or left?
int dir=(x0<x1)?1:-1;
for(int col=col0; col!=col1; col+=dir)
{
float x= col*regionWidth;
float y=m*x+b;
int row = (int) (y/regionHeight);
g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
g.fillRect(col * REGION_X, row * REGION_Y, REGION_X, REGION_Y);
}
}
g.setColor(Color.pink);
g.drawLine(x0, y0, x1, y1);
}
private static final void line2(int x0, int y0, int x1, int y1, int regionXSize, int regionYSize, Graphics g) {
boolean steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);
if (steep) {
int tmp = x0;
x0 = y0;
y0 = tmp;
tmp = x1;
x1 = y1;
y1 = tmp;
}
if (x0 > x1) {
int tmp = x0;
x0 = x1;
x1 = tmp;
tmp = y0;
y0 = y1;
y1 = tmp;
}
int deltax = x1 - x0;
int deltay = Math.abs(y1 - y0);
int error = deltax / 2;
int ystep = -1;
int y = y0;
if (y0 < y1)
ystep = 1;
for (int x = x0; x <= x1; x++) {
int absX;
int absY;
if (steep) {
absX = y;
absY = x;
} else {
absX = x;
absY = y;
}
int regX = absX / regionXSize;
int regY = absY / regionYSize;
if (absX < 0)
regX--;
if (absY < 0)
regY--;
g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
g.fillRect(regX * REGION_X, regY * REGION_Y, REGION_X, REGION_Y);
int dX;
int dY;
if (steep) {
dX = regionYSize - (absY - (regionYSize * regY));
dY = absX - (regionXSize * regX);
} else {
dX = regionXSize - (absX - (regionXSize * regX));
dY = absY - (regionYSize * regY);
}
int ceil = x + dX;
for (; x < ceil; x++) {
error -= deltay;
if (error < 0) {
y += ystep;
error += deltax;
dY += ystep;
if (dY < 0 || dY > (steep ? regionXSize : regionYSize))
break;
}
}
}
g.setColor(Color.pink);
g.drawLine(x0, y0, x1, y1);
}
}
EDIT: modified the code to make it easier to spot differences
EDIT2: OK one last modification to show coordinates
The missing squares of my implementation are due to only sampling when entering a col/row. To match all the squares the code has to be modified to also sample when leaving the col/row. This then can be optimized to only being done when the sampled row/col differs from the last one. Maybe I’ll find some time this eve.
Here’s the accurate version:
private static final void line(int x0, int y0, int x1, int y1, int cellWidth, int cellHeight, Graphics g)
{
// flag to get back the old slightly faster but inaccurate version
boolean skipMissedCells=false;
int alternate = 0;
int col0 = (int) ((float)x0/cellWidth);
int row0 = (int) ((float)y0/cellHeight);
int col1 = (int) ((float)x1/cellWidth);
int row1 = (int) ((float)y1/cellHeight);
// fill start and end cell
g.setColor(new Color(0, 127,127));
g.fillRect(col0 * cellWidth, row0 * cellHeight, cellWidth, cellHeight);
g.fillRect(col1 * cellWidth, row1 * cellHeight, cellWidth, cellHeight);
float m=(float)(y0-y1)/(x0-x1);
float b=y0-m*x0;
// a "steep" line
if(Math.abs(m)>1)
{
int lastCol=col0;
// does it go up or down?
int dir=(y0<y1)?1:-1;
for(int row=row0+dir; row!=row1; row+=dir)
{
float y= row*cellHeight;
float x= (y-b)/m;
int col = (int) (x/cellWidth);
g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
g.fillRect(col * cellWidth, row * cellHeight, cellWidth, cellHeight);
// when the sampled column changes, there might be another missed cell
if(!skipMissedCells && col!=lastCol)
{
// sample again - slightly before the row boundary
y= row*cellHeight-1;
x= (y-b)/m;
int missedCol = (int) (x/cellWidth);
// really missed that one?
if(lastCol!=missedCol)
{
g.setColor(new Color(127,127, 0));
// must be (row-dir), since the missed cell belongs to the last sampled row
g.fillRect(missedCol * cellWidth, (row-dir) * cellHeight, cellWidth, cellHeight);
}
lastCol=col;
}
}
}
// a "flat" line
else
{
int lastRow=row0;
// does it go right or left?
int dir=(x0<x1)?1:-1;
for(int col=col0+dir; col!=col1; col+=dir)
{
float x = col*cellWidth;
float y = m*x+b;
int row = (int) (y/cellHeight);
g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
g.fillRect(col * cellWidth, row * cellHeight, cellWidth, cellHeight);
// when the sampled column changes, there might be another missed cell
if(!skipMissedCells && row!=lastRow)
{
// sample again - slightly before the column boundary
x = col*cellWidth-1;
y = m*x+b;
int missedRow = (int) (y/cellHeight);
// really missed that one?
if(lastRow!=missedRow)
{
g.setColor(new Color(127,127, 0));
// must be (col-dir), since the missed cell belongs to the last sampled column
g.fillRect((col-dir) * cellWidth, missedRow * cellHeight, cellWidth, cellHeight);
}
lastRow=row;
}
}
}
g.setColor(Color.pink);
g.drawLine(x0, y0, x1, y1);
}