| Re: some geometry questions. [message #48152] |
Fri, 31 March 2006 08:50 |
Craig Markwardt
Messages: 1869
Registered: November 1996
|
Senior Member |
|
|
David Fanning <davidf@dfanning.com> writes:
> qian writes:
>
>> If I have 4 random points (x0,y0) (x1,y1), (x3,y3), (x4,y4), is there a
>> simple way to decide whether one of them is inside of the triangle
>> formed by the other three points?
>>
>> If none of them is in the triangle by others, how can I connect them in
>> order to form a 4 edges polygon, instead of two head on triangles, when
>> using order 1-2-3-4-1?
>>
>> like this:
>> 1----2
>> \ \
>> 4\__\3
>>
>> not like this:
>> 1-----2
>> \ /
>> /\
>> / \
>> 3-----4
>
> You are looking for a "complex hull algorithm", such as this
> one:
>
> http://nms.csail.mit.edu/~aklmiu/6.838/convexhull/index.html
>
> In IDL you can find the convex hull of a set of points
> with the TRIANGULATE command:
>
> http://www.dfanning.com/tips/convex_hull.html
David, I'm surprised you didn't refer to your own page, "Is Point
Inside Polygon?"
http://www.dfanning.com/tips/point_in_polygon.html
I've been using the algorithm you printed there by Krane for several
years and it works well. It is vectorized.
Craig
--
------------------------------------------------------------ --------------
Craig B. Markwardt, Ph.D. EMAIL: craigmnet@REMOVEcow.physics.wisc.edu
Astrophysics, IDL, Finance, Derivatives | Remove "net" for better response
------------------------------------------------------------ --------------
|
|
|
|
| Re: some geometry questions. [message #48170 is a reply to message #48152] |
Wed, 29 March 2006 21:29  |
Karl[1]
Messages: 79
Registered: October 2005
|
Member |
|
|
You might do a google search for "signed areas" and/or see:
http://softsurfer.com/Archive/algorithm_0101/algorithm_0101. htm#Triangles
The idea is to take the vector cross product of something like
(v4-v1)x(v2-v1) and compare it to (v2-v3)x(v4-v3). If the signs of the
z components are different, the lines cross.
A much bigger hammer to use is IDLgrTessellator. If you call the
AddPolygon method with those 4 points and then call the Tessellate
method, the tessellator will always return 2 triangles, but it will
return a 5th point if the lines cross, since the 5th point is needed to
define the point of intersection.
|
|
|
|
| Re: some geometry questions. [message #48174 is a reply to message #48170] |
Wed, 29 March 2006 15:56 |
David Fanning
Messages: 11724
Registered: August 2001
|
Senior Member |
|
|
qian writes:
> If I have 4 random points (x0,y0) (x1,y1), (x3,y3), (x4,y4), is there a
> simple way to decide whether one of them is inside of the triangle
> formed by the other three points?
>
> If none of them is in the triangle by others, how can I connect them in
> order to form a 4 edges polygon, instead of two head on triangles, when
> using order 1-2-3-4-1?
>
> like this:
> 1----2
> \ \
> 4\__\3
>
> not like this:
> 1-----2
> \ /
> /\
> / \
> 3-----4
You are looking for a "complex hull algorithm", such as this
one:
http://nms.csail.mit.edu/~aklmiu/6.838/convexhull/index.html
In IDL you can find the convex hull of a set of points
with the TRIANGULATE command:
http://www.dfanning.com/tips/convex_hull.html
Cheers,
David
--
David Fanning, Ph.D.
Fanning Software Consulting, Inc.
Coyote's Guide to IDL Programming: http://www.dfanning.com/
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
