1
$\begingroup$

my question is simple: I have four lines (given by $Ax + By + C = 0$ equation) $l[0]$, $l[1]$, $l[2]$, $l[3]$. There are maximum of $6$ intersection points. How to find four points out of these that form convex quadrilaterals?

$\endgroup$
0
$\begingroup$

You're not guaranteed a convex quadrilateral, in general. If you want a systematic way to find the four intersection, given that your four lines do form a convex quadrilateral, you can sort intersections by their position relative to the others.

Pick 2 random lines, and focus on their intersection point. Along each line, there should be 2 other intersections; keep these in mind. For a line intersection to be the vertex of a convex quadrilateral, it must be the middle point on one of the two lines which form the intersection. Numerically, this can be found by examining the signs of the displacement vectors between the central intersection point and the other colinear points.

You just have to repeat until you find the 4 vertices.

EDIT: In general, there will be 1 vertex which is not a middle-point. This point has the extra property that it is not co-linear with the other 3 middle-point-vertices. Use this criterion to find the fourth vertex.

$\endgroup$
  • $\begingroup$ 'For a line intersection to be the vertex of a convex quadrilateral, it must be the middle point on one of the two lines which form the intersection.' I think I do not understand this. First: Why? Second: If I understand this correctly (A point is a vertex of a convex quadrilateral if and only if it is between two other points from the same line) I cannot see why this is true $\endgroup$ – user2874894 Dec 22 '14 at 22:40
  • $\begingroup$ If you draw a picture of a convex quadrilateral, this should become apparent. Make sure you show every intersection, even the 2 that aren't vertices. $\endgroup$ – Benjamin Roycraft Dec 22 '14 at 22:44
  • $\begingroup$ This is not true. I have an example with 3 of the four vertexes of the quadrilateral in between the other points on their lines and one that is not. $\endgroup$ – user2874894 Dec 22 '14 at 22:51
  • $\begingroup$ Could you post a picture of your example? $\endgroup$ – Benjamin Roycraft Dec 22 '14 at 22:53
  • $\begingroup$ Currently I cannot, but I will be able tommorow. If intersect the first three line and name their intersection points A, B, C and then intersect the triangle with the last line like the link The quadrilateral is ABDE, but A is not in between any of the two lines it belongs. $\endgroup$ – user2874894 Dec 22 '14 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.