src/lib/gpc.cpp

//
// AutoCoast: Automatic Coastline scenery generator for Flight Simulator
//
// Copyright (c) 2004, Takuya Murakami. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
//
// 1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// gpc.cc : GPC wrapper

#include <stdio.h>
#include <math.h>

#include "gpc.hpp"
#include "vector.hpp"

GpcVertexList::GpcVertexList(void)
{
        vlist = NULL;
        ownVlistMemory = true;
}

GpcVertexList::GpcVertexList(int n, gpc_vertex *vertex)
{
        vlist = new gpc_vertex_list;
        vlist->num_vertices = n;

        if (n == 0) {
                vlist->vertex = NULL;
        } else {
                vlist->vertex = new gpc_vertex[n];
                if (vertex) {
                        for (int i = 0; i < n; i++) {
                                vlist->vertex[i] = vertex[i];
                        }
                }
        }

        ownVlistMemory = true;
}

GpcVertexList::GpcVertexList(gpc_vertex_list *v)
{
        vlist = v;
        ownVlistMemory = false;
}

GpcVertexList::~GpcVertexList()
{
        if (ownVlistMemory && vlist) {
                if (vlist->vertex) {
                        delete [] vlist->vertex;
                }
                delete vlist;
        }

        vlist = NULL;
}

//
// Modify initial vertex to the edge on BoundingBox.
//
void GpcVertexList::modifyStartPointFromEdge(BoundingBox &bbox)
{
        check();

        int n = vlist->num_vertices;
        int i, j;

        int prev;
        int flags;
        int startPoint = -1;

        prev = bbox.checkEdge(vx(n-1), vy(n-1));
        for (i = 0; i < n; i++) {
                flags = bbox.checkEdge(vx(i), vy(i));

                // Leaved from edge?
                if ((prev & ~flags) != 0 &&
                    (prev & flags) == 0) {
                        if (i == 0) {
                                startPoint = n - 1;
                        } else {
                                startPoint = i - 1;
                        }
                        break;
                }
                prev = flags;
        }

        if (startPoint < 0) {
                // No start point. Do nothing.
                return;
        }

        // Copy data
        gpc_vertex *tmp = new gpc_vertex[n];
        for (i = 0, j = startPoint; i < n; i++, j++) {
                if (j >= n) j = j - n;

                tmp[i] = vlist->vertex[j];
        }

        memcpy(vlist->vertex, tmp, sizeof(gpc_vertex) * n);
        delete [] tmp;
}

void GpcVertexList::invert(void)
{
        check();

        int n = vlist->num_vertices;
        gpc_vertex tmp;

        for (int i = 0; i < n / 2; i++) {
                tmp = vlist->vertex[i];
                vlist->vertex[i] = vlist->vertex[n - 1 - i];
                vlist->vertex[n - 1 - i] = tmp;
        }
}

//
// Check drawing order
//
bool GpcVertexList::isLeftHand(void)
{
        int n = vlist->num_vertices;

        Vector v1, v2;

        double deg, total_deg = 0.0;

        // calculate rotation angles between all sides.
        for (int i = 0; i < n; i++) {
                int i1 = i - 1;
                int i2 = i + 1;

                if (i1 <  0) i1 += n;
                if (i2 >= n) i2 -= n;
                
                v1.set(&vlist->vertex[i1], &vlist->vertex[i]);
                v2.set(&vlist->vertex[i],  &vlist->vertex[i2]);

                deg = v1.Angle(v2);
                total_deg += deg;
        }

        return total_deg > 0 ? true : false;
}

//
// Smoothing
//
void GpcVertexList::smoothing(void)
{
        int n = vlist->num_vertices;

        Vector v1, v2, vm, first;

        //
        // move all points to the medium point between 
        // current and next points.
        //
        first.set(&vlist->vertex[0]);
        for (int i = 0; i < n; i++) {
                v1.set(&vlist->vertex[i]);
                if (i < n - 1) {
                        v2.set(&vlist->vertex[i+1]);
                } else {
                        v2 = first;
                }
                
                vm = (v1 + v2) / 2.0;

                vlist->vertex[i].x = vm.x;
                vlist->vertex[i].y = vm.y;
        }
}

//
// Crop useless points
//
void GpcVertexList::crop(BoundingBox &bbox)
{
        int n = vlist->num_vertices;

        int i, j;
        double x, y;
        double prev_x = -99999, prev_y = -99999;

#define ERR     1.0     // degree...
        
        for (i = 0, j = 0; i < n; i++) {
                x = vlist->vertex[i].x;
                y = vlist->vertex[i].y;

                if (!bbox.isInbox(x, y) &&
                    ABS(x - prev_x) < ERR &&
                    ABS(y - prev_y) < ERR) {
                        // skip this point
                        continue;
                }

                // use this point
                vlist->vertex[j] = vlist->vertex[i];
                prev_x = vlist->vertex[i].x;
                prev_y = vlist->vertex[i].y;

                j++;
        }

        vlist->num_vertices = j;
}


////////////////////////////////////////////////////////////////////////
// GpcPolygon
GpcPolygon::GpcPolygon()
{
        polygon.num_contours = 0;
        polygon.contour = NULL;
        polygon.hole = NULL;
}

GpcPolygon::~GpcPolygon()
{
        GpcPolygon::clear();
}

void GpcPolygon::clear(void)
{
        vector<GpcVertexList*>::iterator it;

        for (it = contour.begin(); it != contour.end(); it++) {
                delete *it;
        }
        contour.clear();

        gpc_free_polygon(&polygon);
}

void GpcPolygon::LoadFromFile(const char *fname)
{
        FILE *fp = fopen(fname, "rb");
        if (!fp) {
                fprintf(stderr, "Can't open file: %s\n", fname);
                exit(1);
        }
        
        gpc_free_polygon(&polygon);
        gpc_read_polygon(fp, 0, &polygon);

        fclose(fp);

        BuildVertexListFromGpcPolygon();
}

void GpcPolygon::SaveToFile(const char *fname)
{
        FILE *fp = fopen(fname, "wb");
        if (!fp) {
                fprintf(stderr, "Can't open file: %s\n", fname);
                exit(1);
        }
        
        gpc_write_polygon(fp, 0, &polygon);

        fclose(fp);
}

void GpcPolygon::AddVertexList(GpcVertexList *list, bool rebuild)
{
        // add gpc contour (duplicate)
        gpc_add_contour(&polygon, list->getvlist(), 0);

        // rebuild GpcVertexList
        if (rebuild) BuildVertexListFromGpcPolygon();
}

void GpcPolygon::Smoothing(void)
{
        vector<GpcVertexList*>::iterator it;

        for (it = contour.begin(); it != contour.end(); it++) {
                (*it)->smoothing();
        }
}

void GpcPolygon::Crop(BoundingBox &bbox)
{
        vector<GpcVertexList*>::iterator it;

        for (it = contour.begin(); it != contour.end(); it++) {
                (*it)->crop(bbox);
        }
}


GpcPolygon *GpcPolygon::Clipping(BoundingBox &bbox)
{
        // Generate polygons for clipping.
        GpcPolygon clip;

        gpc_vertex vertex[4];
        vertex[0].x = bbox.xmin; vertex[0].y = bbox.ymin;
        vertex[1].x = bbox.xmax; vertex[1].y = bbox.ymin;
        vertex[2].x = bbox.xmax; vertex[2].y = bbox.ymax;
        vertex[3].x = bbox.xmin; vertex[3].y = bbox.ymax;

        GpcVertexList contour(4, vertex);
        clip.AddVertexList(&contour);

        // clipping
        GpcPolygon *clipped = new GpcPolygon;
        gpc_polygon *gp = clipped->getpolygon();
        gpc_polygon_clip(GPC_INT, &polygon, clip.getpolygon(), gp);

        // create GpcVertexList strucutures...
        clipped->BuildVertexListFromGpcPolygon();
        return clipped;
}

void GpcPolygon::BuildVertexListFromGpcPolygon(void)
{
        vector<GpcVertexList*>::iterator it;
        for (it = contour.begin(); it != contour.end(); it++) {
                delete *it;
        }
        contour.clear();

        for (int i = 0; i < polygon.num_contours; i++) {
                GpcVertexList *vl = new GpcVertexList(&polygon.contour[i]);
                contour.push_back(vl);
        }
}

bool GpcPolygon::isEmpty(void)
{
        return polygon.num_contours > 0 ? false : true;
}

// check if the polygon covers whole bounding box.
bool GpcPolygon::isFull(BoundingBox &target)
{
        if (polygon.num_contours != 1) {
                return false;   
        }

        // Check if the number of vertices == 4?
        gpc_vertex_list *contour = &polygon.contour[0];

        if (contour->num_vertices != 4) {
                return false;
        }

        // generate Bounding Box
        BoundingBox bbox;
        for (int i = 0; i < 4; i++) {
                bbox.setpoint(contour->vertex[i].x, contour->vertex[i].y);
        }

        // check each vertices
        return bbox.compare(target);
}


void GpcPolygon::printStat(void)
{
        int n = numVList();

        int nv = 0;
        for (int i = 0; i < numVList(); i++) {
                nv += getVList(i)->numVertices();
        }
        fprintf(stderr, "Contour=%d Vertices=%d\n", n, nv);

}