# Geometry :

Subject: Re: [geometry] Finding a boost::equal simplified polygon
From: Barend Gehrels (barend_at_[hidden])
Date: 2013-10-23 11:16:34

Hi Claus,

Claus Christmann wrote On 23-10-2013 16:47:
> Hi
>
> I am looking for a method for finding boost::euqual polygons. The problem I am
> facing is that my code creates unnecessarily complex polygons of the type
>
> <ascii art>
> A------------B
> | |
> | D-------(C,E)
> | \
> G--------------F
> </ascii art>
>
> where the vertex D sits inside the polygon. Technically the polygon
> (A,B,C,D,E,F,G,A) is boost::equal to the polygon (A,B,C,F,G,A). Could anybody
> point me to how I could write/get/find/have an efficient way to get the
> 'simplified' (A,B,C,F,G,A) from the 'complicated' (A,B,C,D,E,F,G,A)?
> Note though that the 'spike' to the interior can have several (coinciding)
> vertices.
>
> My current approach checks all vertices for colocation and then computes the
> area of the ring spanned by all the interim vertices ((C,D,E) in the above
> example). Does anybody have a better idea?

There is a "remove_spikes" in the extensions which did not always work.
By chance I recently created a new version, intended for the main trunk
(so not an extension). But it still has to be committed, I will do that
this week.

What it does is removing C-D and D-C in your figure above (also multiple
vertices, the spike can also have corners; it can be inside or outside).

By the way, if you compute the area to do the "equals", removing spikes
is not necessary... But area-computation is not really sufficient to do
"equals"...

Regards, Barend

Geometry list run by mateusz at loskot.net