Java - Detect Straight Lines with given Coordinates

Question

ADDED INFO:

I'm using the inside of a square as an arena. On start up, the square spawns in a random position, and rotation, and I can't access any of the squares attributes.

I then have a moving object inside the square, that I'm building AI for, and I want the object to 'learn' where the arena walls are. Every time the object bumps into a wall, I get a touch return, so I know if its hit or not. I'm using this to map the global position of where the object hit the wall and save it ... After 3 hits on the same wall, I want to mathematically 'draw a straight line' down those dots which will represent the arena walls - with this, I can tell my object not to go near these coordinates.

The reason for 3 dots? Well, if the object hit one side of a wall, then was to hit another side of a wall, I will have a line drawn from one side to another, giving false data about where the wall is.

If Java sees three (or more) dots inline, it knows that the object has hit the same wall (either being further up or so).

CONTINUED:

I'm trying to map out lines with given coordinate data. Basically I have an array that holds X and Y coordinates, and I want to be able to mathematically detect if it's they make up a straight line (give or take a few pixels). (The coordinate are a boarder of a square)

For example, the array might be like this:

[x0][y0] - 1,1

[x1][y1] - 2,2

[x2][y2] - 5,5

Which will present a diagonal line of on side of the square, like so:

But sometimes I might get one coordinate of one side of the square, and then another side, all mixed up (and not necessarily on a 90 degree angle either!). So I want to be able to run through the array, and detect what coordinates make a line (or the boarder side of the square), like so:

So right now, I have a 2D array:

private double wallLocations[][] = new double[10][10];

and a while loop that doesn't do the job. I don't really know where to even start with this one:

for(int r = 0; r < wallIndex; r++){
            for(int c = 0; c < wallIndex; c++){

                int index = 0;
                if(wallLocations[r][index] == wallLocations[r][c] && wallLocations[r][index + 1] == wallLocations[r][c] &&
                        wallLocations[r][index + 2] == wallLocations[r][c]){

                    System.out.println("***** Wall Here! *****");
                    index++;
                }

            }
        }

---- UPDATE ----

Heres a better example in what I'm looking for. The red dots represent the coordinates coming in, a line is detected when 3 or more dots line up (if it was 2 dots, then it would detect any and ever dot) ... You notice that this is starting to look like the boarder of a square?

Answer 1

This seems to essentially be a clustering problem, and those can be generally pretty hard. Part of a reason clustering is hard is that there may be more than one applicable mapping.

For instance (please forgive my bad ascii art):

 X   X   X  

   X   X   X

 X   X   X   X   

could be mapped

 X---X---X          X   X   X 
                     \ / \ / \ 
   X---X---X   or     X   X   X
                     / \ / \   \
 X---X---X---X      X   X   X   X 

I've seen uses of the Expectation Maximization algorithm using mixed Gaussian models used for this kind of thing (when there were a lot of points but only a few expected lines) but you generally do have to give that algorithm a definite number of clusters, and while its results are good, it's a pretty slow algorithm requiring possibly many iterations. I'm kinda thinking I've seen something generally faster that's some sort of image processing algorithm but I'd have to do some research.

I'm kinda wondering about something where you find y=mx+b for every pair of points and them sort them over m and b. It might be advantageous to find the angle θ in [0,pi) for each pair instead and sort over the angles instead of m, or maybe beter cluster by cos(2θ)-- the point of that being that the group of lines {y= -0.0001x + 1, y =1, and y=0.0001x + 1} are very similar, the group of lines {y= -10000x + 10, x = 0, and y=10000x - 10} are also very similar, but cos(2θ) should put them as far apart as possible, as any two pairs between each group should be nearly perpendicular.

Also note, in my example, b doesn't matter much for the lines nearly perpendicular to the x axis, so "b" might not be so useful for direct clustering.

I guess, perhaps, there may be some utilizable measure of "distance" between two lines, I'm just not sure what it would be. Two lines that are nearly parallel that converge "on screen" (where the points generally are) might ought to be considered "closer" than if they converge a trillion units a way from the screen--or should they? Purely speaking, three lines can never pairwise be considered closer to one another if none of them are parallel (If they're on a plane, they'll all meet somewhere), but intuitively, if we have two lines that are generally one inch apart in the area we're concerned with, we'd pick that pair as closer over two identically pointed lines that are a mile apart in the area of concern. That makes me think maybe the area between the lines,as bound by our area* ought to be used as a metric.

Sorry, I'm not sure how useful all that brainstorming might be, but it might put a different light on things.

Edit: You know what, a better answer might possibly be found by researching this:

http://en.wikipedia.org/wiki/Hough_transform

Edit II & III:

Ok,... the situation you've just described is a lot simpler and less generic (although, to be honest, I think I misread your initial query to be more generic than it really was).

You've got 4 candidate walls. Let your AI bounce around until it finds three co-linear points. That should be a simple test of combinations. Assign those three points a wall. Depending upon what other points you have, you actually might be able to determine or at least estimate the other three walls (assuming it is a square). If you have 5 points with 3 on separate walls, you should be able to calculate the distance between walls, and therefore the likely position of the 4th wall. To test if the other two points are on separate walls, make sure they're pair-wise not co-linear with a line perpendicular or parallel to the line defined by your wall, or if they are on a line parallel, test to see if the distance between them is less than the distance between the wall and them (if that's the case, they're on the wall opposite of the first candidate wall). Given that they are on separate walls, either one is facing the first found wall, or they're on walls perpendicular to that wall. Either way you can find the lines defining the walls with a little tricky geometry.

(and actually, to determine the dimensions, I don't think you need to even test to see that you have 3 co-linear points... I think you just need to test to see that you've made two turns... which takes 4 points minimum but likely more if you're unlucky. two of the points would have to be determinable to be on a different wall from the other two, which means really big bounces!)

There's a bit of math involved, and I'm a bit too tired to explain further tonight, and I don't know how much of the geometry of points around a square you want to take advantage of, because you wouldn't be able to use those properties in a more general case, so I'll leave it at that, and maybe also remove some of my other previous brainstorm cruft later.