Given a set of lines intersecting the quadrant with $x, y>0$, what are the available algorithms for finding the area below all straight lines (including $y$ and $x$ axis)? In other words, methods to find the points of the polygon given be the intersections of the lines?
Finding the intersections of straight lines
2
$\begingroup$
geometry
algorithms
computational-geometry
-
0set equal this lines each other,did i guess correctly what did you mean? – 2012-03-24
-
0I'm looking for algorithms to solve this problem in the most efficient way.. – 2012-03-24
-
1are you trying to find the area bounded by a set of lines and the x and y axes? by x,y > 0 do you mean that the x and y intercept of all lines in the set are positive? – 2012-03-24
-
0The question is very confusingly written. I think you are interested in the area of a polygon given in the form $Ax\le b$, $x\ge 0$, which you can do with fast convex hull algorithms. – 2012-03-24
1 Answers
1
If I understand the question, you can compute the polygon you are interested in by dualizing, computing the convex hull, and then going back. This is pretty standard course material, e.g., http://www.cs.umd.edu/class/spring2012/cmsc754/Lects/lect08.pdf
-
0Can the Graham's algorithm (http://en.wikipedia.org/wiki/Graham_scan) be extended to the case when points are added or removed? – 2012-03-27
-
0This seems like a different question that might be more appropriate for cs.SE. – 2012-03-28