Re: complex polygon decomposition

Hi Dave,

I can't thank you enough. That wasn't just an answer, that was an implementation plan. Thank you a lot.

Anyway, I have a few quesions regarding the whole thing. I hope I don't ask for to much but it would be great if you can give some inputs on the following two questions as well.


Bentley-Ottmann:

As anyone who ever implemented this algorithm and exposed it to real world data knows that the algorithm has issues. Namely each time you create an intersection you slightly modify the slope of all affected edges. This might cause new intersections to be generated that the bentley-ottmann algorithm can't find anymore.

This might cause all later algorithm that insinst on non-intersecting geometry to bark or run into infinite loops. (I'm sure you've seen this effect!)


During the research I did before I have seen two ways to tacke this problem.

1st: Brute force: Repeat the Bentley-Ottmann as long as you get new intersections.

2nd: Add some minkovski-sum based sensitive error metric to the intersection calculations and hope it will do it's magic.

How would you tacke these problems?

The first solution is tempting because it's just wrapping the algorithm into a simple loop which only gets executed in extreme cases anyway. I have my doubts if such an algorithm will in all caes terminate and don't go into an endless loop though.



The Data-Structure:

You've wrote that it might be easy to adapt my current datastructure for the intersection "pick the top-node and always walk as CCW as you can"-algorithm.

Well - my data-structure is built around a strong next->current->prev relationship. I'm doing decomposition into monotone chains and trinanglate the monotone chains afterwards. So my data-structure is hand-tailored to exactly this task. I have some more info to store extra-edges that get created during the monotone decomposition, indices and such stuff, but I'm not prepared for multiple next/previous links.

Converting from one structure to another is not a problem, so what data-structure for the intersection-decomposition thing would you suggest. I think the good old index/vertex database with some fine way to do fast connection queries will do the job, won't it?


Thanks in advance..
Nils
.

Relevant Pages

  • Re: complex polygon decomposition
    ... As anyone who ever implemented this algorithm and exposed it to real world ... intersection you slightly modify the slope of all affected edges. ... original line segments as an array of LineSegmentPlus. ... I'm doing decomposition into monotone chains and trinanglate ...
    (comp.graphics.algorithms)
  • Re: Letter to US Sen. Byron Dorgan re unpaid overtime
    ... and Richard made it clear that he understands the order ... >> of evaluation of a for loop. ... > using strlen but using an Oalgorithm when there is a trivial O ... >> In most other languages the terminating ...
    (comp.programming)
  • Re: Efficiency questions: combined ifs and looping 4 times
    ... Choice of algorithm always has a far bigger impact in performance than ... Use sizeof before the loop, store the result in a var and use ... speaks well of PHP. ... your order of complexity analysis is off. ...
    (comp.lang.php)
  • Re: count of each word occurred
    ... > take each word in order and compare it with the rest of the list ... Another version of this algorithm takes advantage of the fact that it does ... loop over all words in the list ... a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Letter to US Sen. Byron Dorgan re unpaid overtime
    ... and Richard made it clear that he understands the order ... > of evaluation of a for loop. ... using strlen but using an Oalgorithm when there is a trivial O ... > condition is an end value and in these languages the strlen value ...
    (comp.programming)