| Re: [AD] Triangulator broken |
[ Thread Index |
Date Index
| More lists.liballeg.org/allegro-developers Archives
]
Algorithm is working in a little bit different way. All holes are
sorted from right to the left according to most right vertex in the
hole. Therefore First handled hole will be hole 2. Split line will go
from bottom right vertex to 'b' vertex. After merge, the only hole
will be the hole 1. Second goes as on the picture:
+-------------------------------------------------------+ a
| |
| |
| +-------+ |
| | | -+----+ |
| | \ B / | | |
| | | / +----+ |
| +----------+- \ |
| x \ |i
| ^ hole 1 ^ hole 2 \ |
| \ A |
| \ |
| \ |
| \ |
| \|
+-------------------------------------------------------+ b
If split is done incorrectly, then probably sorting fail in some way.
Do you have any specific set of data which produce wrong
triangulation?
On 13 March 2011 09:13, Trent Gamblin <trent@xxxxxxxxxx> wrote:
> I ran into this bug in the polygon triangulator. Due to the way it's written,
> I think it may be a difficult fix, but maybe Michal would be able to do it more
> easily... Here's the situation.
>
>
>
> +-------------------------------------------------------+ a
> | |
> | |
> | +-------+ |
> | | | +----+ |
> | | \ | | |
> | | | +----+ |
> | +----------+ ^ hole 2 |
> | x |i
> | ^ hole 1 |
> | |
> | |
> | |
> | |
> | |
> +-------------------------------------------------------+ b
>
> ^ outer polygon
>
> >From my understanding of Michal's code, when calculating splits for the holes,
> a ray is cast from the rightmost edge of a hole (marked with x) to the nearest
> intersection to the right (i). The problem is that that's all it tries. It then deems
> that either point a or b is suitable for the split. The problem is that if you look at this
> diagram, drawing a line from x to a is going to pass through a hole which is a
> no no. b is open but there could easily be another hole there, too. In my own
> triangulator (which has flaws of its own), I do the nearest right intersection
> test, then cast rays to point a or b. If that ray hits anything before a or b
> then I recalculate with the split now on hole 2. Looking at the code, I don't
> know how to proceed because hole 2 may not be part of the vertex list at the time
> hole 1 is processed (if hole 2 appears later in the data you pass).
>
> Michal, any chance you can take a look or at least advise on this?
>
> Trent
> ------------------------------------------------------------------------------
> Colocation vs. Managed Hosting
> A question and answer guide to determining the best fit
> for your organization - today and in the future.
> http://p.sf.net/sfu/internap-sfd2d
> --
> https://lists.sourceforge.net/lists/listinfo/alleg-developers
>
--
thedmd, Michał Cichoń
Artifex Mundi
michcic@xxxxxxxxxx
http://www.artifexmundi.com