Point enclosed by segments

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Point enclosed by segments

Post by FAQ »

Given a point A (x, y) and N segments (x1, y1, x2, y2). Check if these segments can enclose point A
Enclose = point A will stay in (or on any segment) a polygon made by endpoints of segments or their intersection points (sorry for my poor English)

Could anyone tell me how fast we can solve this problem, please?
N <= 150
co-ordinates <= abs(10^4)

Thanks

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

essentially you want to find a ray that goes between your point and end point of another line segment to see if it intersects any other line segments. if no then report no, otherwise report yes.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

As I understood the original problem, this won't work.

An O(n^2) solution should be reasonable. (Disregarding special cases,) test all pairs of segments for intersection, build a graph where vertices=intersections, edges=parts of segments. This graph is clearly planar.
Find the face that contains the point A and verify whether it is the outer face or not.

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ »

excuse me misof,

I couldn't get this sentence
Find the face that contains the point A and verify whether it is the outer face or not.
how fast can we find a face like this?

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude »

this is what USA computing olympiad training site says at their chapter 3.4
USACO 3.4 wrote:
Point in triangle
To check if a point A is in a triangle, find another point B which is within the triangle (the average of the three vertices works well). Then, check if the point A is on the same side of the three lines defined by the edges of the triangle as B.

Point in convex polygon
The same trick works for a convex polygon:

Checking convexity of 2-dimensional polygon
To check the convexity of a 2-dimensional polygon, walk the polygon in clock-wise order. For each triplet of consecutive points (A, B, C), calculate the cross product (B - A) x (C - A). If the z component of each of these vectors is positive, the polygon is convex.

Point in non-convex polygon
To calculate if a point is within a nonconvex polygon, make a ray from that point in a random direction and count the number of times it intersects the polygon. If the ray intersects the polygon at a vertex or along an edge, pick a new direction. Otherwise, the point is within the polygon if and only if the ray intersects the polygon an odd number of times.



This method also extends to three dimensions (and higher), but the restriction on intersection is that it only intersects at faces and not at either a vertex or an edge.
fahim
#include <smile.h>

Post Reply

Return to “Algorithms”