One of the most common tasks you will find in geometry problems is line intersection. Despite the fact that it is so common, a lot of coders still have trouble with it. The first question is, what form are we given our lines in, and what form would we like them in? Ideally, each of our lines will be in the form Ax+By=C, where A, B and C are the numbers which define the line. However, we are rarely given lines in this format, but we can easily generate such an equation from two points. Say we are given two different points, (x1, y1) and (x2, y2), and want to find A, B and C for the equation above. We can do so by setting
A = y2-y1
B = x1-x2
C = A*x1+B*y1
Regardless of how the lines are specified, you should be able to generate two different points along the line, and then generate A, B and C. Now, lets say that you have lines, given by the equations:
A1x + B1y = C1
A2x + B2y = C2
To find the point at which the two lines intersect, we simply need to solve the two equations for the two unknowns, x and y.
double det = A1*B2 - A2*B1
if(det == 0){
//Lines are parallel
}else{
double x = (B2*C1 - B1*C2)/det
double y = (A1*C2 - A2*C1)/det
}
To see where this comes from, consider multiplying the top equation by B2, and the bottom equation by B1. This gives you
A1B2x + B1B2y = B2C1
A2B1x + B1B2y = B1C2
Now, subtract the bottom equation from the top equation to get
A1B2x - A2B1x = B2C1 - B1C2
Finally, divide both sides by A1B2 - A2B1, and you get the equation for x. The equation for y can be derived similarly.
This gives you the location of the intersection of two lines, but what if you have line segments, not lines. In this case, you need to make sure that the point you found is on both of the line segments. If your line segment goes from (x1,y1) to (x2,y2), then to check if (x,y) is on that segment, you just need to check that min(x1,x2) ≤ x ≤ max(x1,x2), and do the same thing for y. You must be careful about double precision issues though. If your point is right on the edge of the segment, or if the segment is horizontal or vertical, a simple comparison might be problematic. In these cases, you can either do your comparisons with some tolerance, or else use a fraction class.
Name:
Anonymous2009-12-26 11:34
>>2
I don't care whether you're copy pasting that or what, but this is as good as any thread.
I have two lists. I have a list of unique points, then another list where every every entry refers to a point from the other list. This second list is an indexed mapping and composes the points into a shape (may be a polygon, may be a polygon with internal segments). I have been having a difficult time producing an efficient algorithm that finds where those internal segments can be "cut" along to produce two or more smaller polygons. Essentially: take a square composed of four line segments, draw a line segment from one vertex to the opposite diagonal vertex, then separate it all into two equilateral triangles.
I have a segment intersection-separation algorithm; an algorithm that trims segments with only one connected end; and an algorithm that determines whether at least one polygon is produced through the mapped list. It's not that I CAN'T produce an algorithm that does what I want in some respect, but that I can't produce an algorithm that works consistently with all possible segment connections.
An example of one failed case has output as one of the smaller polygons and an outline of the whole shape. Even if I can prove that the outputs overlap, I can not move beyond this point.
Name:
Anonymous2009-12-26 11:38
I HATE women. I never had a girlfriend and never will. The only times I got laid was when I paid a woman or promised her something. I'm never going to hold hands with a chick, kiss a girl intimately because we're in love, or any of the other shit that human beings were made to do. I guess that I'm suppose to be happy masturbating every fucking night. I'm a man with sexual urges and can't get with a female. I'm suppose to be alright with that? THERE IS A FUCKING CURSE ON MY LIFE. A CURSE THAT PREVENTS ANY FEMALE FROM LIKING ME. Oh I forgot, I do get interest from fat chicks and I'm not attracted to fat chicks.
I don't give a fuck anymore. I'm going to become the biggest asshole in the world. I tried the whole being considerate thing and it got me nowhere. If people can't handle my newfound harshness, then bring it on. BECAUSE I DON'T GIVE A FUCK. I DON'T GIVE A FUCK. I DON'T GIVE A FUCK.
I get happy when I hear about some college slut getting murdered or injured in a hit and run. "oh she was a beautiful and talented girl, how could this happen." I don't know but I'm glad it did.