tag:blogger.com,1999:blog-8152247234598992686.post33880210096363411..comments2017-03-18T10:57:27.417-07:00Comments on Totologic: Accurate point in triangle testLogichttp://www.blogger.com/profile/10024617997824703986noreply@blogger.comBlogger30125tag:blogger.com,1999:blog-8152247234598992686.post-34981296615419827192017-01-15T03:30:43.398-08:002017-01-15T03:30:43.398-08:00Hi.
You must "translate" my AS3 code in...Hi.<br /><br />You must "translate" my AS3 code into IDL code.<br /><br />It is not difficult because my code only use basic features (variable, function, if-else structure) and a few maths being common in all programming languages.<br /><br />At this point I have never worked with IDL so I can't help you more.Logichttp://www.blogger.com/profile/10024617997824703986noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-26951142527882089802017-01-13T21:14:53.857-08:002017-01-13T21:14:53.857-08:00Hi! Your article is very helpful. I am a beginner ...Hi! Your article is very helpful. I am a beginner and I would like to know how to use these codes using IDL (Interactive Data Language). Thank you and more power. Khate Bayerhttp://www.blogger.com/profile/02662182394149683960noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-47844688667774700652016-11-16T03:53:04.053-08:002016-11-16T03:53:04.053-08:00Thanks for you reply!Thanks for you reply!David Frogernoreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-88566685240408258892016-11-05T09:50:20.016-07:002016-11-05T09:50:20.016-07:00Well, for N<7 its not too bad, but the Delaunay...Well, for N<7 its not too bad, but the Delaunay procedure is certainly worth looking into. Can "CM" of the polygon, X=(sum Xi, i=1..N)/N, play a useful role in sorting vertices?Bob Terryhttp://www.blogger.com/profile/07137578798614253121noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-51412245812533673712016-11-05T05:54:38.801-07:002016-11-05T05:54:38.801-07:00Take care how you build your list of triangles. Co...Take care how you build your list of triangles. Considering ALL possible triangles made from the vertices list is not efficient. On the other hand, trying to optimize your triangles list, you could miss one or several.<br /><br />You should consider to build a Delaunay triangulation from your n-vertices polygon.<br /><br />Or check for algorithms directly dedicated to n-sides polygons.Logichttp://www.blogger.com/profile/10024617997824703986noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-72922427687502985752016-11-05T05:45:47.585-07:002016-11-05T05:45:47.585-07:00Winding number method is a powerful method for n-s...Winding number method is a powerful method for n-sides polygons. But applied and optimized to 3 sides polygons, it is equivalent to the "check sides" method I exposed ;)Logichttp://www.blogger.com/profile/10024617997824703986noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-25290487292240862872016-11-04T08:54:36.049-07:002016-11-04T08:54:36.049-07:00Ok, suppose that we have a general convex polygon,...Ok, suppose that we have a general convex polygon, N vertices.<br /><br />We seek to place or reject a test point, P within the polygon.<br /><br />We select as many test triangles as possible, N points 3 at a time, and apply the test on each triangle.<br /><br />The test point is in the polygon if it rests within at least one of the [N,3] of the triangles.<br /><br />Right?Bob Terryhttp://www.blogger.com/profile/07137578798614253121noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-34896437376936139282016-11-03T16:50:51.379-07:002016-11-03T16:50:51.379-07:00Hello, what about the winding number method [1] fo...Hello, what about the winding number method [1] for the step 2?<br /><br />thanks!<br /><br />[1] http://geomalgorithms.com/a03-_inclusion.htmlDavid Frogerhttps://github.com/dfrogernoreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-48590890937085933512016-06-06T12:51:03.264-07:002016-06-06T12:51:03.264-07:00Thank you very much.Thank you very much.lchtanhttp://www.blogger.com/profile/00405559574145155062noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-72120007165923767602016-05-30T03:49:06.913-07:002016-05-30T03:49:06.913-07:00Very good article. Thanks a lot it was very useful...Very good article. Thanks a lot it was very usefull to me.MrLikeidontcarehttp://www.blogger.com/profile/12945519555943583864noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-26812800670648337862015-11-24T17:54:38.396-08:002015-11-24T17:54:38.396-08:00Thank you.Thank you.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-39086688179525623122015-11-10T04:17:07.498-08:002015-11-10T04:17:07.498-08:00If you are not sure that your triangle is safe, be...If you are not sure that your triangle is safe, better is to check it before perfoming calculation. Check if any 2 points don't overlap. But problems can still occur with points being too close from each other !<br /><br />That is why in my library (Daedalus Lib) I proceeded differently. I choosed to merge points that are too close each other. For that I checked if the distance is smaller than the epsilon value.Logichttp://www.blogger.com/profile/10024617997824703986noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-38470013624272812472015-11-09T20:26:14.087-08:002015-11-09T20:26:14.087-08:00so first you have to test if the triangle is in fa...so first you have to test if the triangle is in fact a triangle?drecnoreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-50809424905754423802015-08-27T10:53:20.124-07:002015-08-27T10:53:20.124-07:00A graphical area is a semi-open interval - for con...A graphical area is a semi-open interval - for consistency this is usually done with lower bound inclusive, upper bound exclusive. A point on the boundary of two regions should not be in both; it should be in the region where the point is inclusive and excluded from the region where the point is exclusive. Very few graphics packages handle this issue properly - most have a fencepost error on the boundary. It should be possible to draw two squares from (0,0) to (10,10) and from (10,0) to (20,10) and have them abut exactly, as the pixels should be drawn from 0..9 and 10..19 - in which case a point such as (10,5) would belong to the (10,0) to (20,10) square only.Ghttp://www.blogger.com/profile/04079389970653405030noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-60557344438161067292015-07-15T14:57:49.456-07:002015-07-15T14:57:49.456-07:00Yes from a computational point of view, they are v...Yes from a computational point of view, they are very close. But the concepts involved in the reasonings are different, that's why I found interesting to expose both.Logichttp://www.blogger.com/profile/10024617997824703986noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-54773898368076641102015-07-15T13:58:04.779-07:002015-07-15T13:58:04.779-07:00Aren't the first and second methods the same t...Aren't the first and second methods the same thing? Joenoreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-2294873761870991802015-03-17T12:21:20.470-07:002015-03-17T12:21:20.470-07:00thanks a lotthanks a lotAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-57333204756537495442015-03-10T06:12:11.407-07:002015-03-10T06:12:11.407-07:00Awesome thank you very much for the help!
I will g...Awesome thank you very much for the help!<br />I will go ahead and implement it that way. Also thanks again for this great article! I will definitely come back to it, the next time I need a accurate triangle/point test! Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-13471023143643321872015-03-09T22:06:55.372-07:002015-03-09T22:06:55.372-07:00If your purpose is to identify the quad the user h...If your purpose is to identify the quad the user has clicked on, you can use your method, I think you will not face problems.Logichttp://www.blogger.com/profile/10024617997824703986noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-14037770457002438152015-03-08T12:36:20.635-07:002015-03-08T12:36:20.635-07:00Aha I see that makes sense!
What I am trying to do...Aha I see that makes sense!<br />What I am trying to do is a is-point-on-quad-test. The quad might be distorted in whatever way the user drags the corners. So my idea was to divide the quad into two triangles and simply test if the point is on either of those. There might be an arbitrary amount of quads, so I am a little cautious about computation time.<br />Since the trinagles share a border is it save to assume, that the barycentric test including Epsilon will not fail, if the point lies directly on the border?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-50906617671280076662015-03-08T01:51:46.792-08:002015-03-08T01:51:46.792-08:00The problem here is you don't have the control...The problem here is you don't have the control of the acceptance distance. This distance will be variable and will depend on the size of your triangle. So you face the danger to have wrong results with large triangles.Logichttp://www.blogger.com/profile/10024617997824703986noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-68858878536060627152015-03-06T11:46:45.164-08:002015-03-06T11:46:45.164-08:00This is a great article! Very informative.
I have ...This is a great article! Very informative.<br />I have one question though. Wouldn't it also be possible to acchive accurate results with only the barycentric method if you use it taking EPSILON into account?<br />Something like this:<br /><br />(0 - EPSILON) <= a <= (1 + EPSILON) and <br />(0 - EPSILON) <= b <= (1 + EPSILON) and <br />(0 - EPSILON) <= c <= (1 + EPSILON)<br /><br />Computation-wise that would be faster than the distance check on each segment. Wouldn't it be just as accurate?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-51330693290052959192014-09-18T23:25:52.333-07:002014-09-18T23:25:52.333-07:00Assuming you have P(x, y, z) and a triangle define...Assuming you have P(x, y, z) and a triangle defined by P1(x1, y1, z1), P2(x2, y2, z2), P3(x3, y3, z3), you can try to solve:<br /><br />x = a * x1 + b * x2 + c * x3<br />y = a * y1 + b * y2 + c * y3<br />z = a * z1 + b * z2 + c * z3<br />a + b + c = 1<br /><br />But having 3 free variables and 4 constraints means you are surely in trouble.<br /><br />You must add a new free degree in your system. For example, you could consider to have a new axis pointing orthogonaly to the plane defined by the triangle ; let's call it Ph(xh, yh, zh). Then you consider the system:<br /><br />x = a * x1 + b * x2 + c * x3 + t * xh<br />y = a * y1 + b * y2 + c * y3 + t * yh<br />z = a * z1 + b * z2 + c * z3 + t * zh<br />a + b + c = 1<br /><br />and you solve it for a, b, c, t.<br /><br />The t value can be:<br />t=0 if P is on the plane defined by the triangle<br />t>0 if P is above<br />t<0 if P is belowLogichttp://www.blogger.com/profile/10024617997824703986noreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-26803733183543219082014-09-18T16:51:54.783-07:002014-09-18T16:51:54.783-07:00Hi,
Can you tell how can i interpolate z using me...Hi,<br /><br />Can you tell how can i interpolate z using method 1. I also have a z coordinate for each point. I think there will be a d along with a, b, c but don't know how to calculate it.<br /><br />ThanksAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8152247234598992686.post-80495642253325813732014-09-08T04:25:40.752-07:002014-09-08T04:25:40.752-07:00Usually, 0 value for denominator happens for degen...Usually, 0 value for denominator happens for degenerate cases.<br /><br />For example, when you try to find the intersection of 2 lines using a parametric system, you face a 0 value when lines are parallel.<br /><br />In our case our system try to find the p coordinates as a linear combination of [p1, p2] and {p1, p3]. So what are our degenerate cases ? For example, when p2 = p3 ! Meaning your triangle is collapsed as a flat line !Logichttp://www.blogger.com/profile/10024617997824703986noreply@blogger.com