1
$\begingroup$

I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects itself using Bentley–Ottmann algorithm.

I planned to build non-self intersecting polygons by editing edges around intersection points, but problem is when you have two edges that intersect, you don't know which two of the four sides are inside, and which are outside of polygon.

I could use ray crossing algorithm to resolve this, but it is too slow. Its time complexity is O(n), and I'd have two do it at least two times for every intersection point. So it would be extremely slow with around 200k points of polygon.

So what I'm asking is, is there any faster way to divide self intersecting polygon into non-self intersecting ones.

I need this because I am doing polygon triangulation. I already done sweep-line triangulation algorithm for triangulating non-self intersecting polygons with holes. So I just need tho have array of these polygons as input.

Improve this question
$\endgroup$
6
  • $\begingroup$ What kind of editing can you do at intersection points, do you mean operations like the one in this question? $\endgroup$
    – Chao Xu
    Mar 28, 2014 at 7:35
  • $\begingroup$ maybe the data structure you're looking for is a doubly-connected edge list? It's easier to keep track of faces that way. en.wikipedia.org/wiki/Doubly_connected_edge_list $\endgroup$
    – Joe
    Mar 28, 2014 at 8:23
  • $\begingroup$ Chao Xu that is exactly kind of editing I'm trying to do. I looked at your question, but I'm not sure I understood, is it than possible to do it? Joe I am working with DCEL, but problem with self intersections is that they sometimes make CCW polygon to be CW and vice versa. However I found a way to do it by keeping info which side of edge is inside of polygon. $\endgroup$
    – fuzzomorphism
    Mar 28, 2014 at 13:20
  • $\begingroup$ @user2764266 If you have an answer, then feel free to answer your own question. Also, you can use the @ symbol in front of a username to notify that user that you have responded to their comment, just like I have done in this comment, by writing @user2764266 $\endgroup$
    – Joe
    Mar 28, 2014 at 20:45
  • $\begingroup$ @Joe thanks for suggestions. I am not sure if what I've found is answer for the whole question, because it still doesn't prove that I can triangulate self intersecting polygon, but just that I can find out if point is inside of polygon. I can do this by keeping info with each edge on which side of this edge lies interior of polygon, than I can check if given point is on the same side as polygon interior of tho adjacent edges. $\endgroup$
    – fuzzomorphism
    Apr 1, 2014 at 15:06

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.