From: "Rainer Rosenthal" Subject: Re: Is the empty set a finite set? Date: Mon, 4 Sep 2000 21:36:27 +0200 To: "Dave Rusin" Summary: [missing] [deletia --djr] We had and still have a fine thread in de.sci.math regarding the question of Malte Lance "Test if 4 points ..." date 09-02-00. I managed to find out an elegant solution, based on "the right look". We now try to settle the theory, making the definitions rigorous. A very nice task - so simple at first sight, but with little intricacies. In Malte's problem he is confronted with sets of 4 points each, no ordering ! People often speak of quadri- laterals ("Viereck" in German) in the sense of A-B-C-D with given ordering of { A, B, C, D}. I'll check the web-sites for definitions. Could you give me a hint ? This may be a nice entrance to your enchanted "Atlas" ! Being proud of my finding, which I later will post as "Re" to Malte's thread here (after everything is cleared :-)), I just write it down: For two line segments a and b I use the following notation: a(x)b means "a and b intersect" a(=)b means "a and b don't intersect" Four points A, B, C, D in the plane make up a non-convex quadrilateral, iff AB(=)CD and AC(=)BD and AD(=)BC (*) The nice thing is, you don't have to talk about "interior" or "orientation" and there is no handwaving and "intuition". Just three conditions to test, which are about 10 lines of code, solving the corresponding linear equations. Thanks again and good night Rainer ------------------------------------------------------------------ When you are sincere, you don't have to ask. Do you ? ============================================================================== From: Dave Rusin Subject: Re: Is the empty set a finite set? Date: Mon, 4 Sep 2000 15:00:22 -0500 (CDT) To: r.rosenthal@ngi.de I responded by private email to the "4 points" person. The fastest answer I have seen before is: simply check whether any of the four points is in the convex hull of the other three, and to do that (four times), simply compute the areas of the triangles and see if the one which is supposed to be the outer triangle has an area equal to the sum of the three inner triangles. Numerically, this makes for a fairly robust algorithm because there is no division at all and we don't have to worry about degenerate cases (e.g. 3 collinear points). The nearest thing to a numerical problem is deciding whether or not (area1)=(area2)+(area3)+(area4), but in some sense that's not a problem: if the two numbers are so close that you cannot tell whether they are truly equal, then one of your points is very close to the triangle joining the other three. It makes perfect sense to flag those as being configurations of "indeterminate convexity" or whatever. dave ============================================================================== From: Malte Lance Subject: Re: 2.Try: Test, if 4 points build up a convex quadrilateral ? Date: Tue, 5 Sep 2000 11:56:41 +0200 (CEST) To: Dave Rusin On Mon, 4 Sep 2000, Dave Rusin wrote: > In article <8or3sc$j9n$13$1@news.t-online.com> you write: > >In article <8oqi2v$gg9$18$1@news.t-online.com>, > > malte.lance@gmx.net (Malte Lance) writes: > >> Hi, > >> > >> how can i test, if 4 arbitrarily chosen points in R^2 build up to a > >> convex quadrilateral under their convex hull, without refering > >> to 'orientation' nor 'oriented basis'. > > COmpute the areas of the triangles spanned by each set of three. If > say p1, p2, p3 are vertices of the largest of the four triangles, > check to see whether or not it's the sum of the other three areas, > p1 p2 p4, p1 p3 p4, and p2 p3 p4. If it is equal to the sum of > these three, then p4 is inside the triangle p1 p2 p3. Otherwise, > p4 is outside. Ok, that works. Thanks! Do you have an idea or a starting-point, how to prove the correctness ? Or maybe you have a pointer to a proofsketch or a reference. > dave Malte Lance.