Polygon detection library for C++

Avg Bid (USD)
Project Budget (USD)
$250 - $750

Project Description:
Hi everybody,
I need someone to implement a c++ library for polygon detection from a point.Something like the algorithm in the paper below.
[url removed, login to view]

This library should take a list of line segments and a point as input
and as output
-it should give back a polygon where the point resides in
-island polygons to exclude
-All lose line segments which are not a part of any polygons
Acceptable complexity is around O(n) or some variety of it (e.g O(n) + nlogn etc)
O(n2) and worse is not acceptable

Please have a look at the drawing attached and read the rest

Line Segments List(AB,EF,AG,CD,HI,JK,KL,ML,MN)
Point pt1 (x,y)

Included Polygon:points H,J,K,L,M,N,2,I (as a list)
Excluded Polygons (island(s)):points 4,5,6,7 (as a list)
and if there are more excluded polygons they should be the part of outputs

Loose Line Segments List (E1,G1,D2,2F,3C,3B)

Additional Project Description:
04/09/2013 at 2:19 IST
I made a mistake when stating the desired complexity
Just ignore that O(n2) comment

04/09/2013 at 5:16 IST
/* you can use std lists for List containers or your home made list, i dont care
I asked for a complexity less than O(n^2) but I think it is not possible , so I will accept O(n^2) as well
One more thing about your intersection calculations , with float numbers it is always a good idea to work with a delta for point comparisions
#define List YourPrefferedListContainer

struct RAPointF
RAPointF(float xx,float yy): x(xx),y(yy);
float x,y;
/*add whatever you need to after this point*/


struct RALineSegment
RALineSegment(RAPointF A,RAPointF B);
RAPointF start;
RAPointF end;
/*add whatever you need to after this point*/

struct RAPolygon
List<RAPointF> points;
bool island; //here keep it true for the real bordering polygon , set false if it is an island polygon.Only one polygon has this value false , rest (if there are should be true.
/*add whatever you need to after this point*/


class RAPolygonDetect
void init(List<RALineSegment> lineSegments); //this will be called once and re- called if line segments are changed
List<RAPolygon> getPolygons(RAPointF targetPoint); //i will call this one repeatedly to get different polygons for different points
/*add whatever you need to after this point*/


Skills required:
Algorithm, C++ Programming, Mathematics
Additional Files: polygons.png
About the employer:
Public Clarification Board
Bids are hidden by the project creator. Log in as the employer to view bids or to bid on this project.
You will not be able to bid on this project if you are not qualified in one of the job categories. To see your qualifications click here.

$ 500
in 1 days
$ 499
in 3 days
$ 275
in 5 days
$ 500
in 4 days
$ 472
in 7 days
$ 500
in 3 days
$ 300
in 7 days
Hire xuhaijiao
$ 330
in 7 days
Hire vladgrinko
$ 251
in 2 days
Hire claudiocordara
$ 750
in 15 days