Skip to content
A segmentation procedure for planar graphs defined by an input polyline.
C++ C
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
Screenshots
example
obj
src
.gitattributes
.gitignore
DegenerateInput.xlsx
DegenerateLine.txt
Notes.txt
README.md
ScribbleSegmenter.sln
addons.make
emptyExample.vcxproj
emptyExample.vcxproj.filters
icon.rc

README.md

ofxScribbleSegmenter

A segmentation procedure for planar graphs defined by an input polyline.

alt text

#Input:

A list of 2D points defining a polyline.

Alternativly you can use a list of polylines.

#Output: A list of lists of points, where each list of point represents a polygon representing one face of the planar graph when the input polyline is embedded into it.

#External Faces:

Please note the some of the polygons in the output list will be external faces, in that they include the entire infinite cartesian plane minus the space encompassed by the union of the internal faces.

Another way of saying this is that if I were to give a square-ish polyline as an input the the program, the it would produce 2 faces, one that contains the indide of the square and one that contains the outside of the square.

Example Screen Shot

Please Note that the exact number may be slightly off due to randomization.

alt text

Usage

#include "ofMain.h"
#include "FaceFinder.h"

...

std::vector<ofPoint> input; // The input is a polyline, *not* a polygon.

<Populate Input here.>

FaceFinder segmenter;

// Data Structures for computed information.
std::vector< std::vector<scrib::point_info> *> * polygonal_output;
std::vector<int> external_face_indices;

// Using the FaceFinder to derive polygonal face infomation.
polygonal_output = segmenter.findFaces(&input);
// Appends the indices of every external face to the external_face_indices vector.
segmenter.determineExternalFaces(polygonal_output, &external_face_indices);

It is also possible to derive faces for a list of polyline inputs.

std::vector<std::vector<ofPoint> *> input;

<Same code as in singular polyline case from here on out.>

// - Function is overridden by a function of the same name that takes in a
//   vector<vector<ofPoint *> >; instead of a vector<ofPoint>.
polygonal_output = segmenter.findFaces(&input);

#Example Output (One possible run)

setup done!
4 Cycles!
There is/are 1 external faces with 12,  points in each of them respectively.

 Information about all of the polygons:

Polygon 0
 --Point : 51.7093, 49.0416, 0, index = 11
 --Point : 51.7056, 48.465, 0, index = 4
 --Point : 51.7093, 49.0416, 0, index = 11
 --Point : 99.7357, 49.5628, 0, index = 13
 --Point : 99.0668, -0.946655, 0, index = 6
 --Point : 1.83067, 0.255829, 0, index = 10
 --Point : 1.7207, 100.376, 0, index = 8
 --Point : 52.033, 99.7853, 0, index = 12
 --Point : 51.7093, 49.0416, 0, index = 11
 --Point : 49.5549, 49.0182, 0, index = 0
Polygon 1
 --Point : 99.7357, 49.5628, 0, index = 13
 --Point : 100.393, 99.2178, 0, index = 7
 --Point : 52.033, 99.7853, 0, index = 12
 --Point : 52.3484, 149.233, 0, index = 3
 --Point : 149.137, 149.424, 0, index = 2
 --Point : 150.136, 50.1098, 0, index = 1
Polygon 2
 --Point : 149.137, 149.424, 0, index = 2
 --Point : 52.3484, 149.233, 0, index = 3
 --Point : 52.033, 99.7853, 0, index = 12
 --Point : 1.7207, 100.376, 0, index = 8
 --Point : 1.83067, 0.255829, 0, index = 10
 --Point : -0.580078, 0.285645, 0, index = 5
 --Point : 1.83067, 0.255829, 0, index = 10
 --Point : 1.84265, -10.6498, 0, index = 9
 --Point : 1.83067, 0.255829, 0, index = 10
 --Point : 99.0668, -0.946655, 0, index = 6
 --Point : 99.7357, 49.5628, 0, index = 13
 --Point : 150.136, 50.1098, 0, index = 1
Polygon 3
 --Point : 99.7357, 49.5628, 0, index = 13
 --Point : 51.7093, 49.0416, 0, index = 11
 --Point : 52.033, 99.7853, 0, index = 12
 --Point : 100.393, 99.2178, 0, index = 7

Process returned 0 (0x0)   execution time : 8.427 s
Press any key to continue.

TODO:

  1. Elliminate the Comparator Errors inside of the Intersector. Evidently my comparison events are not valid comparators and through errors that can be seen when compiled in debug mode.
  2. Fix comments.
  3. Modernize this README and chronicle all of the features, including perhaps the offset curves.
  4. Add set output types to various functions such as complemented face determination, because for many users it will make more sense to output the list of indices as a set.
  5. Go and remove all of the int to size_t warnings with vector sizes to avoid errors in ridiculously large inputs.
  6. FIX Union meet at 1 point only bug, because the union of all of the neighbors of a landlocked face, but not the face itself will include it because the neighborhood will be improiperly traced.
You can’t perform that action at this time.