navit/maptool/geom.c

/**
 * ZANavi, Zoff Android Navigation system.
 * Copyright (C) 2011-2012 Zoff <zoff@zoff.cc>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * version 2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA  02110-1301, USA.
 */

/**
 * Navit, a modular navigation system.
 * Copyright (C) 2005-2011 Navit Team
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * version 2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA  02110-1301, USA.
 */
#include <string.h>
#include <math.h>
#include "maptool.h"

void geom_coord_copy(struct coord *from, struct coord *to, int count, int reverse)
{
        int i;
        if (!reverse)
        {
                memcpy(to, from, count * sizeof(struct coord));
                return;
        }
        from += count;
        for (i = 0; i < count; i++)
        {
                *to++ = *--from;
        }
}


/**
  * Get coordinates of polyline middle point.
  * @param in *p array of poly vertex coordinates
  * @param in count count of poly vertexes
  * @param out *c coordinates of middle point
  * @returns number of first vertex of segment containing middle point
  */
int geom_line_middle(struct coord *p, int count, struct coord *c)
{
        double length = 0, half = 0, len = 0;
        int i;

        if (count == 1)
        {
                *c=*p;
                return 0;
        }
        
        for (i=0; i<count-1; i++)
        {
                length+=sqrt(sq(p[i].x-p[i+1].x)+sq(p[i].y-p[i+1].y));
        }

        length /= 2;
        for (i=0; (i<count-1) && (half<length); i++)
        {
                len=sqrt(sq(p[i].x-p[i+1].x)+sq(p[i].y-p[i+1].y));
                half += len;
        }

        if (i > 0)
        {
                i--;
                half -= length;
                if (len)
                {
                        c->x=(p[i].x*half+p[i+1].x*(len-half))/len;
                        c->y=(p[i].y*half+p[i+1].y*(len-half))/len;
                }
                else
                {
                        *c = p[i];
                }
        }
        else
        {
                *c = p[0];
        }

        return i;
}

void geom_coord_revert(struct coord *c, int count)
{
        struct coord tmp;
        int i;

        for (i = 0; i < count / 2; i++)
        {
                tmp = c[i];
                c[i] = c[count - 1 - i];
                c[count - 1 - i] = tmp;
        }
}

long long geom_poly_area(struct coord *c, int count)
{
        long long area = 0;
        int i, j = 0;
#if 0
        fprintf(stderr,"count=%d\n",count);
#endif
        for (i = 0; i < count; i++)
        {
                if (++j == count)
                        j = 0;
#if 0
                fprintf(stderr,"(%d+%d)*(%d-%d)=%d*%d="LONGLONG_FMT"\n",c[i].x,c[j].x,c[i].y,c[j].y,c[i].x+c[j].x,c[i].y-c[j].y,(long long)(c[i].x+c[j].x)*(c[i].y-c[j].y));
#endif
                area += (long long) (c[i].x + c[j].x) * (c[i].y - c[j].y);
#if 0
                fprintf(stderr,"area="LONGLONG_FMT"\n",area);
#endif
        }
        return area / 2;
}

/**
  * Get poly centroid coordinates.
  * @param in *p array of poly vertex coordinates
  * @param in count count of poly vertexes
  * @param out *c coordinates of poly centroid
  * @returns 1 on success, 0 if poly area is 0

new version taken from mapnik source:
https://github.com/mapnik/mapnik/blob/master/include/mapnik/geometry.hpp
function:
label_position

  */
int
geom_poly_centroid(struct coord *p, int count, struct coord *c)
{
        int i;
        long long ox, oy, x0, y0, x1, y1;

        double ai;
        double atmp = 0;
        double xtmp = 0;
        double ytmp = 0;

    // Use first point as origin to improve numerical accuracy
        ox=p[0].x;
        oy=p[0].y;

    for (i = 0; i < count-1; i++)
    {
                x0=p[i].x;
                y0=p[i].y;
                x1=p[i+1].x;
                y1=p[i+1].y;

        x0 -= ox; y0 -= oy;
        x1 -= ox; y1 -= oy;

        ai = x0 * y1 - x1 * y0;
        atmp += ai;
        xtmp += (x1 + x0) * ai;
        ytmp += (y1 + y0) * ai;
    }

        if (atmp != 0)
        {
                c->x = (xtmp/(3*atmp)) + ox;
                c->y = (ytmp/(3*atmp)) + oy;
                return 1;
        }
        c->x = x0;
        c->y = y0;

        return 0;
}


/**
  * Get coordinates of polyline point c most close to given point p.
  * @param in *pl array of polyline vertex coordinates
  * @param in count count of polyline vertexes
  * @param in *p point coordinates 
  * @param out *c coordinates of polyline point most close to given point.
  * @returns first vertex number of polyline segment to which c belongs
  */
int
geom_poly_closest_point(struct coord *pl, int count, struct coord *p, struct coord *c)
{
        int i,vertex=0;
        long long x, y, xi, xj, yi, yj, u, d, dmin=0;
        if(count<2) {
                c->x=pl->x;
                c->y=pl->y;
                return 0;
        }
        for(i=0;i<count-1;i++) {
                xi=pl[i].x;
                yi=pl[i].y;
                xj=pl[i+1].x;
                yj=pl[i+1].y;
                u=(xj-xi)*(xj-xi)+(yj-yi)*(yj-yi);
                if(u!=0) {
                        u=((p->x-xi)*(xj-xi)+(p->y-yi)*(yj-yi))*1000/u;
                }
                if(u<0) 
                        u=0;
                else if (u>1000) 
                        u=1000;
                x=xi+u*(xj-xi)/1000;
                y=yi+u*(yj-yi)/1000;
                d=(p->x-x)*(p->x-x)+(p->y-y)*(p->y-y);
                if(i==0 || d<dmin) {
                        dmin=d;
                        c->x=x;
                        c->y=y;
                        vertex=i;
                }
        }
        return vertex;
}

/**
  * Check if point is inside polygon
  * @param in *cp array of polygon vertex coordinates
  * @param in count count of polygon vertexes
  * @param in *c point coordinates 
  * @returns 1 - inside, 0 - outside
  */
int
geom_poly_point_inside(struct coord *cp, int count, struct coord *c)
{
        int ret=0;
        struct coord *last=cp+count-1;
        while (cp < last)
        {
                if ((cp[0].y > c->y) != (cp[1].y > c->y) &&
                        c->x < ((long long)cp[1].x-cp[0].x)*(c->y-cp[0].y)/(cp[1].y-cp[0].y)+cp[0].x)
                {
#if 0
                        fprintf(stderr," cross 0x%x,0x%x-0x%x,0x%x %dx%d",cp,cp[0].x,cp[0].y,cp[1].x,cp[1].y,cp[1].x-cp[0].x,c->y-cp[0].y);
                        printf("type=selected_line\n");
                        coord_print(projection_mg, &cp[0], stdout);
                        coord_print(projection_mg, &cp[1], stdout);
#endif
                        ret=!ret;
                }
                cp++;
        }
        return ret;
}


GList *
geom_poly_segments_insert(GList *list, struct geom_poly_segment *first, struct geom_poly_segment *second, struct geom_poly_segment *third)
{
        int count;
        struct geom_poly_segment *ret;
        struct coord *pos;

        if (!second)
                return NULL; ret=g_new(struct geom_poly_segment, 1);
        ret->type = second->type;
        count = (second->last - second->first) + 1;
        if (first)
                count += (first->last - first->first);
        if (third)
                count += (third->last - third->first);
#if 0
        fprintf(stderr,"count=%d first=%p second=%p third=%p\n",count,first,second,third);
        if (first)
        fprintf(stderr,"first:0x%x,0x%x-0x%x,0x%x (%d)\n",first->first->x,first->first->y,first->last->x,first->last->y, first->last-first->first+1);
        if (second)
        fprintf(stderr,"second:0x%x,0x%x-0x%x,0x%x (%d)\n",second->first->x,second->first->y,second->last->x,second->last->y, second->last-second->first+1);
        if (third)
        fprintf(stderr,"third:0x%x,0x%x-0x%x,0x%x (%d)\n",third->first->x,third->first->y,third->last->x,third->last->y, third->last-third->first+1);
#endif
        ret->first=g_new(struct coord, count);
        pos = ret->first;
        if (first)
        {
                count = (first->last - first->first) + 1;
                geom_coord_copy(first->first, pos, count, coord_is_equal(*first->first, *second->first));
                pos += count - 1;
        }
        count = (second->last - second->first) + 1;
        geom_coord_copy(second->first, pos, count, 0);
        pos += count;
        if (third)
        {
                pos--;
                count = (third->last - third->first) + 1;
                geom_coord_copy(third->first, pos, count, coord_is_equal(*third->last, *second->last));
                pos += count;
        }
        ret->last = pos - 1;
#if 0
        fprintf(stderr,"result:0x%x,0x%x-0x%x,0x%x (%d)\n",ret->first->x,ret->first->y,ret->last->x,ret->last->y, ret->last-ret->first+1);
#endif
        list = g_list_prepend(list, ret);
#if 0
        fprintf(stderr,"List=%p\n",list);
#endif
        return list;
}

void geom_poly_segment_destroy(struct geom_poly_segment *seg)
{
        g_free(seg->first);
        g_free(seg);
}

GList *
geom_poly_segments_remove(GList *list, struct geom_poly_segment *seg)
{
        if (seg)
        {
                list = g_list_remove(list, seg);
                geom_poly_segment_destroy(seg);
        }
        return list;
}

int geom_poly_segment_compatible(struct geom_poly_segment *s1, struct geom_poly_segment *s2, int dir)
{
        int same = 0, opposite = 0;
        if (s1->type == geom_poly_segment_type_none || s2->type == geom_poly_segment_type_none)
                return 0;
        if (s1->type == s2->type)
        {
                same = 1;
                if (s1->type == geom_poly_segment_type_way_inner || s1->type == geom_poly_segment_type_way_outer)
                {
                        opposite = 1;
                }
        }
        if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side)
                opposite = 1;
        if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side)
                opposite = 1;
        if (s1->type == geom_poly_segment_type_way_unknown || s2->type == geom_poly_segment_type_way_unknown)
        {
                same = 1;
                opposite = 1;
        }
        if (dir < 0)
        {
                if ((opposite && coord_is_equal(*s1->first, *s2->first)) || (same && coord_is_equal(*s1->first, *s2->last)))
                        return 1;
        }
        else
        {
                if ((opposite && coord_is_equal(*s1->last, *s2->last)) || (same && coord_is_equal(*s1->last, *s2->first)))
                        return 1;
        }
        return 0;
}

GList *
geom_poly_segments_sort(GList *in, enum geom_poly_segment_type type)
{
        GList *ret = NULL;
        while (in)
        {
                struct geom_poly_segment *seg = in->data;
                GList *tmp = ret;
                struct geom_poly_segment *merge_first = NULL, *merge_last = NULL;
                while (tmp)
                {
                        struct geom_poly_segment *cseg = tmp->data;
                        if (geom_poly_segment_compatible(seg, cseg, -1))
                                merge_first = cseg;
                        if (geom_poly_segment_compatible(seg, cseg, 1))
                                merge_last = cseg;
                        tmp = g_list_next(tmp);
                }
                if (merge_first == merge_last)
                {
                        merge_last = NULL;
                }
                ret = geom_poly_segments_insert(ret, merge_first, seg, merge_last);
                ret = geom_poly_segments_remove(ret, merge_first);
                ret = geom_poly_segments_remove(ret, merge_last);
                in = g_list_next(in);
        }

        in = ret;
        while (in)
        {
                struct geom_poly_segment *seg = in->data;
                if (coord_is_equal(*seg->first, *seg->last))
                {
                        long long area = geom_poly_area(seg->first, seg->last - seg->first + 1);
                        if (type == geom_poly_segment_type_way_right_side && seg->type == geom_poly_segment_type_way_right_side)
                        {
                                seg->type = area > 0 ? geom_poly_segment_type_way_outer : geom_poly_segment_type_way_inner;
                        }
                }
                in = g_list_next(in);
        }
        return ret;
}

int geom_poly_segments_point_inside(GList *in, struct coord *c)
{
        int open_matches = 0, closed_matches = 0;
        struct coord *cp;

        //fprintf(stderr,"point: x=%d, y=%d\n",c->x,c->y);

        while (in)
        {
                struct geom_poly_segment *seg = in->data;
                cp = seg->first;

                //fprintf(stderr, "   seg x=%d, y=%d\n", seg->first[0].x, seg->first[0].y);

                if (geom_poly_point_inside(seg->first, seg->last - seg->first + 1, c))
                {
#if 0
                        fprintf(stderr," inside");
#endif
                        if (coord_is_equal(*seg->first, *seg->last))
                        {
                                closed_matches++;
                        }
                        else
                        {
                                open_matches++;
                        }
                }
                else
                {
#if 0
                        fprintf(stderr," outside");
#endif
                }
                in = g_list_next(in);
        }
#if 0
        fprintf(stderr,"\n");
        fprintf(stderr,"open_matches %d closed_matches %d\n",open_matches,closed_matches);
#endif
        if (closed_matches)
        {
                if (closed_matches & 1)
                        return 1;
                else
                        return 0;
        }
        if (open_matches)
        {
                if (open_matches & 1)
                        return -1;
                else
                        return 0;
        }
        return 0;
}

int
item_bin_is_closed_poly(struct item_bin *ib)
{
        // int is_closed_poly = 0;

        int i;
        int count = ib->clen / 2;
        if (count <= 1)
        {
                return 0;
        }

        struct coord *c = (struct coord *) (ib + 1);
        //for (i = 0; i < count; i++) // loop thru all the coordinates (nodes) of this way
        //{
        //}

        if ((c[0].x == c[count-1].x) && (c[0].y == c[count-1].y))
        {
                //fprintf(stderr,"%d,%d %d,%d\n", c[0].x,c[0].y,c[count-1].x,c[count-1].y);
                // is_closed_poly = 1;
                return 1;
        }
        //else
        //{
        //      //fprintf(stderr,"%d .. %d,%d %d,%d\n", count, c[0].x,c[0].y,c[count-1].x,c[count-1].y);
        //}

        // return is_closed_poly;
        return 0;
}

struct geom_poly_segment *
item_bin_to_poly_segment(struct item_bin *ib, int type)
{
        //fprintf(stderr,"item_bin_to_poly_segment:001\n");

        struct geom_poly_segment *ret=g_new(struct geom_poly_segment, 1);
        int count = ib->clen * sizeof(int) / sizeof(struct coord);

        //fprintf(stderr, "item id:%lld\n", item_bin_get_attr(ib, attr_osm_wayid, NULL));
        //fprintf(stderr,"item_bin_to_poly_segment:count=%d\n", ib->clen);

        ret->type = type;
        ret->first=g_new(struct coord, count);
        ret->last = ret->first + count - 1;

        //fprintf(stderr,"item_bin_to_poly_segment:002.f %d %d\n", ret->first->x, ret->first->y);
        //fprintf(stderr,"item_bin_to_poly_segment:002.l %d %d\n", ret->last->x, ret->last->y);

        //fprintf(stderr,"********DUMP***********\n");
        //dump_itembin(ib);
        //fprintf(stderr,"********DUMP***********\n");

        geom_coord_copy((struct coord *) (ib + 1), ret->first, count, 0);

        //fprintf(stderr,"item_bin_to_poly_segment:099\n");

        return ret;
}

static int clipcode(struct coord *p, struct rect *r)
{
        int code = 0;
        if (p->x < r->l.x)
                code = 1;
        if (p->x > r->h.x)
                code = 2;
        if (p->y < r->l.y)
                code |= 4;
        if (p->y > r->h.y)
                code |= 8;
        return code;
}

static int clip_line_code(struct coord *p1, struct coord *p2, struct rect *r)
{
        int code1, code2, ret = 1;
        long long dx, dy;
        code1 = clipcode(p1, r);
        if (code1)
                ret |= 2;
        code2 = clipcode(p2, r);
        if (code2)
                ret |= 4;
        dx = p2->x - p1->x;
        dy = p2->y - p1->y;
        while (code1 || code2)
        {
                if (code1 & code2)
                        return 0;
                if (code1 & 1)
                {
                        p1->y += (r->l.x - p1->x) * dy / dx;
                        p1->x = r->l.x;
                }
                else if (code1 & 2)
                {
                        p1->y += (r->h.x - p1->x) * dy / dx;
                        p1->x = r->h.x;
                }
                else if (code1 & 4)
                {
                        p1->x += (r->l.y - p1->y) * dx / dy;
                        p1->y = r->l.y;
                }
                else if (code1 & 8)
                {
                        p1->x += (r->h.y - p1->y) * dx / dy;
                        p1->y = r->h.y;
                }
                code1 = clipcode(p1, r);
                if (code1 & code2)
                        return 0;
                if (code2 & 1)
                {
                        p2->y += (r->l.x - p2->x) * dy / dx;
                        p2->x = r->l.x;
                }
                else if (code2 & 2)
                {
                        p2->y += (r->h.x - p2->x) * dy / dx;
                        p2->x = r->h.x;
                }
                else if (code2 & 4)
                {
                        p2->x += (r->l.y - p2->y) * dx / dy;
                        p2->y = r->l.y;
                }
                else if (code2 & 8)
                {
                        p2->x += (r->h.y - p2->y) * dx / dy;
                        p2->y = r->h.y;
                }
                code2 = clipcode(p2, r);
        }
        if (p1->x == p2->x && p1->y == p2->y)
                ret = 0;
        return ret;
}

void clip_line(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
{
        char *buffer = g_alloca(sizeof(char) * (ib->len * 4 + 32));
        struct item_bin *ib_new = (struct item_bin *) buffer;
        struct coord *pa = (struct coord *) (ib + 1);
        int count = ib->clen / 2;
        struct coord p1, p2;
        int i, code;
        item_bin_init(ib_new, ib->type);
        for (i = 0; i < count; i++)
        {
                if (i)
                {
                        p1.x = pa[i - 1].x;
                        p1.y = pa[i - 1].y;
                        p2.x = pa[i].x;
                        p2.y = pa[i].y;
                        /* 0 = invisible, 1 = completely visible, 3 = start point clipped, 5 = end point clipped, 7 both points clipped */
                        code = clip_line_code(&p1, &p2, r);
#if 1
                        if (((code == 1 || code == 5) && ib_new->clen == 0) || (code & 2))
                        {
                                item_bin_add_coord(ib_new, &p1, 1);
                        }
                        if (code)
                        {
                                item_bin_add_coord(ib_new, &p2, 1);
                        }
                        if (i == count - 1 || (code & 4))
                        {
                                if (ib_new->clen)
                                        item_bin_write_clipped(ib_new, param, out);
                                item_bin_init(ib_new, ib->type);
                        }
#else
                        if (code)
                        {
                                item_bin_init(ib_new, ib->type);
                                item_bin_add_coord(ib_new, &p1, 1);
                                item_bin_add_coord(ib_new, &p2, 1);
                                item_bin_write_clipped(ib_new, param, out);
                        }
#endif
                }
        }
}

static int is_inside(struct coord *p, struct rect *r, int edge)
{
        switch (edge)
        {
                case 0:
                        return p->x >= r->l.x;
                case 1:
                        return p->x <= r->h.x;
                case 2:
                        return p->y >= r->l.y;
                case 3:
                        return p->y <= r->h.y;
                default:
                        return 0;
        }
}

static void poly_intersection(struct coord *p1, struct coord *p2, struct rect *r, int edge, struct coord *ret)
{
        int dx = p2->x - p1->x;
        int dy = p2->y - p1->y;
        switch (edge)
        {
                case 0:
                        ret->y = p1->y + (r->l.x - p1->x) * dy / dx;
                        ret->x = r->l.x;
                        break;
                case 1:
                        ret->y = p1->y + (r->h.x - p1->x) * dy / dx;
                        ret->x = r->h.x;
                        break;
                case 2:
                        ret->x = p1->x + (r->l.y - p1->y) * dx / dy;
                        ret->y = r->l.y;
                        break;
                case 3:
                        ret->x = p1->x + (r->h.y - p1->y) * dx / dy;
                        ret->y = r->h.y;
                        break;
        }
}

void clip_polygon(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
{
        int count_in = ib->clen / 2;
        struct coord *pin, *p, *s, pi;
        char *buffer1 = g_alloca(sizeof(char) * (ib->len * 4 + ib->clen * 7 + 32));
        struct item_bin *ib1 = (struct item_bin *) buffer1;
        char *buffer2 = g_alloca(sizeof(char) * (ib->len * 4 + ib->clen * 7 + 32));
        struct item_bin *ib2 = (struct item_bin *) buffer2;
        struct item_bin *ib_in, *ib_out;
        int edge, i;
        ib_out = ib1;
        ib_in = ib;
        for (edge = 0; edge < 4; edge++)
        {
                count_in = ib_in->clen / 2;
                pin = (struct coord *) (ib_in + 1);
                p = pin;
                s = pin + count_in - 1;
                item_bin_init(ib_out, ib_in->type);
                for (i = 0; i < count_in; i++)
                {
                        if (is_inside(p, r, edge))
                        {
                                if (!is_inside(s, r, edge))
                                {
                                        poly_intersection(s, p, r, edge, &pi);
                                        item_bin_add_coord(ib_out, &pi, 1);
                                }
                                item_bin_add_coord(ib_out, p, 1);
                        }
                        else
                        {
                                if (is_inside(s, r, edge))
                                {
                                        poly_intersection(p, s, r, edge, &pi);
                                        item_bin_add_coord(ib_out, &pi, 1);
                                }
                        }
                        s = p;
                        p++;
                }
                if (ib_in == ib1)
                {
                        ib_in = ib2;
                        ib_out = ib1;
                }
                else
                {
                        ib_in = ib1;
                        ib_out = ib2;
                }
        }
        if (ib_in->clen)
                item_bin_write_clipped(ib_in, param, out);
}

1	zoff99	8	/**
2	zoff99	31	* ZANavi, Zoff Android Navigation system.
3			* Copyright (C) 2011-2012 Zoff <zoff@zoff.cc>
4			*
5			* This program is free software; you can redistribute it and/or
6			* modify it under the terms of the GNU General Public License
7			* version 2 as published by the Free Software Foundation.
8			*
9			* This program is distributed in the hope that it will be useful,
10			* but WITHOUT ANY WARRANTY; without even the implied warranty of
11			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12			* GNU General Public License for more details.
13			*
14			* You should have received a copy of the GNU General Public License
15			* along with this program; if not, write to the
16			* Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17			* Boston, MA 02110-1301, USA.
18			*/
19
20			/**
21	zoff99	8	* Navit, a modular navigation system.
22			* Copyright (C) 2005-2011 Navit Team
23			*
24			* This program is free software; you can redistribute it and/or
25			* modify it under the terms of the GNU General Public License
26			* version 2 as published by the Free Software Foundation.
27			*
28			* This program is distributed in the hope that it will be useful,
29			* but WITHOUT ANY WARRANTY; without even the implied warranty of
30			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31			* GNU General Public License for more details.
32			*
33			* You should have received a copy of the GNU General Public License
34			* along with this program; if not, write to the
35			* Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
36			* Boston, MA 02110-1301, USA.
37			*/
38			#include <string.h>
39	zoff99	31	#include <math.h>
40	zoff99	8	#include "maptool.h"
41
42	zoff99	31	void geom_coord_copy(struct coord from, struct coord to, int count, int reverse)
43	zoff99	8	{
44			int i;
45	zoff99	31	if (!reverse)
46			{
47			memcpy(to, from, count * sizeof(struct coord));
48	zoff99	8	return;
49			}
50	zoff99	31	from += count;
51			for (i = 0; i < count; i++)
52			{
53			to++ = --from;
54			}
55	zoff99	8	}
56
57	zoff99	31
58			/**
59			* Get coordinates of polyline middle point.
60			* @param in *p array of poly vertex coordinates
61			* @param in count count of poly vertexes
62			* @param out *c coordinates of middle point
63			* @returns number of first vertex of segment containing middle point
64			*/
65			int geom_line_middle(struct coord p, int count, struct coord c)
66	zoff99	8	{
67	zoff99	31	double length = 0, half = 0, len = 0;
68			int i;
69
70			if (count == 1)
71			{
72			c=p;
73			return 0;
74			}
75
76			for (i=0; i<count-1; i++)
77			{
78			length+=sqrt(sq(p[i].x-p[i+1].x)+sq(p[i].y-p[i+1].y));
79			}
80
81			length /= 2;
82			for (i=0; (i<count-1) && (half<length); i++)
83			{
84			len=sqrt(sq(p[i].x-p[i+1].x)+sq(p[i].y-p[i+1].y));
85			half += len;
86			}
87
88			if (i > 0)
89			{
90			i--;
91			half -= length;
92			if (len)
93			{
94			c->x=(p[i].xhalf+p[i+1].x(len-half))/len;
95			c->y=(p[i].yhalf+p[i+1].y(len-half))/len;
96			}
97			else
98			{
99			*c = p[i];
100			}
101			}
102			else
103			{
104			*c = p[0];
105			}
106
107			return i;
108			}
109
110			void geom_coord_revert(struct coord *c, int count)
111			{
112	zoff99	8	struct coord tmp;
113			int i;
114
115	zoff99	31	for (i = 0; i < count / 2; i++)
116			{
117			tmp = c[i];
118			c[i] = c[count - 1 - i];
119			c[count - 1 - i] = tmp;
120	zoff99	8	}
121			}
122
123	zoff99	31	long long geom_poly_area(struct coord *c, int count)
124	zoff99	8	{
125	zoff99	31	long long area = 0;
126			int i, j = 0;
127	zoff99	8	#if 0
128			fprintf(stderr,"count=%d\n",count);
129			#endif
130	zoff99	31	for (i = 0; i < count; i++)
131			{
132	zoff99	8	if (++j == count)
133	zoff99	31	j = 0;
134	zoff99	8	#if 0
135			fprintf(stderr,"(%d+%d)(%d-%d)=%d%d="LONGLONG_FMT"\n",c[i].x,c[j].x,c[i].y,c[j].y,c[i].x+c[j].x,c[i].y-c[j].y,(long long)(c[i].x+c[j].x)*(c[i].y-c[j].y));
136			#endif
137	zoff99	31	area += (long long) (c[i].x + c[j].x) * (c[i].y - c[j].y);
138	zoff99	8	#if 0
139			fprintf(stderr,"area="LONGLONG_FMT"\n",area);
140			#endif
141			}
142	zoff99	31	return area / 2;
143	zoff99	8	}
144
145	zoff99	31	/**
146			* Get poly centroid coordinates.
147			* @param in *p array of poly vertex coordinates
148			* @param in count count of poly vertexes
149			* @param out *c coordinates of poly centroid
150			* @returns 1 on success, 0 if poly area is 0
151
152			new version taken from mapnik source:
153			https://github.com/mapnik/mapnik/blob/master/include/mapnik/geometry.hpp
154			function:
155			label_position
156
157			*/
158			int
159			geom_poly_centroid(struct coord p, int count, struct coord c)
160			{
161			int i;
162			long long ox, oy, x0, y0, x1, y1;
163
164			double ai;
165			double atmp = 0;
166			double xtmp = 0;
167			double ytmp = 0;
168
169			// Use first point as origin to improve numerical accuracy
170			ox=p[0].x;
171			oy=p[0].y;
172
173			for (i = 0; i < count-1; i++)
174			{
175			x0=p[i].x;
176			y0=p[i].y;
177			x1=p[i+1].x;
178			y1=p[i+1].y;
179
180			x0 -= ox; y0 -= oy;
181			x1 -= ox; y1 -= oy;
182
183			ai = x0 * y1 - x1 * y0;
184			atmp += ai;
185			xtmp += (x1 + x0) * ai;
186			ytmp += (y1 + y0) * ai;
187			}
188
189			if (atmp != 0)
190			{
191			c->x = (xtmp/(3*atmp)) + ox;
192			c->y = (ytmp/(3*atmp)) + oy;
193			return 1;
194			}
195			c->x = x0;
196			c->y = y0;
197
198			return 0;
199			}
200
201
202			/**
203			* Get coordinates of polyline point c most close to given point p.
204			* @param in *pl array of polyline vertex coordinates
205			* @param in count count of polyline vertexes
206			* @param in *p point coordinates
207			* @param out *c coordinates of polyline point most close to given point.
208			* @returns first vertex number of polyline segment to which c belongs
209			*/
210			int
211			geom_poly_closest_point(struct coord pl, int count, struct coord p, struct coord *c)
212			{
213			int i,vertex=0;
214			long long x, y, xi, xj, yi, yj, u, d, dmin=0;
215			if(count<2) {
216			c->x=pl->x;
217			c->y=pl->y;
218			return 0;
219			}
220			for(i=0;i<count-1;i++) {
221			xi=pl[i].x;
222			yi=pl[i].y;
223			xj=pl[i+1].x;
224			yj=pl[i+1].y;
225			u=(xj-xi)(xj-xi)+(yj-yi)(yj-yi);
226			if(u!=0) {
227			u=((p->x-xi)(xj-xi)+(p->y-yi)(yj-yi))*1000/u;
228			}
229			if(u<0)
230			u=0;
231			else if (u>1000)
232			u=1000;
233			x=xi+u*(xj-xi)/1000;
234			y=yi+u*(yj-yi)/1000;
235			d=(p->x-x)(p->x-x)+(p->y-y)(p->y-y);
236			if(i==0 \|\| d<dmin) {
237			dmin=d;
238			c->x=x;
239			c->y=y;
240			vertex=i;
241			}
242			}
243			return vertex;
244			}
245
246			/**
247			* Check if point is inside polygon
248			* @param in *cp array of polygon vertex coordinates
249			* @param in count count of polygon vertexes
250			* @param in *c point coordinates
251			* @returns 1 - inside, 0 - outside
252			*/
253			int
254			geom_poly_point_inside(struct coord cp, int count, struct coord c)
255			{
256			int ret=0;
257			struct coord *last=cp+count-1;
258			while (cp < last)
259			{
260			if ((cp[0].y > c->y) != (cp[1].y > c->y) &&
261			c->x < ((long long)cp[1].x-cp[0].x)*(c->y-cp[0].y)/(cp[1].y-cp[0].y)+cp[0].x)
262			{
263			#if 0
264			fprintf(stderr," cross 0x%x,0x%x-0x%x,0x%x %dx%d",cp,cp[0].x,cp[0].y,cp[1].x,cp[1].y,cp[1].x-cp[0].x,c->y-cp[0].y);
265			printf("type=selected_line\n");
266			coord_print(projection_mg, &cp[0], stdout);
267			coord_print(projection_mg, &cp[1], stdout);
268			#endif
269			ret=!ret;
270			}
271			cp++;
272			}
273			return ret;
274			}
275
276
277	zoff99	8	GList *
278			geom_poly_segments_insert(GList list, struct geom_poly_segment first, struct geom_poly_segment second, struct geom_poly_segment third)
279			{
280			int count;
281			struct geom_poly_segment *ret;
282			struct coord *pos;
283
284			if (!second)
285	zoff99	31	return NULL; ret=g_new(struct geom_poly_segment, 1);
286			ret->type = second->type;
287			count = (second->last - second->first) + 1;
288			if (first)
289			count += (first->last - first->first);
290	zoff99	8	if (third)
291	zoff99	31	count += (third->last - third->first);
292	zoff99	8	#if 0
293	zoff99	31	fprintf(stderr,"count=%d first=%p second=%p third=%p\n",count,first,second,third);
294			if (first)
295			fprintf(stderr,"first:0x%x,0x%x-0x%x,0x%x (%d)\n",first->first->x,first->first->y,first->last->x,first->last->y, first->last-first->first+1);
296			if (second)
297			fprintf(stderr,"second:0x%x,0x%x-0x%x,0x%x (%d)\n",second->first->x,second->first->y,second->last->x,second->last->y, second->last-second->first+1);
298			if (third)
299			fprintf(stderr,"third:0x%x,0x%x-0x%x,0x%x (%d)\n",third->first->x,third->first->y,third->last->x,third->last->y, third->last-third->first+1);
300	zoff99	8	#endif
301			ret->first=g_new(struct coord, count);
302	zoff99	31	pos = ret->first;
303			if (first)
304			{
305			count = (first->last - first->first) + 1;
306	zoff99	8	geom_coord_copy(first->first, pos, count, coord_is_equal(first->first, second->first));
307	zoff99	31	pos += count - 1;
308	zoff99	8	}
309	zoff99	31	count = (second->last - second->first) + 1;
310	zoff99	8	geom_coord_copy(second->first, pos, count, 0);
311	zoff99	31	pos += count;
312			if (third)
313			{
314	zoff99	8	pos--;
315	zoff99	31	count = (third->last - third->first) + 1;
316	zoff99	8	geom_coord_copy(third->first, pos, count, coord_is_equal(third->last, second->last));
317	zoff99	31	pos += count;
318	zoff99	8	}
319	zoff99	31	ret->last = pos - 1;
320	zoff99	8	#if 0
321			fprintf(stderr,"result:0x%x,0x%x-0x%x,0x%x (%d)\n",ret->first->x,ret->first->y,ret->last->x,ret->last->y, ret->last-ret->first+1);
322			#endif
323	zoff99	31	list = g_list_prepend(list, ret);
324	zoff99	8	#if 0
325			fprintf(stderr,"List=%p\n",list);
326			#endif
327			return list;
328			}
329
330	zoff99	31	void geom_poly_segment_destroy(struct geom_poly_segment *seg)
331	zoff99	8	{
332			g_free(seg->first);
333			g_free(seg);
334			}
335
336			GList *
337			geom_poly_segments_remove(GList list, struct geom_poly_segment seg)
338			{
339	zoff99	31	if (seg)
340			{
341			list = g_list_remove(list, seg);
342	zoff99	8	geom_poly_segment_destroy(seg);
343			}
344			return list;
345			}
346
347	zoff99	31	int geom_poly_segment_compatible(struct geom_poly_segment s1, struct geom_poly_segment s2, int dir)
348	zoff99	8	{
349	zoff99	31	int same = 0, opposite = 0;
350	zoff99	8	if (s1->type == geom_poly_segment_type_none \|\| s2->type == geom_poly_segment_type_none)
351			return 0;
352			if (s1->type == s2->type)
353	zoff99	31	{
354			same = 1;
355			if (s1->type == geom_poly_segment_type_way_inner \|\| s1->type == geom_poly_segment_type_way_outer)
356			{
357			opposite = 1;
358			}
359			}
360	zoff99	8	if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side)
361	zoff99	31	opposite = 1;
362	zoff99	8	if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side)
363	zoff99	31	opposite = 1;
364			if (s1->type == geom_poly_segment_type_way_unknown \|\| s2->type == geom_poly_segment_type_way_unknown)
365			{
366			same = 1;
367			opposite = 1;
368	zoff99	8	}
369	zoff99	31	if (dir < 0)
370			{
371			if ((opposite && coord_is_equal(s1->first, s2->first)) \|\| (same && coord_is_equal(s1->first, s2->last)))
372	zoff99	8	return 1;
373	zoff99	31	}
374			else
375			{
376			if ((opposite && coord_is_equal(s1->last, s2->last)) \|\| (same && coord_is_equal(s1->last, s2->first)))
377	zoff99	8	return 1;
378			}
379			return 0;
380			}
381
382			GList *
383			geom_poly_segments_sort(GList *in, enum geom_poly_segment_type type)
384			{
385	zoff99	31	GList *ret = NULL;
386			while (in)
387			{
388			struct geom_poly_segment *seg = in->data;
389			GList *tmp = ret;
390			struct geom_poly_segment merge_first = NULL, merge_last = NULL;
391			while (tmp)
392			{
393			struct geom_poly_segment *cseg = tmp->data;
394	zoff99	8	if (geom_poly_segment_compatible(seg, cseg, -1))
395	zoff99	31	merge_first = cseg;
396	zoff99	8	if (geom_poly_segment_compatible(seg, cseg, 1))
397	zoff99	31	merge_last = cseg;
398			tmp = g_list_next(tmp);
399	zoff99	8	}
400			if (merge_first == merge_last)
401	zoff99	31	{
402			merge_last = NULL;
403			}
404			ret = geom_poly_segments_insert(ret, merge_first, seg, merge_last);
405			ret = geom_poly_segments_remove(ret, merge_first);
406			ret = geom_poly_segments_remove(ret, merge_last);
407			in = g_list_next(in);
408	zoff99	8	}
409	zoff99	31
410			in = ret;
411			while (in)
412			{
413			struct geom_poly_segment *seg = in->data;
414			if (coord_is_equal(seg->first, seg->last))
415			{
416			long long area = geom_poly_area(seg->first, seg->last - seg->first + 1);
417			if (type == geom_poly_segment_type_way_right_side && seg->type == geom_poly_segment_type_way_right_side)
418			{
419			seg->type = area > 0 ? geom_poly_segment_type_way_outer : geom_poly_segment_type_way_inner;
420	zoff99	8	}
421			}
422	zoff99	31	in = g_list_next(in);
423	zoff99	8	}
424			return ret;
425			}
426
427	zoff99	31	int geom_poly_segments_point_inside(GList in, struct coord c)
428	zoff99	8	{
429	zoff99	31	int open_matches = 0, closed_matches = 0;
430	zoff99	8	struct coord *cp;
431	zoff99	31
432			//fprintf(stderr,"point: x=%d, y=%d\n",c->x,c->y);
433
434			while (in)
435			{
436			struct geom_poly_segment *seg = in->data;
437			cp = seg->first;
438
439			//fprintf(stderr, " seg x=%d, y=%d\n", seg->first[0].x, seg->first[0].y);
440
441			if (geom_poly_point_inside(seg->first, seg->last - seg->first + 1, c))
442			{
443			#if 0
444			fprintf(stderr," inside");
445			#endif
446			if (coord_is_equal(seg->first, seg->last))
447			{
448			closed_matches++;
449			}
450			else
451			{
452			open_matches++;
453			}
454	zoff99	8	}
455	zoff99	31	else
456			{
457			#if 0
458			fprintf(stderr," outside");
459			#endif
460			}
461			in = g_list_next(in);
462	zoff99	8	}
463	zoff99	31	#if 0
464			fprintf(stderr,"\n");
465			fprintf(stderr,"open_matches %d closed_matches %d\n",open_matches,closed_matches);
466			#endif
467			if (closed_matches)
468			{
469			if (closed_matches & 1)
470			return 1;
471			else
472			return 0;
473			}
474			if (open_matches)
475			{
476			if (open_matches & 1)
477			return -1;
478			else
479			return 0;
480			}
481			return 0;
482	zoff99	8	}
483
484	zoff99	31	int
485			item_bin_is_closed_poly(struct item_bin *ib)
486			{
487			// int is_closed_poly = 0;
488
489			int i;
490			int count = ib->clen / 2;
491			if (count <= 1)
492			{
493			return 0;
494			}
495
496			struct coord c = (struct coord ) (ib + 1);
497			//for (i = 0; i < count; i++) // loop thru all the coordinates (nodes) of this way
498			//{
499			//}
500
501			if ((c[0].x == c[count-1].x) && (c[0].y == c[count-1].y))
502			{
503			//fprintf(stderr,"%d,%d %d,%d\n", c[0].x,c[0].y,c[count-1].x,c[count-1].y);
504			// is_closed_poly = 1;
505			return 1;
506			}
507			//else
508			//{
509			// //fprintf(stderr,"%d .. %d,%d %d,%d\n", count, c[0].x,c[0].y,c[count-1].x,c[count-1].y);
510			//}
511
512			// return is_closed_poly;
513			return 0;
514			}
515
516	zoff99	8	struct geom_poly_segment *
517			item_bin_to_poly_segment(struct item_bin *ib, int type)
518			{
519	zoff99	31	//fprintf(stderr,"item_bin_to_poly_segment:001\n");
520
521	zoff99	8	struct geom_poly_segment *ret=g_new(struct geom_poly_segment, 1);
522	zoff99	31	int count = ib->clen * sizeof(int) / sizeof(struct coord);
523
524			//fprintf(stderr, "item id:%lld\n", item_bin_get_attr(ib, attr_osm_wayid, NULL));
525			//fprintf(stderr,"item_bin_to_poly_segment:count=%d\n", ib->clen);
526
527			ret->type = type;
528	zoff99	8	ret->first=g_new(struct coord, count);
529	zoff99	31	ret->last = ret->first + count - 1;
530
531			//fprintf(stderr,"item_bin_to_poly_segment:002.f %d %d\n", ret->first->x, ret->first->y);
532			//fprintf(stderr,"item_bin_to_poly_segment:002.l %d %d\n", ret->last->x, ret->last->y);
533
534			//fprintf(stderr,"******DUMP*********\n");
535			//dump_itembin(ib);
536			//fprintf(stderr,"******DUMP*********\n");
537
538			geom_coord_copy((struct coord *) (ib + 1), ret->first, count, 0);
539
540			//fprintf(stderr,"item_bin_to_poly_segment:099\n");
541
542	zoff99	8	return ret;
543			}
544
545	zoff99	31	static int clipcode(struct coord p, struct rect r)
546	zoff99	8	{
547	zoff99	31	int code = 0;
548	zoff99	8	if (p->x < r->l.x)
549	zoff99	31	code = 1;
550	zoff99	8	if (p->x > r->h.x)
551	zoff99	31	code = 2;
552	zoff99	8	if (p->y < r->l.y)
553	zoff99	31	code \|= 4;
554	zoff99	8	if (p->y > r->h.y)
555	zoff99	31	code \|= 8;
556	zoff99	8	return code;
557			}
558
559	zoff99	31	static int clip_line_code(struct coord p1, struct coord p2, struct rect *r)
560	zoff99	8	{
561	zoff99	31	int code1, code2, ret = 1;
562			long long dx, dy;
563			code1 = clipcode(p1, r);
564	zoff99	8	if (code1)
565			ret \|= 2;
566	zoff99	31	code2 = clipcode(p2, r);
567	zoff99	8	if (code2)
568			ret \|= 4;
569	zoff99	31	dx = p2->x - p1->x;
570			dy = p2->y - p1->y;
571			while (code1 \|\| code2)
572			{
573	zoff99	8	if (code1 & code2)
574			return 0;
575	zoff99	31	if (code1 & 1)
576			{
577			p1->y += (r->l.x - p1->x) * dy / dx;
578			p1->x = r->l.x;
579	zoff99	8	}
580	zoff99	31	else if (code1 & 2)
581			{
582			p1->y += (r->h.x - p1->x) * dy / dx;
583			p1->x = r->h.x;
584			}
585			else if (code1 & 4)
586			{
587			p1->x += (r->l.y - p1->y) * dx / dy;
588			p1->y = r->l.y;
589			}
590			else if (code1 & 8)
591			{
592			p1->x += (r->h.y - p1->y) * dx / dy;
593			p1->y = r->h.y;
594			}
595			code1 = clipcode(p1, r);
596	zoff99	8	if (code1 & code2)
597			return 0;
598	zoff99	31	if (code2 & 1)
599			{
600			p2->y += (r->l.x - p2->x) * dy / dx;
601			p2->x = r->l.x;
602	zoff99	8	}
603	zoff99	31	else if (code2 & 2)
604			{
605			p2->y += (r->h.x - p2->x) * dy / dx;
606			p2->x = r->h.x;
607			}
608			else if (code2 & 4)
609			{
610			p2->x += (r->l.y - p2->y) * dx / dy;
611			p2->y = r->l.y;
612			}
613			else if (code2 & 8)
614			{
615			p2->x += (r->h.y - p2->y) * dx / dy;
616			p2->y = r->h.y;
617			}
618			code2 = clipcode(p2, r);
619	zoff99	8	}
620			if (p1->x == p2->x && p1->y == p2->y)
621	zoff99	31	ret = 0;
622	zoff99	8	return ret;
623			}
624
625	zoff99	31	void clip_line(struct item_bin ib, struct rect r, struct tile_parameter param, struct item_bin_sink out)
626	zoff99	8	{
627	zoff99	31	char buffer = g_alloca(sizeof(char) (ib->len * 4 + 32));
628			struct item_bin ib_new = (struct item_bin ) buffer;
629			struct coord pa = (struct coord ) (ib + 1);
630			int count = ib->clen / 2;
631			struct coord p1, p2;
632			int i, code;
633	zoff99	8	item_bin_init(ib_new, ib->type);
634	zoff99	31	for (i = 0; i < count; i++)
635			{
636			if (i)
637			{
638			p1.x = pa[i - 1].x;
639			p1.y = pa[i - 1].y;
640			p2.x = pa[i].x;
641			p2.y = pa[i].y;
642	zoff99	8	/* 0 = invisible, 1 = completely visible, 3 = start point clipped, 5 = end point clipped, 7 both points clipped */
643	zoff99	31	code = clip_line_code(&p1, &p2, r);
644	zoff99	8	#if 1
645	zoff99	31	if (((code == 1 \|\| code == 5) && ib_new->clen == 0) \|\| (code & 2))
646			{
647	zoff99	8	item_bin_add_coord(ib_new, &p1, 1);
648			}
649	zoff99	31	if (code)
650			{
651	zoff99	8	item_bin_add_coord(ib_new, &p2, 1);
652			}
653	zoff99	31	if (i == count - 1 \|\| (code & 4))
654			{
655	zoff99	8	if (ib_new->clen)
656			item_bin_write_clipped(ib_new, param, out);
657			item_bin_init(ib_new, ib->type);
658			}
659			#else
660	zoff99	31	if (code)
661			{
662	zoff99	8	item_bin_init(ib_new, ib->type);
663			item_bin_add_coord(ib_new, &p1, 1);
664			item_bin_add_coord(ib_new, &p2, 1);
665			item_bin_write_clipped(ib_new, param, out);
666			}
667			#endif
668			}
669			}
670			}
671
672	zoff99	31	static int is_inside(struct coord p, struct rect r, int edge)
673	zoff99	8	{
674	zoff99	31	switch (edge)
675			{
676			case 0:
677			return p->x >= r->l.x;
678			case 1:
679			return p->x <= r->h.x;
680			case 2:
681			return p->y >= r->l.y;
682			case 3:
683			return p->y <= r->h.y;
684			default:
685			return 0;
686	zoff99	8	}
687			}
688
689	zoff99	31	static void poly_intersection(struct coord p1, struct coord p2, struct rect r, int edge, struct coord ret)
690	zoff99	8	{
691	zoff99	31	int dx = p2->x - p1->x;
692			int dy = p2->y - p1->y;
693			switch (edge)
694			{
695			case 0:
696			ret->y = p1->y + (r->l.x - p1->x) * dy / dx;
697			ret->x = r->l.x;
698			break;
699			case 1:
700			ret->y = p1->y + (r->h.x - p1->x) * dy / dx;
701			ret->x = r->h.x;
702			break;
703			case 2:
704			ret->x = p1->x + (r->l.y - p1->y) * dx / dy;
705			ret->y = r->l.y;
706			break;
707			case 3:
708			ret->x = p1->x + (r->h.y - p1->y) * dx / dy;
709			ret->y = r->h.y;
710			break;
711	zoff99	8	}
712			}
713
714	zoff99	31	void clip_polygon(struct item_bin ib, struct rect r, struct tile_parameter param, struct item_bin_sink out)
715	zoff99	8	{
716	zoff99	31	int count_in = ib->clen / 2;
717			struct coord pin, p, *s, pi;
718			char buffer1 = g_alloca(sizeof(char) (ib->len * 4 + ib->clen * 7 + 32));
719			struct item_bin ib1 = (struct item_bin ) buffer1;
720			char buffer2 = g_alloca(sizeof(char) (ib->len * 4 + ib->clen * 7 + 32));
721			struct item_bin ib2 = (struct item_bin ) buffer2;
722			struct item_bin ib_in, ib_out;
723			int edge, i;
724			ib_out = ib1;
725			ib_in = ib;
726			for (edge = 0; edge < 4; edge++)
727			{
728			count_in = ib_in->clen / 2;
729			pin = (struct coord *) (ib_in + 1);
730			p = pin;
731			s = pin + count_in - 1;
732	zoff99	8	item_bin_init(ib_out, ib_in->type);
733	zoff99	31	for (i = 0; i < count_in; i++)
734			{
735			if (is_inside(p, r, edge))
736			{
737			if (!is_inside(s, r, edge))
738			{
739			poly_intersection(s, p, r, edge, &pi);
740	zoff99	8	item_bin_add_coord(ib_out, &pi, 1);
741			}
742			item_bin_add_coord(ib_out, p, 1);
743	zoff99	31	}
744			else
745			{
746			if (is_inside(s, r, edge))
747			{
748			poly_intersection(p, s, r, edge, &pi);
749	zoff99	8	item_bin_add_coord(ib_out, &pi, 1);
750			}
751			}
752	zoff99	31	s = p;
753	zoff99	8	p++;
754			}
755	zoff99	31	if (ib_in == ib1)
756			{
757			ib_in = ib2;
758			ib_out = ib1;
759	zoff99	8	}
760	zoff99	31	else
761			{
762			ib_in = ib1;
763			ib_out = ib2;
764			}
765	zoff99	8	}
766			if (ib_in->clen)
767			item_bin_write_clipped(ib_in, param, out);
768			}
769	zoff99	31