// Copyright (c) 2018 PaddlePaddle Authors. All Rights Reserved. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. /*************************************************************************** * * Copyright (c) 2015 Baidu.com, Inc. All Rights Reserved * **************************************************************************/ /** * @file include/gpc.h * @author huhan02(com@baidu.com) * @date 2015/12/18 13:52:10 * @brief * * @modified by sunyipeng * @email sunyipeng@baidu.com * @date 2018/6/12 **/ #ifndef PADDLE_PHI_KERNELS_FUNCS_GPC_H_ // GPC_H_ #define PADDLE_PHI_KERNELS_FUNCS_GPC_H_ // GPC_H_ #include #include #include #include namespace phi { namespace funcs { typedef enum { // Set operation type GPC_DIFF, // Difference GPC_INT, // Intersection GPC_XOR, // Exclusive or GPC_UNION // Union } gpc_op; typedef struct { // Polygon vertex structure double x; // Vertex x component double y; // vertex y component } gpc_vertex; typedef struct { // Vertex list structure int num_vertices; // Number of vertices in list gpc_vertex *vertex; // Vertex array pointer } gpc_vertex_list; typedef struct { // Polygon set structure int num_contours; // Number of contours in polygon int *hole; // Hole external contour flags gpc_vertex_list *contour; // Contour array pointer } gpc_polygon; typedef struct { // Tristrip set structure int num_strips; // Number of tristrips gpc_vertex_list *strip; // Tristrip array pointer } gpc_tristrip; typedef enum { LEFT, RIGHT } gpc_left_right; typedef enum { ABOVE, BELOW } gpc_above_below; typedef enum { CLIP, SUBJ } gpc_clip_subj; typedef enum { /* Edge intersection classes */ NUL, /* Empty non-intersection */ EMX, /* External maximum */ ELI, /* External left intermediate */ TED, /* Top edge */ ERI, /* External right intermediate */ RED, /* Right edge */ IMM, /* Internal maximum and minimum */ IMN, /* Internal minimum */ EMN, /* External minimum */ EMM, /* External maximum and minimum */ LED, /* Left edge */ ILI, /* Internal left intermediate */ BED, /* Bottom edge */ IRI, /* Internal right intermediate */ IMX, /* Internal maximum */ FUL /* Full non-intersection */ } vertex_type; typedef enum { /* Horizontal edge states */ NH, /* No horizontal edge */ BH, /* Bottom horizontal edge */ TH /* Top horizontal edge */ } h_state; typedef enum { /* Edge bundle state */ UNBUNDLED, /* Isolated edge not within a bundle */ BUNDLE_HEAD, /* Bundle head node */ BUNDLE_TAIL /* Passive bundle tail node */ } bundle_state; typedef struct v_shape { /* Internal vertex list datatype */ double x; /* X coordinate component */ double y; /* Y coordinate component */ struct v_shape *next; /* Pointer to next vertex in list */ } vertex_node; typedef struct p_shape { /* Internal contour / tristrip type */ int active; /* Active flag / vertex count */ int hole; /* Hole / external contour flag */ vertex_node *v[2]; /* Left and right vertex list ptrs */ struct p_shape *next; /* Pointer to next polygon contour */ struct p_shape *proxy; /* Pointer to actual structure used */ } polygon_node; typedef struct edge_shape { gpc_vertex vertex; /* Piggy-backed contour vertex data */ gpc_vertex bot; /* Edge lower (x, y) coordinate */ gpc_vertex top; /* Edge upper (x, y) coordinate */ double xb; /* Scanbeam bottom x coordinate */ double xt; /* Scanbeam top x coordinate */ double dx; /* Change in x for a unit y increase */ int type; /* Clip / subject edge flag */ int bundle[2][2]; /* Bundle edge flags */ int bside[2]; /* Bundle left / right indicators */ bundle_state bstate[2]; /* Edge bundle state */ polygon_node *outp[2]; /* Output polygon / tristrip pointer */ struct edge_shape *prev; /* Previous edge in the AET */ struct edge_shape *next; /* Next edge in the AET */ struct edge_shape *pred; /* Edge connected at the lower end */ struct edge_shape *succ; /* Edge connected at the upper end */ struct edge_shape *next_bound; /* Pointer to next bound in LMT */ } edge_node; inline bool gpc_eq(float a, float b) { return (fabs(a - b) <= 1e-6); } inline bool gpc_prev_index(float a, float b) { return (fabs(a - b) <= 1e-6); } inline int gpc_prev_index(int i, int n) { return ((i - 1 + n) % n); } inline int gpc_next_index(int i, int n) { return ((i + 1) % n); } inline int gpc_optimal(gpc_vertex *v, int i, int n) { return (v[(i + 1) % n].y != v[i].y || v[(i - 1 + n) % n].y != v[i].y); } inline int gpc_fwd_min(edge_node *v, int i, int n) { return (v[(i + 1) % n].vertex.y > v[i].vertex.y && v[(i - 1 + n) % n].vertex.y >= v[i].vertex.y); } inline int gpc_not_fmax(edge_node *v, int i, int n) { return (v[(i + 1) % n].vertex.y > v[i].vertex.y); } inline int gpc_rev_min(edge_node *v, int i, int n) { return (v[(i + 1) % n].vertex.y >= v[i].vertex.y && v[(i - 1 + n) % n].vertex.y > v[i].vertex.y); } inline int gpc_not_rmax(edge_node *v, int i, int n) { return (v[(i - 1 + n) % n].vertex.y > v[i].vertex.y); } // inline void gpc_p_edge(edge_node *d, edge_node *e, int p, double i, double j) // { inline void gpc_p_edge(edge_node *d, edge_node *e, int p) { d = e; do { d = d->prev; } while (!d->outp[p]); // i = d->bot.x + d->dx * (j - d->bot.y); } // inline void gpc_n_edge(edge_node *d, edge_node *e, int p, double i, double j) // { inline void gpc_n_edge(edge_node *d, edge_node *e, int p) { d = e; do { d = d->next; } while (!d->outp[p]); // i = d->bot.x + d->dx * (j - d->bot.y); } template void gpc_malloc(T *&p, int b, char *s) { if (b > 0) { p = reinterpret_cast(malloc(b)); if (!p) { fprintf(stderr, "gpc malloc failure: %s\n", s); exit(0); } } else { p = NULL; } } template void gpc_free(T *&p) { if (p) { free(p); p = NULL; } } /* =========================================================================== Public Function Prototypes =========================================================================== */ void add_vertex(vertex_node **t, double x, double y); void gpc_vertex_create(edge_node *e, int p, int s, double x, double y); /* void gpc_read_polygon(FILE *infile_ptr, int read_hole_flags, gpc_polygon *polygon); void gpc_write_polygon(FILE *outfile_ptr, int write_hole_flags, gpc_polygon *polygon); */ void gpc_add_contour(gpc_polygon *polygon, gpc_vertex_list *contour, int hole); void gpc_polygon_clip(gpc_op set_operation, gpc_polygon *subject_polygon, gpc_polygon *clip_polygon, gpc_polygon *result_polygon); void gpc_tristrip_clip(gpc_op set_operation, gpc_polygon *subject_polygon, gpc_polygon *clip_polygon, gpc_tristrip *result_tristrip); void gpc_polygon_to_tristrip(gpc_polygon *polygon, gpc_tristrip *tristrip); void gpc_free_polygon(gpc_polygon *polygon); void gpc_free_tristrip(gpc_tristrip *tristrip); } // namespace funcs } // namespace phi #endif // PADDLE_PHI_KERNELS_FUNCS_GPC_H_ /* vim: set expandtab ts=4 sw=4 sts=4 tw=100: */