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.

Mike Nakis
  • 56,297
  • 11
  • 110
  • 142
  • And, what is your approach so far? – Thomas Junk May 01 '15 at 07: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. –  May 01 '15 at 07:09
  • 4
    (btw, those shapes are not polygons) – Joel May 01 '15 at 07:35

3 Answers3

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.

Community
  • 1
  • 1
Raniz
  • 10,882
  • 1
  • 32
  • 64
  • 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? –  May 01 '15 at 08:30
  • How is your arc defined? – Raniz May 01 '15 at 08:32
  • In the above image you can see the arc. which is used to draw a image. –  May 01 '15 at 08: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 01 '15 at 08:41
  • For defining arc I have following data : 1. center point. 2. start and end angle 3. start and end point. 4. arc radius. –  May 01 '15 at 08:43
  • Can I used the above algorithm for find the intersecting point between line and arc? if yes the how? Thank you. –  May 02 '15 at 14:14
  • 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 07 '15 at 01:03
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.

Mike Nakis
  • 56,297
  • 11
  • 110
  • 142
  • 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 01 '15 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 01 '15 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. –  May 01 '15 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](http://sscce.org/) 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 01 '15 at 13:04
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.

camickr
  • 321,443
  • 19
  • 166
  • 288
  • 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. –  May 04 '15 at 02:27