I need to calculate in a fast way, the following:

2D real space:
1. If segment crosses a polygon.
2. Which (x,y) positions does the segment crosses the polygon.
(this can be two algoritms, so that first be as fast as possible).
The polygon is defined is a clockwise list of vertices.
It has holes but, only matters the results of the outer ring.

3D real space:
1. If a segment crosses a 3D cube.(it cube can be a rotated cube in the 3d
space)
2. Which surface of the cube, and the shortests distance.
Currently a have an algoritm that projects the segment against each of
surfaces of the cube.
An ideia is to transform the cube so that it is paralel with the xy plane,
and the makes clipping tests.
Other algoritms would be apreciated.

Thanks in advanced

Alexandre Bento Freire schrieb:

You hve to construct an half plane construction for the anles of the
point and the border polygon points.

Have fun A.Weidauer

If the point is inside you got a number greater then 180 degrees.
If the Point is outside you got nearly zero.

Here are the routines:

//------------------------------------------------------------------------------

Function  XYLength(A,B:TXYPoint):Double;
  Begin
   XYLength:=SQRT(SQR(A.X-B.X)+SQR(A.Y-B.Y));
  End;

//------------------------------------------------------------------------------

Function TriXYAngle(PBegin,PMiddle,PEnd:TXYPoint):Double;
 Var AC,ACX,ACG,TR:Double;
 Begin
   TR:=TriXYArea(PEnd,PMiddle,PBegin);
   AC:=TriXYCos(PBegin,PMiddle,PEnd);
   ACX:=ArcCos(AC);
   ACG:=ACX/Pi*180;
   if Tr>=0 then TriXYAngle:=+ACG;
   if Tr<0 then TriXYAngle :=-ACG;
   if AC=1e38 then TriXYAngle:=1e38;
 End;

//------------------------------------------------------------------------------

Function TriXYArea(PBegin,PMiddle,PEnd:TXYPoint):Double;
 Begin
  TriXYArea:=(PBegin .y  +PMiddle.y)/2*(PMiddle.x - PBegin.X)
            +(PMiddle.y  +PEnd.y)   /2*(PEnd.x    - PMiddle.X)
            +(PBegin .y  +PEnd.y)   /2*(PBegin.x  - PEnd.X);
 End;
//------------------------------------------------------------------------------

Function TriXYCos(PBegin,PMiddle,PEnd:TXYPoint):Double;
 Var a,b,c:Double;
 Begin
  a:=XYLength(PBegin,PMiddle);
  b:=XYLength(PMiddle,PEnd);
  c:=XYLength(PEnd,PBegin);
  if a*b=0 then
   TriXYCos:=1E38
  Else
   TriXYCos:=(SQR(C)-SQR(A)-SQR(B))/-(2*A*B); // Cosinussatz
 End;

//------------------------------------------------------------------------------

Function TXYPointList.Inside(P:TXYPoint):Boolean;
Var i:Integer; Sum:Double;
Begin
 ClosePolygon;Sum:=0;
 For i:=1 to MaxPoint-1 Do Begin
  Sum:=Sum+TriXYAngle(Points[i],P,Points[i+1]);
 End;
 Result:=(Sum>180);
End;

"Alexandre Bento Freire" <a-bentofre...@a-bentofreire.com.nospam> wrote in message
news:3a6c1a8d_1@dnews...

Try "Point in Polygon" links:
http://www.efg2.com/Lab/Library/Delphi/Graphics/Math.htm

Non-Delphi links:
"Clipping" (polygon clipping, etc.) and "Point in Polygon" links in Section B of
http://www.efg2.com/Lab/Library/Graphics.htm#Algorithms     :

--
efg

Earl F. Glynn, Overland Park, KS  USA     E-mail:  e...@efg2.com

efg's Computer Lab:  http://www.efg2.com/Lab
Mirror:  http://homepages.borland.com/efg2lab/Default.htm

Thank you for the code !
But, i have already an algoritm for point in polygon.
The title of may e-mail was incorrect.
What i need is to know is if the segment intersects the polygon.
Both start point, and end point may be outside, but the line still crosses
the polygon.

Any pointers will be most helpuf.

news:3A6C39D6.B40842E5@ifgdv-mv.de...

Alexandre Bento Freire schrieb:
I need to calculate in a fast way, the following:
2D real space:
1. If segment crosses a polygon.
2. Which (x,y) positions does the segment crosses the polygon.
(this can be two algoritms, so that first be as fast as possible).
The polygon is defined is a clockwise list of vertices.
It has holes but, only matters the results of the outer ring.
3D real space:
1. If a segment crosses a 3D cube.(it cube can be a rotated cube in the 3d
space)
2. Which surface of the cube, and the shortests distance.
Currently a have an algoritm that projects the segment against each of
surfaces of the cube.
An ideia is to transform the cube so that it is paralel with the xy plane,
and the makes clipping tests.
Other algoritms would be apreciated.
Thanks in advanced

You hve to construct an half plane construction for the anles of the
point and the border polygon points.
Have fun A.Weidauer
If the point is inside you got a number greater then 180 degrees.
If the Point is outside you got nearly zero.
Here are the routines:
//--------------------------------------------------------------------------
----
Function  XYLength(A,B:TXYPoint):Double;
  Begin
   XYLength:=SQRT(SQR(A.X-B.X)+SQR(A.Y-B.Y));
  End;
//--------------------------------------------------------------------------
----
Function TriXYAngle(PBegin,PMiddle,PEnd:TXYPoint):Double;
 Var AC,ACX,ACG,TR:Double;
 Begin
   TR:=TriXYArea(PEnd,PMiddle,PBegin);
   AC:=TriXYCos(PBegin,PMiddle,PEnd);
   ACX:=ArcCos(AC);
   ACG:=ACX/Pi*180;
   if Tr>=0 then TriXYAngle:=+ACG;
   if Tr<0 then TriXYAngle :=-ACG;
   if AC=1e38 then TriXYAngle:=1e38;
 End;
//--------------------------------------------------------------------------
----
Function TriXYArea(PBegin,PMiddle,PEnd:TXYPoint):Double;
 Begin
  TriXYArea:=(PBegin .y  +PMiddle.y)/2*(PMiddle.x - PBegin.X)
            +(PMiddle.y  +PEnd.y)   /2*(PEnd.x    - PMiddle.X)
            +(PBegin .y  +PEnd.y)   /2*(PBegin.x  - PEnd.X);
 End;
//--------------------------------------------------------------------------
----
Function TriXYCos(PBegin,PMiddle,PEnd:TXYPoint):Double;
 Var a,b,c:Double;
 Begin
  a:=XYLength(PBegin,PMiddle);
  b:=XYLength(PMiddle,PEnd);
  c:=XYLength(PEnd,PBegin);
  if a*b=0 then
   TriXYCos:=1E38
  Else
   TriXYCos:=(SQR(C)-SQR(A)-SQR(B))/-(2*A*B); // Cosinussatz
 End;
//--------------------------------------------------------------------------
----
Function TXYPointList.Inside(P:TXYPoint):Boolean;
Var i:Integer; Sum:Double;
Begin
 ClosePolygon;Sum:=0;
 For i:=1 to MaxPoint-1 Do Begin
  Sum:=Sum+TriXYAngle(Points[i],P,Points[i+1]);
 End;
 Result:=(Sum>180);
End;

Thank you for the links!
But, i have already an algoritm for point in polygon.
The title of may e-mail was incorrect.
What i need is to know is if the segment intersects the polygon.
Both start point, and end point may be outside, but the line still crosses
the polygon.

Any pointers will be most helpuf.
I'm a regular reader of www.efg2.com

"Earl F. Glynn" <EarlGl...@att.net> wrote in message
news:94hlsp$oef16@bornews.inprise.com...

Alexandre Bento Freire <a-bentofre...@a-bentofreire.com.nospam> wrote in
message 3a6c8eb6_2@dnews...

You have to check if your segment intersects any segment of the polygon
between two consecutive vertexes , i think ! So your problem becomes : "how
do i find intersection between two segments ( one of which is a segment of
the polygon  )?"
i think this problem is much easier !

i have an algoritm for line intersecction.
But is't there a fastest way ?

news:94i83q$m5b3@bornews.inprise.com...

Hi Alexandre,

If your polygons have many sides and if your segment is not very long, you
might try to use the algorithm for line intersection only for the sides
that could cross your segment.

For example, if both ends of one side have either a smaller or larger X
(or Y) than any of the two ends of your segment, you already know that the
side will not be able to cross the segment.

Thrse