source: abuse/tags/pd/abuse/src/intsect.c @ 49

Last change on this file since 49 was 49, checked in by Sam Hocevar, 11 years ago
  • Imported original public domain release, for future reference.
  • Property svn:keywords set to Id
File size: 5.2 KB
Line 
1#include "macs.hpp"
2#include <stdlib.h>
3
4void pushback(long x1,long y1,long &x2,long &y2,
5                     long xp1, long yp1, long xp2, long yp2, int xdir, int ydir, int inside)
6{
7
8   // determine if the lines are intersecting before we set back
9
10//   if (yp1==yp2)
11//   {
12//     if (inside && y2>=yp1)
13       
14}
15
16
17/* int setback_intersect(long x1,long y1,long &x2,long &y2,
18                     long xp1, long yp1, long xp2, long yp2)
19{
20  long mx1,my1,b1,mx2,my2,b2,side1,side2,tx2,ty2;
21  my1=(y2-y1);
22  if (!my1)                  // is the first line strait across?
23  {
24    side1=yp1-y2;          // if yes, check to see if the other is top/bottom
25    side2=yp2-y2;
26    mx1=(x2-x1);          // make sure we give this a value
27    b1=y2;
28  }
29  else
30  {
31    mx1=(x2-x1);           // if the line strait up and down?
32    if (!mx1)
33    {
34      side1=xp1-x1;
35      side2=xp2-x2;             
36    } else
37    {
38      b1=y1-(my1*x1/mx1);    // calculate the y intercept
39      side1=yp1-((my1*xp1)/mx1+b1);   
40      side2=yp2-((my1*xp2)/mx1+b1);
41    }
42  }
43  if ((side1>=0 && side2<=0) || (side1<=0 && side2>=0))
44  {
45    my2=(yp2-yp1);
46    if (!my2)
47    {
48      side1=y1-yp2;
49      side2=y2-yp2;
50      b2=yp1;
51      mx2=(xp2-xp1);
52    }
53    else
54    {
55      mx2=(xp2-xp1);
56      if (!mx2)
57      {
58        side1=x1-xp2;
59        side2=x2-xp2;
60      } else
61      {
62        b2=yp1-(my2*xp1/mx2);
63        side1=y1-((my2*x1)/mx2+b2);
64        side2=y2-((my2*x2)/mx2+b2);
65      }
66    }
67
68    // check two wierd cases where the lines are parallel
69    if (mx1==mx2 && mx1==0)             
70      if (y2<yp1 || y1>yp2)
71        side1=side2=1;           
72      else side1=side2=0;
73
74    if (my1==my2 && my2==0)
75      if (x2<xp1 || x1>xp2)
76        side1=side2=1;
77      else side1=side2=0;
78
79    if ((side1>=0 && side2<=0) || (side1<=0 && side2>=0))
80    {
81      tx2=x2;  ty2=y2;
82      int xadd,yadd;
83      if (x1>x2) xadd=1; else if (x1<x2) xadd=-1; else xadd=0;
84      if (y1>y2) yadd=1; else if (y1<y2) yadd=-1; else yadd=0;
85     
86      // now find the point of intersection
87      if (mx1==0)  // if the first line is strait up & down
88      {     
89        if (mx2==0)   // if they are both strait up then
90        { tx2=x1; ty2=y1; }  // they connect everywhere, don't let it move!
91        else
92          ty2=my2*x2/mx2+b2+yadd;                   
93      } else if (mx2==0)
94      { tx2=xp1+xadd;
95        ty2=my1*tx2/mx1+b1;
96      }
97      else
98      {
99        if (my1==0)
100          if (my2==0)
101            { tx2=x1; ty2=y1; }
102          else tx2=mx2*(y1-b2)/my2+xadd;
103        else if (my2==0)
104        {                   
105          ty2=yp1+yadd;
106          tx2=mx1*(ty2-b1)/my1;           
107        }                 
108        else
109        {
110          if (abs(mx1)>abs(my1))
111          {
112            long ae_bd=my1*mx2-mx1*my2;
113            CONDITION(ae_bd,"line intersect fuck up");
114            tx2=(mx1*mx2*(b2-b1))/ae_bd+xadd;
115            ty2=my1*tx2/mx1+b1;
116          }
117          else
118          {
119            long db_ea=(my2*mx1-mx2*my1);
120            CONDITION(db_ea,"line intersect fuck up");
121            ty2=(mx1*b1*my2-my1*mx2*b2)/db_ea+yadd;
122            tx2=mx1*(ty2-b1)/my1;
123          }
124        }
125      }
126
127      if (abs(tx2-x1)<abs(x2-x1) || abs(ty2-y1)<abs(y2-y1))
128      {
129        x2=tx2;
130        y2=ty2;
131        return 1;
132      } 
133    }
134  }
135  return 0; 
136} */
137
138
139int setback_intersect(long x1,long y1,long &x2,long &y2,
140                      long xp1, long yp1, long xp2, long yp2,
141                     long inside)  // which side is inside the polygon? (0 always setback)
142{
143  // the line equations will be put in the form
144  // x(y2-y1)+y(x1-x2)-x1*y2+x2*y1=0
145  //     A        B        C 
146
147  long a1,b1,c1,a2,b2,c2,r1,r2;             
148
149  a1=y2-y1;       
150  b1=x1-x2;       
151  c1=-x1*y2+x2*y1;
152
153  if (yp1<yp2 || (yp1==yp2 && xp1>xp2))    // use only increasing functions
154  {   
155    r1=yp1; yp1=yp2; yp2=r1;        // swap endpoints if wrong order
156    r1=xp1; xp1=xp2; xp2=r1;
157  }
158
159  long xdiff,ydiff;
160/*  long xdiff=abs(xp1-xp2),ydiff=yp1-yp2; 
161  if (xdiff>=ydiff)                              // increment the endpoints
162    if (xp2<xp1) { xp2--; xp1++; }                               
163    else { xp2++; xp1--; }
164 
165  if (xdiff<=ydiff)
166  {
167    yp1++;   
168    yp2--;
169  } */
170 
171
172  r1=xp1*a1+yp1*b1+c1;
173  r2=xp2*a1+yp2*b1+c1;
174
175  if ((r1^r2)<=0 || r1==0 || r2==0)           // signs must be different to intersect
176  {
177    a2=yp2-yp1; 
178    b2=xp1-xp2; 
179    c2=-xp1*yp2+xp2*yp1;       
180    r1=x1*a2+y1*b2+c2;
181    r2=x2*a2+y2*b2+c2;
182
183    if ((r1^r2)<=0 || r1==0 || r2==0)
184    {
185      if ( ((xp1<xp2) && ((r2^inside)>0)) ||
186           (xp1>=xp2 && ((r2^inside)<0)) ||
187           inside==0 || r2==0)
188      {
189        long ae=a1*b2,bd=b1*a2;
190        if (ae!=bd)         // co-linear returns 0
191        {
192          x2=(b1*c2-b2*c1)/(ae-bd);
193          y2=(a1*c2-a2*c1)/(bd-ae);       
194          xdiff=abs(x2-x1);
195          ydiff=abs(y2-y1);       
196//        if (xdiff<=ydiff)            // push the intersection back one pixel
197//        {
198            if (y2!=y1)
199            {         
200              if (y2>y1)
201                y2--;
202              else y2++;
203            }
204//        }
205//        if (xdiff>=ydiff)
206//        {
207            if (x2!=x1)
208            {
209              if (x2>x1)
210                x2--;
211              else x2++;
212            }
213//        }
214
215          if (inside)        // check to make sure end point is on the
216          {                  // right side
217            r1=x1*a2+y1*b2+c2;     
218            r2=x2*a2+y2*b2+c2;     
219            if ((r2!=0 && ((r1^r2)<0)))
220            {         
221              x2=x1;
222              y2=y1;
223            }     
224          }             
225          return 1;       
226        }
227      }
228    }   
229  }
230  return 0;
231   
232}
233
Note: See TracBrowser for help on using the repository browser.