home *** CD-ROM | disk | FTP | other *** search
/ Toolkit for DOOM / DOOMTOOL.ISO / editors / dme301.zip / SOURCE.ZIP / LINEMATH.C < prev    next >
C/C++ Source or Header  |  1994-07-16  |  19KB  |  883 lines
  1. /*
  2.     This is a DMapEdit source code module.  Though it is copyrighted, you
  3.     may modify it and use it for your own personal use, meaning that new
  4.     modified code and anything derived from it (such as exe files) doesn't
  5.     get distributed to anyone, unless you get my permission first.  Code
  6.     from this file, or code based on ideas from this file may be used with
  7.     other programs, provided that you give credit for it in the source code,
  8.     documentation, and 'about' windows or screens, if one exists, for the
  9.     programs using it.  Giving credit means something like this:
  10.  
  11.     Code from DMapEdit was used in this program
  12.  
  13.                               or
  14.  
  15.     Some code for this program was based on ideas presented in DMapEdit
  16.  
  17.     Whatever.  Just be sure to mention "DMapEdit" in such a way that it's
  18.     self-evident how it was useful to the new program, and be sure to have
  19.     "DMapEdit is a trademark of Jason Hoffoss" in the docs.  That's all..
  20. */
  21.  
  22. #include <stdio.h>
  23. #include <math.h>
  24. #include <graphics.h>
  25. #include <limits.h>
  26. #include "dme.h"
  27. #include "dme2.h"
  28.  
  29. extern int simple_splits;
  30. extern int complex_splits;
  31. extern int *slivers;
  32.  
  33. /* calculate the (x,y) where 2 lines cross */
  34.  
  35. int calc_line_cross(int *vv, int x1, int y1, int v2, int v3, int v4, uint angle)
  36. {
  37.     int x2, y2, x3, y3, x4, y4, angle2, old_angle=0, inc=1;
  38.     long dx1, dx2, dy1, dy2, x, y, ox, oy, oldx, oldy, p1, p2, p3;
  39.     float fy;
  40.  
  41.     x2 = vertexes[v2].x;
  42.     x3 = vertexes[v3].x;
  43.     x4 = vertexes[v4].x;
  44.     y2 = vertexes[v2].y;
  45.     y3 = vertexes[v3].y;
  46.     y4 = vertexes[v4].y;
  47.  
  48.     dx1 = x1 - x2;
  49.     dx2 = x3 - x4;
  50.     dy1 = y1 - y2;
  51.     dy2 = y3 - y4;
  52.  
  53.     if (!dx1) /* line 1 is vertical */
  54.     {
  55.         x = x1;
  56.         if (!dy2) /* line 2 horizontal? */
  57.         {
  58.             y = y3;
  59.             goto check;
  60.         }
  61.         y = (float) dy2 * (x - x3) / dx2 + y3;
  62.         goto check;
  63.     }
  64.  
  65.     if (!dx2) /* line 2 is vertical */
  66.     {
  67.         x = x3;
  68.         if (!dy1) /* line 1 horizontal? */
  69.         {
  70.             y = y1;
  71.             goto check;
  72.         }
  73.         y = (float) dy1 * (x - x1) / dx1 + y1;
  74.         goto check;
  75.     }
  76.  
  77.     if (!dy1) /* line 1 is horizontal */
  78.     {
  79.         y = y1;
  80.         if (!dx2) /* line 2 vertical? */
  81.         {
  82.             x = x3;
  83.             goto check;
  84.         }
  85.         x = (float) dx2 * (y - y3) / dy2 + x3;
  86.         goto check;
  87.     }
  88.  
  89.     if (!dy2) /* line 2 is horizontal */
  90.     {
  91.         y = y3;
  92.         if (!dx1) /* line 1 vertical? */
  93.         {
  94.             x = x1;
  95.             goto check;
  96.         }
  97.         x = (float) dx1 * (y - y1) / dy1 + x1;
  98.         goto check;
  99.     }
  100.  
  101.     p1 = dx1 * dy2;
  102.     p2 = dx2 * dy1;
  103.     p3 = dy1 * dy2;
  104.  
  105.     fy = (y1*p1 - y3*p2 + x3*p3 - x1*p3) / (p1 - p2);
  106.     y = fy + 0.5;
  107.     x = (float) dx2 * (fy - y3) / dy2 + x3;
  108.  
  109. check:
  110.     ox = x;
  111.     oy = y;
  112.  
  113. check2:
  114.     if (x1 == x && y1 == y)
  115.         angle2 = 0;
  116.     else
  117.         angle2 = adjusted_angle(angle, x1, y1, x, y);
  118.  
  119.     if (!angle2 || angle2 == INT_MIN)
  120.     {
  121.         simple_splits++;
  122.         if (v_size == v_max)
  123.         {
  124.             void far *ptr;
  125.  
  126.             ptr = resize_farmem(vertexes, (v_max+20) * sizeof(struct v_struct),
  127.                 "Vertexes");
  128.             if (!ptr)
  129.                 return -1;
  130.             vertexes = ptr;
  131.             v_max += 20;
  132.         }
  133.  
  134.         vertexes[v_size].x = x;
  135.         vertexes[v_size].y = y;
  136.         *vv = v_size;
  137.         return v_size++;
  138.     }
  139.  
  140.     if (angle2 > 0 && old_angle < 0) /* can't split with 0 angle */
  141.     {
  142.        slivers[complex_splits++] = v_size;
  143.         if (v_size+1 >= v_max)
  144.         {
  145.             void far *ptr;
  146.  
  147.             ptr = resize_farmem(vertexes, (v_max+20) * sizeof(struct v_struct),
  148.                 "Vertexes");
  149.             if (!ptr)
  150.                 return -1;
  151.             vertexes = ptr;
  152.             v_max += 20;
  153.         }
  154.  
  155.         vertexes[v_size].x = x;
  156.         vertexes[v_size++].y = y;
  157.         vertexes[v_size].x = oldx;
  158.         vertexes[v_size].y = oldy;
  159.         *vv = v_size++;
  160.         return (v_size - 2);
  161.     }
  162.  
  163.     if (angle2 < 0 && old_angle > 0)
  164.     {
  165.         slivers[complex_splits++] = v_size;
  166.         if (v_size+1 >= v_max)
  167.         {
  168.             void far *ptr;
  169.  
  170.             ptr = resize_farmem(vertexes, (v_max+20) * sizeof(struct v_struct),
  171.                 "Vertexes");
  172.             if (!ptr)
  173.                 return -1;
  174.             vertexes = ptr;
  175.             v_max += 20;
  176.         }
  177.  
  178.         vertexes[v_size].x = x;
  179.         vertexes[v_size].y = y;
  180.         *vv = v_size++;
  181.         vertexes[v_size].x = oldx;
  182.         vertexes[v_size].y = oldy;
  183.         return v_size++;
  184.     }
  185.  
  186.     oldx = ox;
  187.     oldy = oy;
  188.     ox = x;
  189.     oy = y;
  190.     old_angle = angle2;
  191.  
  192.     if (abs(dx2) < abs(dy2)) /* more vertical than horizontal */
  193.     {
  194.         y += inc;
  195.         x = (float) dx2 * (y - y3) / dy2 + x3;
  196.     } else {
  197.         x += inc;
  198.         y = (float) dy2 * (x - x3) / dx2 + y3;
  199.     }
  200.     if (inc < 0)
  201.         inc = -inc + 1;
  202.     else
  203.         inc = -inc - 1;
  204.     goto check2;
  205. }
  206.  
  207. /*  determine if line can be seen on the screen (isn't totally out of
  208.      bounds), and if so, clip it to fit on the screen.
  209. */
  210.  
  211. int line_visible(int num)
  212. {
  213.     int i, x1, y1, x2, y2, point1, point2;
  214.  
  215.     point1 = linedefs[num].v1;
  216.     point2 = linedefs[num].v2;
  217.     x1 = adjvx[point1];
  218.     x2 = adjvx[point2];
  219.     y1 = adjvy[point1];
  220.     y2 = adjvy[point2];
  221.     return line_in_rect(x1, y1, x2, y2, 0, 0, maxx, maxy);
  222. }
  223.  
  224. /*  determine if any point along the line (x1,y1)-(x2,y2) lies within the
  225.      rectangle (xmin,ymin)-(xmax,ymax).  If it does, the line is clipped
  226.      (values returned through global <win> struct)
  227. */
  228.  
  229. int line_in_rect(int x1, int y1, int x2, int y2, int xmin, int ymin, int xmax, int ymax)
  230. {
  231.     int i, left1, right1, top1, bottom1, left2, right2, top2, bottom2;
  232.  
  233.     while (1)
  234.     {
  235.         left1 = x1 < xmin; /* detect all out of bounds coords */
  236.         left2 = x2 < xmin;
  237.         right1 = x1 > xmax;
  238.         right2 = x2 > xmax;
  239.         top1 = y1 < ymin;
  240.         top2 = y2 < ymin;
  241.         bottom1 = y1 > ymax;
  242.         bottom2 = y2 > ymax;
  243.  
  244.         if ((left1*left2 + right1*right2 + top1*top2 + bottom1*bottom2) != 0)
  245.             return 0; /* both points out of same range */
  246.         if (!(left1+left2+right1+right2+top1+top2+bottom1+bottom2))
  247.         { /* line fully fits inside rectangle */
  248.             win.left = x1;
  249.             win.right = x2;
  250.             win.top = y1;
  251.             win.bottom = y2;
  252.             return 1;
  253.         }
  254.  
  255.         if (left1) /* make a clip and re-check */
  256.         {
  257.             y1 = xclip(xmin, x1, y1, x2, y2);
  258.             x1 = xmin;
  259.             continue;
  260.         }
  261.         if (left2)
  262.         {
  263.             y2 = xclip(xmin, x1, y1, x2, y2);
  264.             x2 = xmin;
  265.             continue;
  266.         }
  267.         if (right1)
  268.         {
  269.             y1 = xclip(xmax, x1, y1, x2, y2);
  270.             x1 = xmax;
  271.             continue;
  272.         }
  273.         if (right2)
  274.         {
  275.             y2 = xclip(xmax, x1, y1, x2, y2);
  276.             x2 = xmax;
  277.             continue;
  278.         }
  279.         if (top1)
  280.         {
  281.             x1 = yclip(ymin, x1, y1, x2, y2);
  282.             y1 = ymin;
  283.             continue;
  284.         }
  285.         if (top2)
  286.         {
  287.             x2 = yclip(ymin, x1, y1, x2, y2);
  288.             y2 = ymin;
  289.             continue;
  290.         }
  291.         if (bottom1)
  292.         {
  293.             x1 = yclip(ymax, x1, y1, x2, y2);
  294.             y1 = ymax;
  295.             continue;
  296.         } /* must be bottom2 */
  297.         x2 = yclip(ymax, x1, y1, x2, y2);
  298.         y2 = ymax;
  299.     }
  300. }
  301.  
  302. /*  given line (x1,y1)-(x2,y2) and x, determine y.  (x,y) lies on line  */
  303.  
  304. int xclip(int x, int x1, int y1, int x2, int y2)
  305. {
  306.     return (y1 + (float) (y2-y1) * (x-x1) / (x2-x1));
  307. }
  308.  
  309. /*  given line (x1,y1)-(x2,y2) and y, determine x.  (x,y) lies on line  */
  310.  
  311. int yclip(int y, int x1, int y1, int x2, int y2)
  312. {
  313.     return (x1 + (float) (x2-x1) * (y-y1) / (y2-y1));
  314. }
  315.  
  316. /*  distance mouse is from line (x1,y1)-(x2,y2)  */
  317.  
  318. int line_dist(int x1, int y1, int x2, int y2)
  319. {
  320.     int x, y, dist1, dist2;
  321.     float m1, m2, fx, fy;
  322.  
  323.     x1 -= mousex; /* put mouse at the origin for calculations */
  324.     y1 -= mousey;
  325.     x2 -= mousex;
  326.     y2 -= mousey;
  327.  
  328.     if (x1 == x2) /* vertical line */
  329.     {
  330.         if (between(0, y1, y2))
  331.             return abs(x1);
  332.         dist1 = abs(x1) + abs(y1); /* not true distance, but faster */
  333.         dist2 = abs(x2) + abs(y2); /* actually diamond shaped */
  334.         if (dist1 < dist2)
  335.             return dist1;
  336.         return dist2;
  337.     }
  338.  
  339.     if (y1 == y2) /* horizontal line */
  340.     {
  341.         if (between(0, x1, x2))
  342.             return abs(y1);
  343.         dist1 = abs(x1) + abs(y1);
  344.         dist2 = abs(x2) + abs(y2);
  345.         if (dist1 < dist2)
  346.             return dist1;
  347.         return dist2;
  348.     }
  349.  
  350.     m1 = (float) (y1 - y2) / (x1 - x2); /* line's slope */
  351.     m2 = -(1/m1); /* perpendicular line's slope */
  352.  
  353.     fx = (m1 * x1 - y1) / (m1 - m2); /* solve 2 equations: */
  354.     fy = m2 * fx;           /* y = m1(x - x1) + y1  and  y = m2 * x */
  355.     x = fx; /* now precision isn't important */
  356.     y = fy;
  357.     if (between(x, x1, x2))
  358.         return (abs(x) + abs(y)); /* lies on the line segment */
  359.     dist1 = abs(x1) + abs(y1);
  360.     dist2 = abs(x2) + abs(y2);
  361.     if (dist1 < dist2)
  362.         return dist1;
  363.     return dist2;
  364. }
  365.  
  366. /*  find vertical distance from (x,y) to a line (can be pos or neg) */
  367.  
  368. int line_dist2(int x, int y, int x1, int y1, int x2, int y2)
  369. {
  370.     int yy;
  371.  
  372.     x1 -= x; /* put (x,y) at the origin for calculations */
  373.     y1 -= y;
  374.     x2 -= x;
  375.     y2 -= y;
  376.  
  377.     if (y1 == y2) /* horizontal line */
  378.         return y1;
  379.  
  380.     yy = (float) x1 * (y2 - y1) / (x1 - x2) + y1;
  381.     return yy;
  382. }
  383.  
  384. /*  calculate the angle of line (x1,y1)-(x2,y2).  (x1,y1) is origin  */
  385.  
  386. uint calc_angle(int x1, int y1, int x2, int y2)
  387. {
  388.     int x, y;
  389.     uint ang;
  390.     double angle;
  391.  
  392.     x = abs(x2 - x1);
  393.     y = abs(y2 - y1);
  394.     angle = M_PI_2;
  395.     if (x != 0)
  396.         angle = atan( (float) y/x);
  397.     ang = angle * 32768 / M_PI;
  398.     x = ((x2-x1) < 0)*2 + ((y2-y1) < 0);
  399.     if (x == 1)
  400.         ang = 65536 - ang;
  401.     if (x == 2)
  402.         ang = 32768 - ang;
  403.     if (x == 3)
  404.         ang += 32768;
  405.     return ang;
  406. }
  407.  
  408. /*  find the next line around a polygon
  409.      vertex = consider lines connected to this vertex
  410.      angle  = angle of line, vertex being the 'toward' point
  411.      line   = current line
  412.      side   = tracing around left(1) or right(0) side
  413.  
  414.      return = direction of line (to(1) or from(0) vertex)
  415. */
  416.  
  417. int find_next_line(int *vertex, uint *angle, int *line, int side)
  418. {
  419.     int i, num, sidedef, dir, line_num[50];
  420.     uint new_angle, angles[50];
  421.     long langle, angle_min, angle_max;
  422.  
  423.     for (i=0, num=0; i<l_size; i++)
  424.     {
  425.         if (i == *line)
  426.             continue;
  427.         if (linedefs[i].v1 == *vertex)
  428.         {
  429.             line_num[num] = i + 1;
  430.             angles[num++] = calc_angle(vertexes[*vertex].x,
  431.                 vertexes[*vertex].y, vertexes[linedefs[i].v2].x,
  432.                 vertexes[linedefs[i].v2].y);
  433.         }
  434.         if (linedefs[i].v2 == *vertex)
  435.         {
  436.             line_num[num] = -i - 1;
  437.             angles[num++] = calc_angle(vertexes[*vertex].x,
  438.                 vertexes[*vertex].y, vertexes[linedefs[i].v1].x,
  439.                 vertexes[linedefs[i].v1].y);
  440.         }
  441.     }
  442.     if (!num)
  443.         return -1; /* dead end line */
  444.  
  445.     *line = 0;
  446.     *angle ^= 0x8000; /* switch to opposite direction */
  447.     angle_min = 655360;
  448.     angle_max = 0;
  449.     for (i=0; i<num; i++)
  450.     {
  451.         langle = (long) angles[i] - *angle;
  452.         if (langle < 0)
  453.             langle += 65536;
  454.  
  455.         if (side)
  456.         {
  457.             if (langle < angle_min)
  458.             {
  459.                 angle_min = langle;
  460.                 *line = line_num[i];
  461.                 new_angle = angles[i];
  462.             }
  463.         } else {
  464.             if (langle > angle_max)
  465.             {
  466.                 angle_max = langle;
  467.                 *line = line_num[i];
  468.                 new_angle = angles[i];
  469.             }
  470.         }
  471.     }
  472.     if (!(*line))
  473.         return -1;
  474.  
  475.     if (*line > 0)
  476.     {
  477.         dir = 0;
  478.         *line -= 1;
  479.         *vertex = linedefs[*line].v2;
  480.     } else {
  481.         dir = 1;
  482.         *line = -(*line) - 1;
  483.         *vertex = linedefs[*line].v1;
  484.     }
  485.     *angle = new_angle;
  486.     return dir;
  487. }
  488.  
  489. /* determine if a line & side faces the outside void */
  490.  
  491. int outside_detect(int line1, int side1)
  492. {
  493.     int i, v1, v2, line, orig_line, side, dir;
  494.     uint angle;
  495.  
  496.     if (!max_vertex || !l_size)
  497.         return -1;
  498.     if (line1 == -1)
  499.         return 1;
  500.  
  501.     v1 = 0;
  502.     for (i=1; i<max_vertex; i++)
  503.         if (vertexes[i].y < vertexes[v1].y)
  504.             v1 = i; /* find the bottom most vertex on map */
  505.  
  506.     if ((line = downward_line(v1, &side, testmode)) == -1)
  507.         return -1;
  508.     if (testmode > 1)
  509.     {
  510.         setcolor(0);
  511.         draw_side(tx3, ty3, tx4,ty4);
  512.         setcolor(96);
  513.         draw_line2(adjustx(tx3), adjusty(ty3),
  514.             adjustx(tx4), adjusty(ty4));
  515.     }
  516.  
  517.     orig_line = line; /* this is our starting line */
  518.     v1 = linedefs[line].v1;
  519.     v2 = linedefs[line].v2;
  520.     side = dir = 0;
  521.     if (vertexes[v1].x < vertexes[v2].x)
  522.         side = 1;
  523.     angle = calc_angle(vertexes[v1].x, vertexes[v1].y,
  524.         vertexes[v2].x, vertexes[v2].y);
  525.  
  526.     do /* go through the entire outside border, checking all lines */
  527.     {
  528.         if (line == line1)
  529.         {
  530.             if (dir)
  531.             {
  532.                 if (side != side1)
  533.                     return 1; /* is on outside */
  534.             } else {
  535.                 if (side == side1)
  536.                     return 1;
  537.             }
  538.         }
  539.  
  540.         dir = find_next_line(&v2, &angle, &line, side);
  541.         if (dir == -1)
  542.         {
  543.             deadend_error();
  544.             return -1;
  545.         }
  546.     } while (line != orig_line);
  547.     return 0;
  548. }
  549.  
  550. /*  find an inside line of a polygon that (x,y) is within.  Return this
  551.      line, as well as the side that is inside
  552. */
  553.  
  554. int inside_poly(int x, int y, int *side, int test)
  555. {
  556.     char msg[60];
  557.     int line, new_line, dist, dist_min, v1, v2, x1, x2, y1, y2;
  558.  
  559.     dist_min = INT_MAX; /* find sidedef straight down from (x,y) */
  560.     *side = new_line = -1;
  561.     for (line=0; line<l_size; line++)
  562.     {
  563.         v1 = linedefs[line].v1;
  564.         v2 = linedefs[line].v2;
  565.         x1 = vertexes[v1].x;
  566.         x2 = vertexes[v2].x;
  567.         y1 = vertexes[v1].y;
  568.         y2 = vertexes[v2].y;
  569.         if (x1 == x2)
  570.             continue; /* vertical line, so skip it */
  571.         if ((x1 < x) && (x2 < x))
  572.             continue; /* doesn't cross line */
  573.         if ((x1 > x) && (x2 > x))
  574.             continue; /* doesn't cross line either */
  575.  
  576.         dist = -line_dist2(x, y, x1, y1, x2, y2);
  577.         if (dist < 1)
  578.             continue; /* wrong direction now */
  579.  
  580.         if (dist > dist_min)
  581.             continue;
  582.         if (dist == dist_min) /* time to decide which one we want.. */
  583.         {
  584.             if (test > 1)
  585.             {
  586.                 color2wall(line, 80, 80);
  587.                 color2wall(new_line, 80, 80);
  588.                 cursored_get(0, 9);
  589.                 color2wall(line, 96, 96);
  590.                 color2wall(new_line, 96, 96);
  591.                 setcolor(60);
  592.                 draw_side(tx1, ty1, tx2, ty2);
  593.             }
  594.             if (line_least_angle(line, new_line, 16384) == new_line)
  595.                 continue;
  596.         }
  597.  
  598.         dist_min = dist;
  599.         new_line = line;
  600.         if (x1 > x2)
  601.             *side = 1;
  602.         else
  603.             *side = 0;
  604.  
  605.         if (test > 1)
  606.         {
  607.             if (new_line != -1)
  608.             {
  609.                 setcolor(0);
  610.                 draw_side(tx1, ty1, tx2, ty2);
  611.                 setcolor(96);
  612.                 draw_line2(adjustx(tx1), adjusty(ty1),
  613.                     adjustx(tx2), adjusty(ty2));
  614.             }
  615.  
  616.             setcolor(60);
  617.             if (x1 > x2)
  618.             {
  619.                 tx1 = x1;
  620.                 tx2 = x2;
  621.                 ty1 = y1;
  622.                 ty2 = y2;
  623.             } else {
  624.                 tx1 = x2;
  625.                 tx2 = x1;
  626.                 ty1 = y2;
  627.                 ty2 = y1;
  628.             }
  629.             draw_side(tx1, ty1, tx2, ty2);
  630.             sprintf(msg, "New line detected=%d  Side=%d  dist=%d",
  631.                 new_line, *side, dist);
  632.             toptext(msg);
  633.             cursored_get(0, 9);
  634.         }
  635.     }
  636.     return new_line;
  637. }
  638.  
  639. int downward_line(int vertex, int *side, int test)
  640. {
  641.     char msg[60];
  642.     int x, y, line, new_line, angle, temp, dir, side1, sidedef;
  643.     uint angle_min;
  644.  
  645.     x = vertexes[vertex].x;
  646.     y = vertexes[vertex].y;
  647.     new_line = -1;
  648.     angle_min = 65535;
  649.  
  650.     for (line=0; line<l_size; line++) /* find sidedef of vertex */
  651.     {
  652.         dir = -1;
  653.         if (linedefs[line].v1 == vertex)
  654.         {
  655.             dir = 0;
  656.             temp = linedefs[line].v2;
  657.         }
  658.         if (linedefs[line].v2 == vertex)
  659.         {
  660.             dir = 1;
  661.             temp = linedefs[line].v1;
  662.         }
  663.         if (dir != -1)
  664.         {
  665.             angle = adjusted_angle(49152, x, y, vertexes[temp].x,
  666.                 vertexes[temp].y);
  667.             if (labs(angle) < angle_min)
  668.             {
  669.                 angle_min = labs(angle);
  670.                 side1 = 0;
  671.                 if (angle < 0)
  672.                     side1 = 1;
  673.  
  674.                 if (dir != side1)
  675.                     *side = 1;
  676.                 else
  677.                     *side = 0;
  678.  
  679.                 if (test > 1)
  680.                 {
  681.                     if (new_line != -1)
  682.                     {
  683.                         setcolor(0);
  684.                         draw_side(tx3, ty3, tx4,ty4);
  685.                         setcolor(96);
  686.                         draw_line2(adjustx(tx3), adjusty(ty3),
  687.                             adjustx(tx4), adjusty(ty4));
  688.                     }
  689.  
  690.                     if (side1)
  691.                     {
  692.                         tx3 = x;
  693.                         ty3 = y;
  694.                         tx4 = vertexes[temp].x;
  695.                         ty4 = vertexes[temp].y;
  696.                     } else {
  697.                         tx4 = x;
  698.                         ty4 = y;
  699.                         tx3 = vertexes[temp].x;
  700.                         ty3 = vertexes[temp].y;
  701.                     }
  702.                     setcolor(120);
  703.                     draw_side(tx3, ty3, tx4, ty4);
  704.  
  705.                     if (*side)
  706.                         sidedef = linedefs[line].sd1;
  707.                     else
  708.                         sidedef = linedefs[line].sd2;
  709.  
  710.                     sprintf(msg, "detect point=(%d,%d) Sidedef=%d Angle=%d",
  711.                         x, y, sidedef, angle);
  712.                     toptext(msg);
  713.                     cursored_get(0, 9);
  714.                 }
  715.                 new_line = line; /* new line found */
  716.             }
  717.         }
  718.     }
  719.     return new_line;
  720. }
  721.  
  722. /*  determine which of the 2 given lines (both with a common vertex) has
  723.      the closest angle to the given angle (common vertex is the origin
  724.      of all the angles)
  725. */
  726.  
  727. int line_least_angle(int line1, int line2, uint angle)
  728. {
  729.     int v1, v2, v3, v4, x1, y1, x2, y2, x3, y3, x4, y4, temp;
  730.  
  731.     v1 = linedefs[line1].v1;
  732.     v2 = linedefs[line1].v2;
  733.     v3 = linedefs[line2].v1;
  734.     v4 = linedefs[line2].v2;
  735.  
  736.     if ((v1 == v4) || (v2 == v4))
  737.     {
  738.         temp = v3;
  739.         v3 = v4;
  740.         v4 = temp;
  741.     }
  742.     if (v2 == v3) {
  743.         temp = v1;
  744.         v1 = v2;
  745.         v2 = temp;
  746.     }
  747.     if (v1 != v3)
  748.         return -1;
  749.  
  750.     x1 = vertexes[v1].x;
  751.     x2 = vertexes[v2].x;
  752.     x3 = vertexes[v3].x;
  753.     x4 = vertexes[v4].x;
  754.     y1 = vertexes[v1].y;
  755.     y2 = vertexes[v2].y;
  756.     y3 = vertexes[v3].y;
  757.     y4 = vertexes[v4].y;
  758.  
  759.     if (abs(adjusted_angle(angle, x1, y1, x2, y2)) <
  760.         abs(adjusted_angle(angle, x3, y3, x4, y4)))
  761.         return line1;
  762.     return line2;
  763. }
  764.  
  765. /* return angle of line (x1,y1)-(x2,y2) using <angle> as the reference */
  766.  
  767. int adjusted_angle(uint angle, int x1, int y1, int x2, int y2)
  768. {
  769.     long angle2;
  770.  
  771.     angle2 = (long) angle - calc_angle(x1, y1, x2, y2);
  772.     if (angle2 > INT_MAX)
  773.         angle2 -= 65536;
  774.     if (angle2 < INT_MIN)
  775.         angle2 += 65536;
  776.     return angle2;
  777. }
  778.  
  779. /*  determine where (x,y) lies relative to a line:
  780.      neg  = left side
  781.      zero = on line
  782.      pos  = right side
  783. */
  784.  
  785. int line_side(int line, int x, int y)
  786. {
  787.     int x1, y1, x2, y2, v1, v2;
  788.     uint angle;
  789.  
  790.     v1 = linedefs[line].v1;
  791.     v2 = linedefs[line].v2;
  792.     x1 = vertexes[v1].x;
  793.     x2 = vertexes[v2].x;
  794.     y1 = vertexes[v1].y;
  795.     y2 = vertexes[v2].y;
  796.  
  797.     angle = calc_angle(x1, y1, x, y);
  798.     return adjusted_angle(angle, x1, y1, x2, y2);
  799. }
  800.  
  801. /*  take on characteristics of ajacent lines.  */
  802.  
  803. int match_line(int vertex, int vertex2)
  804. {
  805.     int i, num, v1, v2, sidedef, line_min, line_max, line_num[50];
  806.     uint angle, angles[50];
  807.     long langle, angle_min, angle_max;
  808.  
  809.     num = 0;
  810.     for (i=0; i<l_size; i++)
  811.     {
  812.         v1 = linedefs[i].v1;
  813.         v2 = linedefs[i].v2;
  814.  
  815.         if (v1 == vertex && num < 50)
  816.         {
  817.             line_num[num] = i + 1;
  818.             angles[num++] = calc_angle(vertexes[vertex].x,
  819.                 vertexes[vertex].y, vertexes[v2].x, vertexes[v2].y);
  820.         }
  821.         if (v2 == vertex && num < 50)
  822.         {
  823.             line_num[num] = -i - 1;
  824.             angles[num++] = calc_angle(vertexes[vertex].x,
  825.                 vertexes[vertex].y, vertexes[v1].x, vertexes[v1].y);
  826.         }
  827.     }
  828.     if (!num)
  829.         return 0; /* no other lines connected to this vertex */
  830.  
  831.     angle = calc_angle(vertexes[vertex].x, vertexes[vertex].y,
  832.         vertexes[vertex2].x, vertexes[vertex2].y);
  833.     line_min = line_max = 0;
  834.     angle_min = 65536;
  835.     angle_max = -1;
  836.     for (i=0; i<num; i++)
  837.     {
  838.         langle = (long) angles[i] - angle;
  839.         if (langle < 0)
  840.             langle += 65536; /* 0-65535 range */
  841.         if (langle < angle_min)
  842.         {
  843.             angle_min = langle;
  844.             line_min = line_num[i];
  845.         }
  846.         if (langle > angle_max)
  847.         {
  848.             angle_max = langle;
  849.             line_max = line_num[i];
  850.         }
  851.     }
  852.     if ((!line_min) || (!line_max))
  853.         fatal_error("Impossibility #1");
  854.  
  855.     if (line_min > 0)
  856.     {
  857.         line_min--;
  858.         sidedef = linedefs[line_min].sd1;
  859.     } else {
  860.         line_min = -line_min - 1;
  861.         sidedef = linedefs[line_min].sd2;
  862.     }
  863.  
  864.     if (sidedef != -1)
  865.         linedefs[l_size].sd2 = add_sidedef(sidedef);
  866.  
  867.     if (line_max > 0)
  868.         sidedef = linedefs[line_max - 1].sd2;
  869.     else
  870.         sidedef = linedefs[-line_max - 1].sd1;
  871.  
  872.     if (sidedef != -1)
  873.         linedefs[l_size].sd1 = add_sidedef(sidedef);
  874.  
  875.     if (line_min == l_size)
  876.         fatal_error("line_min == l_size");
  877.  
  878.     linedefs[l_size].attrib = linedefs[line_min].attrib;
  879.     linedefs[l_size].type = linedefs[line_min].type;
  880.     linedefs[l_size].trig = linedefs[line_min].trig;
  881.     return 1;
  882. }
  883.