Check point inside shape

3
votes

I am searching for a point inside or outside Polygon algorithm. So far I found some algorithm (odd even rule algorithm) and which is running successfully if I passed the polygon points. But I faced a problem (for calculating points) for doing this. The problem is if the polygon contains only move to and line to data (For example if the polygon is rectangle or octagon.. etc) then I can easily calculate the points for drawing Polygon. But I have some polygon which can draw using arc data as well as line to and move to data. So in this case I am stuck for checking point inside or outside polygon in generic way.

I am attaching here some polygon images.

enter image description hereenter image description here

You can see the above image which draw using line to, move to as well as arc data. So in that scenario I am not able to checking.

Please give some idea how can I check a point inside or outside of a this type of polygon?

(For drawing the polygon I have data something like that :

MoveTo: Coordinate: 424.941955, 626.04046,

LineTo: Coordinate: 428.941955, 626.04046,

ArcTo: Coordinate: 431.941955, 633.04046 - center point: Coordinate: 433.941955, 628.04046 - angle: -1.5707963267948966,

LineTo: Coordinate: 431.941955, 639.04046,

ArcTo: Coordinate: 428.941955, 646.04046 - center point: Coordinate: 433.941955, 644.04046 - angle: -1.5707963267948966,

LineTo: Coordinate: 424.941955, 646.04046,

ArcTo: Coordinate: 421.941955, 639.04046 - center point: Coordinate: 419.941955, 644.04046 - angle: -1.5707963267948966,

LineTo: Coordinate: 421.941955, 633.04046,

ArcTo: Coordinate: 424.941955, 626.04046 - center point: Coordinate: 419.941955, 628.04046 - angle: -1.5707963267948966 )

This is the approximation data.

Thank you.

3
javapolygon
And, what is your approach so far? – Thomas Junk
First I calculated the points for line to and move to then I tried with for checking if the inside or outside of the arc. For arc I have start end angle, start end point and radius. But I am not getting the correct result. – user4486530
(btw, those shapes are not polygons) – Joel

3 Answers

2
votes

Since you asked for ideas, you have the following options that I can think of:

  1. Do as Raniz suggested. This is the best.

  2. Create temporary polygons approximating the curves using straight line segments and then use your existing algorithm. This is sub-optimal, but depending on the specifics of your situation, it might be a pragmatic approach.

  3. Rasterize the shapes using different foreground and background colors and then just check the color of the pixel under the point. This is highly sub-optimal, but if by any chance you are already rasterizing these shapes in order to display them, then you already have all it takes to implement this real quick.

2
votes

You should do the same algorithm (even-odd) but you need to use a different intersection algorithm for the arcs (bezier curves).

Here's a blog post that should get you started in the correct direction: https://www.particleincell.com/2013/cubic-line-intersection/

Update:

Here's an answer and question on how to do line/circle intersection. It should be fairly trivial to extend to check if the intersection point(s) are within your degree span.

0
votes

You should be able to use a GeneralPath to create your Shape. Then use the contains(...) method to determine if the shape contains your point or not.