JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - New Recipes Working with Lines and Segments
 Working with Lines and Segments | Reply
 Re: Working with Lines and Segments (response to post by Radheya) | Reply
 Re: Working with Lines and Segments (response to post by Radheya) | Reply The recipe was a bit long, but covers a lot of important topics. If it needs to be reduced just post it.
 Re: Working with Lines and Segments (response to post by Radheya) | Reply This recipe is a tricky one to comment, especially without "Using Vector Operations" written yet. The overall impression is: we need to shorten this by removing unnecessary theory and add "Discussion" with examples of using this recipe.More detailed comments (yes, quite a lot of them):1. Cookbooks don't use numbered lists within one recipe, only "Problem-Solution-Discussion" format.2. We don't need definitions of line and segment in introduction, we assume that they are intuitive/already known. I think "Problem" should say something like "Now that we are comfortable with using vector operations for doing simple geometry things, let's see how they work for next popular group of problems - problems which deal with lines and segments on the plane". Then you can remove references to R^n from "Solution", since we've already stated that it's R^2.3. I don't think we need the proof of finding A,B and C from P and Q, just give the formulas (by the way, currently you've got at least one typo in them).4. When you're dealing with two lines, it's better to use (A1,B1,C1) and (A2,B2,C2), this doesn't require an effort to recall what E or F was.5. Finding a line which is perpendicular to a given one and comparing/ordering lines looks like they are not exactly popular topics and thus belong to "Discussion".6. Point-line distance is an important topic, so it does need implementation code (as well as the later one point-segment). I like the way it was given in http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1 .7. As for segments, I somewhat dislike using the term "collinear points", as it might not be a standard definition of all educational systems (as a matter of fact, it's the first time I've heard it). I'd prefer a generalized problem of determining whether the point belongs to the segment, with one solution as a whole.8. All examples should be TC problems. We've had enough geometry to be able to choose :-)
 Re: Working with Lines and Segments (response to post by Nickolas) | Reply
 Re: Working with Lines and Segments (response to post by Nickolas) | Reply A*x+B*y+C=0 is the worst line equation I know. From my experience all the things with lines are done perfectly with dot product: (x; y) and cross product [x; y]. Norm is |x| = sqrt( (x; x) );Here are the most common line equations I use:1. (P - A; N) = 0Here N is normal to line and A is any point on the line. P= is the variable point.2. [P - A; B - A] = 0Perhaps the most useful equation because here A and B are any two distinct points on the line.3. P(t) = A + (B-A)*t parametric equationExtremely useful when segments/rays are involved because the domain of t regulate the behavior of borders.Now some other nice routines:1. Oriented distance between point P and line is (P - A; N) / |N|. You can also use any other line equation easily here.2. The point P lies on the segment A -- B if: [P - A; B - A] = 0 and (P - A; B - A) >= 0 and (P - B; A - B) >= 03. To intersect two lines/rays/segments A--B and C--D you do the following:D = [B - A, D - C];Du = [C - A, D - C];Dv = [C - A, B - A];Then u = Du/D and v = Dv/D are parameters of intersection point for both lines.Here you can place additional requirements on the parameters. For example, if you intersect two segments, you place requirement that u>=0 and u<=1 and v>=0 and v<=1. If you intersect the rays, then you write only the condition that u>=0 and v>=0.After doing the checks you get the point from the parametric equation:P = A + (B-A)*u
 Forums TopCoder Cookbook Algorithm Competitions - New Recipes Working with Lines and Segments Previous Thread  |  Next Thread