Revision: 64333
http://sourceforge.net/p/brlcad/code/64333
Author: starseeker
Date: 2015-03-03 16:37:56 +0000 (Tue, 03 Mar 2015)
Log Message:
-----------
Start trying to get a handle on the CW/CCW status of inputs to triangulation.
Modified Paths:
--------------
brlcad/trunk/include/bn/polygon.h
brlcad/trunk/src/libbn/polygon.c
Modified: brlcad/trunk/include/bn/polygon.h
===================================================================
--- brlcad/trunk/include/bn/polygon.h 2015-03-03 16:11:26 UTC (rev 64332)
+++ brlcad/trunk/include/bn/polygon.h 2015-03-03 16:37:56 UTC (rev 64333)
@@ -43,16 +43,34 @@
/**
* @brief
- * Test whether a point is inside a 2D polygon
+ * test whether a polygon is clockwise (CW) or counter clockwise (CCW)
*
- * Franklin's test for point inclusion within a polygon - see
- * http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
+ * Determine if a set of points forming a polygon are in clockwise
+ * or counter-clockwise order (see http://stackoverflow.com/a/1165943)
+ *
+ * @param[in] npts number of points pts contains
+ * @param[in] pts array of points, building a convex polygon. duplicated points
+ * aren't allowed. the points in the array will be sorted counter-clockwise.
+ *
+ * @return -1 if polygon is counter-clockwise
+ * @return 1 if polygon is clockwise
+ * @return 0 if the test failed
+ */
+BN_EXPORT extern int bn_polygon_clockwise(size_t npts, const point2d_t *pts);
+
+
+/**
+ * @brief
+ * test whether a point is inside a 2d polygon
+ *
+ * franklin's test for point inclusion within a polygon - see
+ * http://www.ecse.rpi.edu/homepages/wrf/research/short_notes/pnpoly.html
* for more details and the implementation file polygon.c for license info.
*
- * @param[in] npts Number of points pts contains
- * @param[in] pts Array of points, building a convex polygon. Duplicated points
- * aren't allowed. The points in the array will be sorted counter-clockwise.
- * @param[in] test_pt Point to test.
+ * @param[in] npts number of points pts contains
+ * @param[in] pts array of points, building a convex polygon. duplicated points
+ * aren't allowed. the points in the array will be sorted counter-clockwise.
+ * @param[in] test_pt point to test.
*
* @return 0 if point is outside polygon
* @return 1 if point is inside polygon
Modified: brlcad/trunk/src/libbn/polygon.c
===================================================================
--- brlcad/trunk/src/libbn/polygon.c 2015-03-03 16:11:26 UTC (rev 64332)
+++ brlcad/trunk/src/libbn/polygon.c 2015-03-03 16:37:56 UTC (rev 64333)
@@ -190,6 +190,22 @@
return 0;
}
+int
+bn_polygon_clockwise(size_t npts, const point2d_t *pts)
+{
+ size_t i;
+ int sum = 0;
+ for (i = 0; i < npts; i++) {
+ if (i + 1 == npts) {
+ sum += (pts[0][0] - pts[i][0]) * (pts[0][1] + pts[i][1]);
+ } else {
+ sum += (pts[i][0] - pts[i+1][0]) * (pts[i][1] + pts[i+1][1]);
+ }
+ }
+ bu_log("sum: %d\n", sum);
+ if (sum == 0) return 0;
+ return (sum > 0) ? 1 : -1;
+}
/*
* Translation to libbn data types of Franklin's point-in-polygon test.
@@ -483,7 +499,13 @@
struct pt_vertex_ref *convex_list = NULL;
struct pt_vertex_ref *reflex_list = NULL;
struct pt_vertex_ref *ear_list = NULL;
+ int ccw = bn_polygon_clockwise(npts, pts);
+ if (ccw != -1) {
+ bu_log("Warning - non-CCW point loop!\n");
+ }
+
+
BU_GET(lists, struct pt_lists);
if(npts < 3) return 1;
if (!faces || !num_faces || !pts) return 1;
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
------------------------------------------------------------------------------
Dive into the World of Parallel Programming The Go Parallel Website, sponsored
by Intel and developed in partnership with Slashdot Media, is your hub for all
things parallel software development, from weekly thought leadership blogs to
news, videos, case studies, tutorials and more. Take a look and join the
conversation now. http://goparallel.sourceforge.net/
_______________________________________________
BRL-CAD Source Commits mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-commits
