3

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 here enter 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
  • And, what is your approach so far? May 1, 2015 at 7:06
  • 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
    May 1, 2015 at 7:09
  • 4
    (btw, those shapes are not polygons)
    – Joel
    May 1, 2015 at 7:35

3 Answers 3

2

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.

4
  • If you have a graphics system available, you can create a monochrome (black or white) bitmap, paint the bitmap all white, render the polygon into the bitmap in black, and then use GetPixel( x, y ) on the bitmap to see if the point at x, y is black or white.
    – Mike Nakis
    May 1, 2015 at 12:36
  • Of course you can also do the same with red polygons, though using color means more bits per pixel, and therefore greater memory needs. I am saying this because the pictures you posted seem to have been created by you, so you appear to already have what it takes to render your polygons into bitmaps.
    – Mike Nakis
    May 1, 2015 at 12:41
  • I have already checked with getPixel(x, y) method but I am not getting the correct result. If you have any sample code for checking point inside or outside with the above polygon then please share.
    – user4486530
    May 1, 2015 at 12:50
  • That's not how stackoverflow works. It works as follows: you make a copy of your code, you strip away everything not absolutely necessary so as to arrive at a Short, Self Contained, Correct Example and you post it in an entirely new question on stackoverflow.com, asking: why is my GetPixel() code not working? The question of why GetPixel() did not work for you is unrelated to the general question of how to find if a point is in a polygon.
    – Mike Nakis
    May 1, 2015 at 13:04
2

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.

7
  • I read the above algorithm which you mentioned but its for finding intersection points for bezier curve and line. In my case I have only click point and arc. Can you please explain how can I use it?
    – user4486530
    May 1, 2015 at 8:30
  • How is your arc defined?
    – Raniz
    May 1, 2015 at 8:32
  • In the above image you can see the arc. which is used to draw a image.
    – user4486530
    May 1, 2015 at 8:38
  • How is it defined in your data structures? There are a number of ways of describing arcs. You can have a center point, a radius and a span of degrees, or two points on the arc, or a bezier curve, or maybe something else. What does yours look like?
    – Raniz
    May 1, 2015 at 8:41
  • 1
    You can transform the arc into a bezier curve and use the post I linked but I think it'd be easier to find a circle/line intersection formula and use/adapt that. I've update my answer with a link to another question on here regarding that.
    – Raniz
    May 7, 2015 at 1:03
0

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.

1
  • For creating a general path their is a problem. In case of line or move to their is no problem. But in case of arc how can I use general path. Even I got some idea for creating a general path for arc like divide arc into number of segment but this is not a optimum solution it will down the performance.
    – user4486530
    May 4, 2015 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.