Mixing
known algorithm to reduce the number of points in a closed contour
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
I have a library that produce a contour, as a list of coordinates like :
[[464.5, 551. ],
[464.5, 550. ],
[464. , 549.5],
[463.5, 549. ],
[463. , 548.5],
[462. , 548.5],
[461. , 548.5],
[460.5, 549. ],
[460. , 549.5],
[459. , 549.5],
[458. , 549.5],
[457. , 549.5],
...
Coordinates are connected by straight lines, defining a closed irregular not self-intersecting polygon.
From the example above, we can see that some points could be removed without losing any surface area, but I don't care if the algorithm has some loss, as long as it is configurable (like intersection of area over union of area > x, or something else ?)
Are there some known algorithm that will reduce the number of points of a closed contour ?
PS: the naive algorithm is to test all subsets of points, and take the smallest subset that is above the acceptable loss. The issue is that i might have hundreds of coordinates, and the number of subsets is exponential (2^(coord_count)). Even computing the loss is expensive : i need to compute the intersection and union of 2 polygons and then compute their surface.
EDIT :
- Removing consecutive points that are aligned is easy and will certainly be the first step to decrease the time complexity of the following steps.
- what i wish is a new polygon whose surface coverage is nearly the same but that has far fewer coordinates : i don't even care if the new polygon is not using any coordinates of the original one (but this seems even more complex than removing some points of the original polygon).
algorithm
asked Jan 3 at 9:22
ThierryThierry
3,7372230
|
show 2 more comments
I have a library that produce a contour, as a list of coordinates like :
[[464.5, 551. ],
[464.5, 550. ],
[464. , 549.5],
[463.5, 549. ],
[463. , 548.5],
[462. , 548.5],
[461. , 548.5],
[460.5, 549. ],
[460. , 549.5],
[459. , 549.5],
[458. , 549.5],
[457. , 549.5],
...
Coordinates are connected by straight lines, defining a closed irregular not self-intersecting polygon.
From the example above, we can see that some points could be removed without losing any surface area, but I don't care if the algorithm has some loss, as long as it is configurable (like intersection of area over union of area > x, or something else ?)
Are there some known algorithm that will reduce the number of points of a closed contour ?
PS: the naive algorithm is to test all subsets of points, and take the smallest subset that is above the acceptable loss. The issue is that i might have hundreds of coordinates, and the number of subsets is exponential (2^(coord_count)). Even computing the loss is expensive : i need to compute the intersection and union of 2 polygons and then compute their surface.
EDIT :
- Removing consecutive points that are aligned is easy and will certainly be the first step to decrease the time complexity of the following steps.
- what i wish is a new polygon whose surface coverage is nearly the same but that has far fewer coordinates : i don't even care if the new polygon is not using any coordinates of the original one (but this seems even more complex than removing some points of the original polygon).
algorithm
asked Jan 3 at 9:22
ThierryThierry
3,7372230
1
If three adjacent points are co-linear, remove the middle point. If a lossy algorithm is acceptable, a priority queue might be useful; the problem then becomes updating the queue after a "surface triangle" is removed.
– meowgoesthedog
Jan 3 at 9:50
Yes, i will start by that to reduce the number of point, but i'd like to remove more points while not losing / addding too much surface (so removing the maximum number of points while not modifying the surface by more than 10% for example)
– Thierry
Jan 3 at 9:53
Could you calculate the area of the triangle formed by three consecutive points and, if it's below the threshold, remove the middle point?
– 500 - Internal Server Error
Jan 3 at 9:55
good idea @500-InternalServerError : i could do that for all 3 consecutive points of the contour, take the smallest triangle (surface), check if it is inside or outside (to see if i update the intersection or the union surface), and repeat the process as along i am above the acceptable loss. (i just checked, and there are issues with this process when removing several points in a row, but it is a good start i guess).
– Thierry
Jan 3 at 10:05
3
The Ramer-Douglas-Peucker algorithm is quite good in reducing points of a route. The desired accuracy (= max error) can be specified.
– Axel Kemper
Jan 3 at 10:11
|
show 2 more comments
I have a library that produce a contour, as a list of coordinates like :
[[464.5, 551. ],
[464.5, 550. ],
[464. , 549.5],
[463.5, 549. ],
[463. , 548.5],
[462. , 548.5],
[461. , 548.5],
[460.5, 549. ],
[460. , 549.5],
[459. , 549.5],
[458. , 549.5],
[457. , 549.5],
...
Coordinates are connected by straight lines, defining a closed irregular not self-intersecting polygon.
From the example above, we can see that some points could be removed without losing any surface area, but I don't care if the algorithm has some loss, as long as it is configurable (like intersection of area over union of area > x, or something else ?)
Are there some known algorithm that will reduce the number of points of a closed contour ?
PS: the naive algorithm is to test all subsets of points, and take the smallest subset that is above the acceptable loss. The issue is that i might have hundreds of coordinates, and the number of subsets is exponential (2^(coord_count)). Even computing the loss is expensive : i need to compute the intersection and union of 2 polygons and then compute their surface.
EDIT :
- Removing consecutive points that are aligned is easy and will certainly be the first step to decrease the time complexity of the following steps.
- what i wish is a new polygon whose surface coverage is nearly the same but that has far fewer coordinates : i don't even care if the new polygon is not using any coordinates of the original one (but this seems even more complex than removing some points of the original polygon).
algorithm
asked Jan 3 at 9:22
ThierryThierry
3,7372230
I have a library that produce a contour, as a list of coordinates like :
[[464.5, 551. ],
[464.5, 550. ],
[464. , 549.5],
[463.5, 549. ],
[463. , 548.5],
[462. , 548.5],
[461. , 548.5],
[460.5, 549. ],
[460. , 549.5],
[459. , 549.5],
[458. , 549.5],
[457. , 549.5],
...
Coordinates are connected by straight lines, defining a closed irregular not self-intersecting polygon.
From the example above, we can see that some points could be removed without losing any surface area, but I don't care if the algorithm has some loss, as long as it is configurable (like intersection of area over union of area > x, or something else ?)
Are there some known algorithm that will reduce the number of points of a closed contour ?
PS: the naive algorithm is to test all subsets of points, and take the smallest subset that is above the acceptable loss. The issue is that i might have hundreds of coordinates, and the number of subsets is exponential (2^(coord_count)). Even computing the loss is expensive : i need to compute the intersection and union of 2 polygons and then compute their surface.
EDIT :
- Removing consecutive points that are aligned is easy and will certainly be the first step to decrease the time complexity of the following steps.
- what i wish is a new polygon whose surface coverage is nearly the same but that has far fewer coordinates : i don't even care if the new polygon is not using any coordinates of the original one (but this seems even more complex than removing some points of the original polygon).
algorithm
algorithm
asked Jan 3 at 9:22
ThierryThierry
3,7372230
asked Jan 3 at 9:22
ThierryThierry
3,7372230
edited Jan 3 at 10:13
Thierry
asked Jan 3 at 9:22
ThierryThierry
3,7372230
asked Jan 3 at 9:22
ThierryThierry
3,7372230
asked Jan 3 at 9:22
ThierryThierry
3,7372230
3,7372230
1
If three adjacent points are co-linear, remove the middle point. If a lossy algorithm is acceptable, a priority queue might be useful; the problem then becomes updating the queue after a "surface triangle" is removed.
– meowgoesthedog
Jan 3 at 9:50
Yes, i will start by that to reduce the number of point, but i'd like to remove more points while not losing / addding too much surface (so removing the maximum number of points while not modifying the surface by more than 10% for example)
– Thierry
Jan 3 at 9:53
Could you calculate the area of the triangle formed by three consecutive points and, if it's below the threshold, remove the middle point?
– 500 - Internal Server Error
Jan 3 at 9:55
good idea @500-InternalServerError : i could do that for all 3 consecutive points of the contour, take the smallest triangle (surface), check if it is inside or outside (to see if i update the intersection or the union surface), and repeat the process as along i am above the acceptable loss. (i just checked, and there are issues with this process when removing several points in a row, but it is a good start i guess).
– Thierry
Jan 3 at 10:05
3
The Ramer-Douglas-Peucker algorithm is quite good in reducing points of a route. The desired accuracy (= max error) can be specified.
– Axel Kemper
Jan 3 at 10:11
|
show 2 more comments
1
If three adjacent points are co-linear, remove the middle point. If a lossy algorithm is acceptable, a priority queue might be useful; the problem then becomes updating the queue after a "surface triangle" is removed.
– meowgoesthedog
Jan 3 at 9:50
Yes, i will start by that to reduce the number of point, but i'd like to remove more points while not losing / addding too much surface (so removing the maximum number of points while not modifying the surface by more than 10% for example)
– Thierry
Jan 3 at 9:53
Could you calculate the area of the triangle formed by three consecutive points and, if it's below the threshold, remove the middle point?
– 500 - Internal Server Error
Jan 3 at 9:55
good idea @500-InternalServerError : i could do that for all 3 consecutive points of the contour, take the smallest triangle (surface), check if it is inside or outside (to see if i update the intersection or the union surface), and repeat the process as along i am above the acceptable loss. (i just checked, and there are issues with this process when removing several points in a row, but it is a good start i guess).
– Thierry
Jan 3 at 10:05
3
The Ramer-Douglas-Peucker algorithm is quite good in reducing points of a route. The desired accuracy (= max error) can be specified.
– Axel Kemper
Jan 3 at 10:11
1
1
If three adjacent points are co-linear, remove the middle point. If a lossy algorithm is acceptable, a priority queue might be useful; the problem then becomes updating the queue after a "surface triangle" is removed.
– meowgoesthedog
Jan 3 at 9:50
If three adjacent points are co-linear, remove the middle point. If a lossy algorithm is acceptable, a priority queue might be useful; the problem then becomes updating the queue after a "surface triangle" is removed.
– meowgoesthedog
Jan 3 at 9:50
Yes, i will start by that to reduce the number of point, but i'd like to remove more points while not losing / addding too much surface (so removing the maximum number of points while not modifying the surface by more than 10% for example)
– Thierry
Jan 3 at 9:53
Yes, i will start by that to reduce the number of point, but i'd like to remove more points while not losing / addding too much surface (so removing the maximum number of points while not modifying the surface by more than 10% for example)
– Thierry
Jan 3 at 9:53
Could you calculate the area of the triangle formed by three consecutive points and, if it's below the threshold, remove the middle point?
– 500 - Internal Server Error
Jan 3 at 9:55
Could you calculate the area of the triangle formed by three consecutive points and, if it's below the threshold, remove the middle point?
– 500 - Internal Server Error
Jan 3 at 9:55
good idea @500-InternalServerError : i could do that for all 3 consecutive points of the contour, take the smallest triangle (surface), check if it is inside or outside (to see if i update the intersection or the union surface), and repeat the process as along i am above the acceptable loss. (i just checked, and there are issues with this process when removing several points in a row, but it is a good start i guess).
– Thierry
Jan 3 at 10:05
good idea @500-InternalServerError : i could do that for all 3 consecutive points of the contour, take the smallest triangle (surface), check if it is inside or outside (to see if i update the intersection or the union surface), and repeat the process as along i am above the acceptable loss. (i just checked, and there are issues with this process when removing several points in a row, but it is a good start i guess).
– Thierry
Jan 3 at 10:05
3
3
The Ramer-Douglas-Peucker algorithm is quite good in reducing points of a route. The desired accuracy (= max error) can be specified.
– Axel Kemper
Jan 3 at 10:11
The Ramer-Douglas-Peucker algorithm is quite good in reducing points of a route. The desired accuracy (= max error) can be specified.
– Axel Kemper
Jan 3 at 10:11
|
show 2 more comments
1 Answer
1
active
oldest
votes
I suggest the following procedure:
- For each 3 consecutive points, check that the line joining the two points either side does not intersect the polygon.
- Calculate the "area contribution" if the middle point is removed; this will be negative if they are convex and positive if concave.
- If you want the optimum result with the fewest number of points, always remove the point which minimizes the net change in area at any stage. Be careful with signs.
- Repeat this until the next optimal net change exceeds the specified tolerance.
The naive version of this algorithm is
O(N^2)in the worst case. You can optimize it somewhat by using a BST / heap to keep track of area deltas corresponding to each point, although updates might be fiddly. A quadtree for intersection testing might also be useful, although it incurs a setup penalty ofO(N log N)which can only be negated if a large number of points is removed.Douglas-Peucker doesn't always produce the optimum result (as many points removed as possible without exceeding the area difference threshold); nor does the original algorithm take self-intersection into account.
answered Jan 3 at 10:24
meowgoesthedogmeowgoesthedog
11.1k41528
There is an issue when we repeat : if for 4 consecutive points, you cut the first 3 by removing area, and then you cut the 3 remaining points by adding surface, at the end, you don't know how much was removed and added, which render the computing of loss problematic. (also let's consider only non intersecting polygons).
– Thierry
Jan 3 at 10:59
@Thierry I'm confused - why wouldn't you know the net change in area? Also, just because the initial polygon doesn't self-intersect, doesn't mean that any removal / addition would not lead to self-intersection (only guaranteed to be true for convex polygons).
– meowgoesthedog
Jan 3 at 11:04
How would you handle computing the loss on your example while combining the yellow line (the right one) with the blue line : they are nearly aligned, and removing the middle point should change the loss by a lot. With the reducted area from the previous step, we would be removing a small area, but when you compare with the original polygon, we would be substracting on the top part, but not really on the bottom one (the one below the blue line)
– Thierry
Jan 3 at 13:42
The sum of what was added - what was removed would be good but to compute (intersection area) / (union area) you need to have the right values of what was added compared to the original polygon vs what was removed.
– Thierry
Jan 3 at 13:46
@Thierry but those two operations cannot be combined, because one will delete a point required by the other. They were just meant to be examples of "negative" or "positive" area changes; no "sequence of action" was implied.
– meowgoesthedog
Jan 3 at 13:46
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54019379%2fknown-algorithm-to-reduce-the-number-of-points-in-a-closed-contour%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I suggest the following procedure:
- For each 3 consecutive points, check that the line joining the two points either side does not intersect the polygon.
- Calculate the "area contribution" if the middle point is removed; this will be negative if they are convex and positive if concave.
- If you want the optimum result with the fewest number of points, always remove the point which minimizes the net change in area at any stage. Be careful with signs.
- Repeat this until the next optimal net change exceeds the specified tolerance.
The naive version of this algorithm is
O(N^2)in the worst case. You can optimize it somewhat by using a BST / heap to keep track of area deltas corresponding to each point, although updates might be fiddly. A quadtree for intersection testing might also be useful, although it incurs a setup penalty ofO(N log N)which can only be negated if a large number of points is removed.Douglas-Peucker doesn't always produce the optimum result (as many points removed as possible without exceeding the area difference threshold); nor does the original algorithm take self-intersection into account.
answered Jan 3 at 10:24
meowgoesthedogmeowgoesthedog
11.1k41528
There is an issue when we repeat : if for 4 consecutive points, you cut the first 3 by removing area, and then you cut the 3 remaining points by adding surface, at the end, you don't know how much was removed and added, which render the computing of loss problematic. (also let's consider only non intersecting polygons).
– Thierry
Jan 3 at 10:59
@Thierry I'm confused - why wouldn't you know the net change in area? Also, just because the initial polygon doesn't self-intersect, doesn't mean that any removal / addition would not lead to self-intersection (only guaranteed to be true for convex polygons).
– meowgoesthedog
Jan 3 at 11:04
How would you handle computing the loss on your example while combining the yellow line (the right one) with the blue line : they are nearly aligned, and removing the middle point should change the loss by a lot. With the reducted area from the previous step, we would be removing a small area, but when you compare with the original polygon, we would be substracting on the top part, but not really on the bottom one (the one below the blue line)
– Thierry
Jan 3 at 13:42
The sum of what was added - what was removed would be good but to compute (intersection area) / (union area) you need to have the right values of what was added compared to the original polygon vs what was removed.
– Thierry
Jan 3 at 13:46
@Thierry but those two operations cannot be combined, because one will delete a point required by the other. They were just meant to be examples of "negative" or "positive" area changes; no "sequence of action" was implied.
– meowgoesthedog
Jan 3 at 13:46
|
show 1 more comment
I suggest the following procedure:
- For each 3 consecutive points, check that the line joining the two points either side does not intersect the polygon.
- Calculate the "area contribution" if the middle point is removed; this will be negative if they are convex and positive if concave.
- If you want the optimum result with the fewest number of points, always remove the point which minimizes the net change in area at any stage. Be careful with signs.
- Repeat this until the next optimal net change exceeds the specified tolerance.
The naive version of this algorithm is
O(N^2)in the worst case. You can optimize it somewhat by using a BST / heap to keep track of area deltas corresponding to each point, although updates might be fiddly. A quadtree for intersection testing might also be useful, although it incurs a setup penalty ofO(N log N)which can only be negated if a large number of points is removed.Douglas-Peucker doesn't always produce the optimum result (as many points removed as possible without exceeding the area difference threshold); nor does the original algorithm take self-intersection into account.
answered Jan 3 at 10:24
meowgoesthedogmeowgoesthedog
11.1k41528
There is an issue when we repeat : if for 4 consecutive points, you cut the first 3 by removing area, and then you cut the 3 remaining points by adding surface, at the end, you don't know how much was removed and added, which render the computing of loss problematic. (also let's consider only non intersecting polygons).
– Thierry
Jan 3 at 10:59
@Thierry I'm confused - why wouldn't you know the net change in area? Also, just because the initial polygon doesn't self-intersect, doesn't mean that any removal / addition would not lead to self-intersection (only guaranteed to be true for convex polygons).
– meowgoesthedog
Jan 3 at 11:04
How would you handle computing the loss on your example while combining the yellow line (the right one) with the blue line : they are nearly aligned, and removing the middle point should change the loss by a lot. With the reducted area from the previous step, we would be removing a small area, but when you compare with the original polygon, we would be substracting on the top part, but not really on the bottom one (the one below the blue line)
– Thierry
Jan 3 at 13:42
The sum of what was added - what was removed would be good but to compute (intersection area) / (union area) you need to have the right values of what was added compared to the original polygon vs what was removed.
– Thierry
Jan 3 at 13:46
@Thierry but those two operations cannot be combined, because one will delete a point required by the other. They were just meant to be examples of "negative" or "positive" area changes; no "sequence of action" was implied.
– meowgoesthedog
Jan 3 at 13:46
|
show 1 more comment
I suggest the following procedure:
- For each 3 consecutive points, check that the line joining the two points either side does not intersect the polygon.
- Calculate the "area contribution" if the middle point is removed; this will be negative if they are convex and positive if concave.
- If you want the optimum result with the fewest number of points, always remove the point which minimizes the net change in area at any stage. Be careful with signs.
- Repeat this until the next optimal net change exceeds the specified tolerance.
The naive version of this algorithm is
O(N^2)in the worst case. You can optimize it somewhat by using a BST / heap to keep track of area deltas corresponding to each point, although updates might be fiddly. A quadtree for intersection testing might also be useful, although it incurs a setup penalty ofO(N log N)which can only be negated if a large number of points is removed.Douglas-Peucker doesn't always produce the optimum result (as many points removed as possible without exceeding the area difference threshold); nor does the original algorithm take self-intersection into account.
answered Jan 3 at 10:24
meowgoesthedogmeowgoesthedog
11.1k41528
I suggest the following procedure:
- For each 3 consecutive points, check that the line joining the two points either side does not intersect the polygon.
- Calculate the "area contribution" if the middle point is removed; this will be negative if they are convex and positive if concave.
- If you want the optimum result with the fewest number of points, always remove the point which minimizes the net change in area at any stage. Be careful with signs.
- Repeat this until the next optimal net change exceeds the specified tolerance.
The naive version of this algorithm is
O(N^2)in the worst case. You can optimize it somewhat by using a BST / heap to keep track of area deltas corresponding to each point, although updates might be fiddly. A quadtree for intersection testing might also be useful, although it incurs a setup penalty ofO(N log N)which can only be negated if a large number of points is removed.Douglas-Peucker doesn't always produce the optimum result (as many points removed as possible without exceeding the area difference threshold); nor does the original algorithm take self-intersection into account.
answered Jan 3 at 10:24
meowgoesthedogmeowgoesthedog
11.1k41528
edited Jan 3 at 10:36
answered Jan 3 at 10:24
meowgoesthedogmeowgoesthedog
11.1k41528
answered Jan 3 at 10:24
meowgoesthedogmeowgoesthedog
11.1k41528
answered Jan 3 at 10:24
meowgoesthedogmeowgoesthedog
11.1k41528
11.1k41528
There is an issue when we repeat : if for 4 consecutive points, you cut the first 3 by removing area, and then you cut the 3 remaining points by adding surface, at the end, you don't know how much was removed and added, which render the computing of loss problematic. (also let's consider only non intersecting polygons).
– Thierry
Jan 3 at 10:59
@Thierry I'm confused - why wouldn't you know the net change in area? Also, just because the initial polygon doesn't self-intersect, doesn't mean that any removal / addition would not lead to self-intersection (only guaranteed to be true for convex polygons).
– meowgoesthedog
Jan 3 at 11:04
How would you handle computing the loss on your example while combining the yellow line (the right one) with the blue line : they are nearly aligned, and removing the middle point should change the loss by a lot. With the reducted area from the previous step, we would be removing a small area, but when you compare with the original polygon, we would be substracting on the top part, but not really on the bottom one (the one below the blue line)
– Thierry
Jan 3 at 13:42
The sum of what was added - what was removed would be good but to compute (intersection area) / (union area) you need to have the right values of what was added compared to the original polygon vs what was removed.
– Thierry
Jan 3 at 13:46
@Thierry but those two operations cannot be combined, because one will delete a point required by the other. They were just meant to be examples of "negative" or "positive" area changes; no "sequence of action" was implied.
– meowgoesthedog
Jan 3 at 13:46
|
show 1 more comment
There is an issue when we repeat : if for 4 consecutive points, you cut the first 3 by removing area, and then you cut the 3 remaining points by adding surface, at the end, you don't know how much was removed and added, which render the computing of loss problematic. (also let's consider only non intersecting polygons).
– Thierry
Jan 3 at 10:59
@Thierry I'm confused - why wouldn't you know the net change in area? Also, just because the initial polygon doesn't self-intersect, doesn't mean that any removal / addition would not lead to self-intersection (only guaranteed to be true for convex polygons).
– meowgoesthedog
Jan 3 at 11:04
How would you handle computing the loss on your example while combining the yellow line (the right one) with the blue line : they are nearly aligned, and removing the middle point should change the loss by a lot. With the reducted area from the previous step, we would be removing a small area, but when you compare with the original polygon, we would be substracting on the top part, but not really on the bottom one (the one below the blue line)
– Thierry
Jan 3 at 13:42
The sum of what was added - what was removed would be good but to compute (intersection area) / (union area) you need to have the right values of what was added compared to the original polygon vs what was removed.
– Thierry
Jan 3 at 13:46
@Thierry but those two operations cannot be combined, because one will delete a point required by the other. They were just meant to be examples of "negative" or "positive" area changes; no "sequence of action" was implied.
– meowgoesthedog
Jan 3 at 13:46
There is an issue when we repeat : if for 4 consecutive points, you cut the first 3 by removing area, and then you cut the 3 remaining points by adding surface, at the end, you don't know how much was removed and added, which render the computing of loss problematic. (also let's consider only non intersecting polygons).
– Thierry
Jan 3 at 10:59
There is an issue when we repeat : if for 4 consecutive points, you cut the first 3 by removing area, and then you cut the 3 remaining points by adding surface, at the end, you don't know how much was removed and added, which render the computing of loss problematic. (also let's consider only non intersecting polygons).
– Thierry
Jan 3 at 10:59
@Thierry I'm confused - why wouldn't you know the net change in area? Also, just because the initial polygon doesn't self-intersect, doesn't mean that any removal / addition would not lead to self-intersection (only guaranteed to be true for convex polygons).
– meowgoesthedog
Jan 3 at 11:04
@Thierry I'm confused - why wouldn't you know the net change in area? Also, just because the initial polygon doesn't self-intersect, doesn't mean that any removal / addition would not lead to self-intersection (only guaranteed to be true for convex polygons).
– meowgoesthedog
Jan 3 at 11:04
How would you handle computing the loss on your example while combining the yellow line (the right one) with the blue line : they are nearly aligned, and removing the middle point should change the loss by a lot. With the reducted area from the previous step, we would be removing a small area, but when you compare with the original polygon, we would be substracting on the top part, but not really on the bottom one (the one below the blue line)
– Thierry
Jan 3 at 13:42
How would you handle computing the loss on your example while combining the yellow line (the right one) with the blue line : they are nearly aligned, and removing the middle point should change the loss by a lot. With the reducted area from the previous step, we would be removing a small area, but when you compare with the original polygon, we would be substracting on the top part, but not really on the bottom one (the one below the blue line)
– Thierry
Jan 3 at 13:42
The sum of what was added - what was removed would be good but to compute (intersection area) / (union area) you need to have the right values of what was added compared to the original polygon vs what was removed.
– Thierry
Jan 3 at 13:46
The sum of what was added - what was removed would be good but to compute (intersection area) / (union area) you need to have the right values of what was added compared to the original polygon vs what was removed.
– Thierry
Jan 3 at 13:46
@Thierry but those two operations cannot be combined, because one will delete a point required by the other. They were just meant to be examples of "negative" or "positive" area changes; no "sequence of action" was implied.
– meowgoesthedog
Jan 3 at 13:46
@Thierry but those two operations cannot be combined, because one will delete a point required by the other. They were just meant to be examples of "negative" or "positive" area changes; no "sequence of action" was implied.
– meowgoesthedog
Jan 3 at 13:46
|
show 1 more comment
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54019379%2fknown-algorithm-to-reduce-the-number-of-points-in-a-closed-contour%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
If three adjacent points are co-linear, remove the middle point. If a lossy algorithm is acceptable, a priority queue might be useful; the problem then becomes updating the queue after a "surface triangle" is removed.
– meowgoesthedog
Jan 3 at 9:50
Yes, i will start by that to reduce the number of point, but i'd like to remove more points while not losing / addding too much surface (so removing the maximum number of points while not modifying the surface by more than 10% for example)
– Thierry
Jan 3 at 9:53
Could you calculate the area of the triangle formed by three consecutive points and, if it's below the threshold, remove the middle point?
– 500 - Internal Server Error
Jan 3 at 9:55
good idea @500-InternalServerError : i could do that for all 3 consecutive points of the contour, take the smallest triangle (surface), check if it is inside or outside (to see if i update the intersection or the union surface), and repeat the process as along i am above the acceptable loss. (i just checked, and there are issues with this process when removing several points in a row, but it is a good start i guess).
– Thierry
Jan 3 at 10:05
3
The Ramer-Douglas-Peucker algorithm is quite good in reducing points of a route. The desired accuracy (= max error) can be specified.
– Axel Kemper
Jan 3 at 10:11